遗传算法 | Java版GA

　　嗯哼，上一篇博客中用Java实现了遗传算法求解TSP（Java版GA_TSP（我的第一个Java程序）），但明显求解效果不太好，都没太好意思贴出具体的结果，今天捣腾了下，对算法做了一些小改进，求解效果也稍微好了点。总算是能见人了，具体改进如下：

　　（1）选择操作由原先的单一轮盘赌策略（Roulette Strategy）改为轮盘赌策略 + 精英策略（Elite Strategy）, 在保证解的多样性的基础上，强化集中搜索。

　　（2）在构建新种群方式上，将原先的无差别接受扰动改为不接受退化的个体。

　　[注]选择操作是形成进行繁衍（扰动产生新解）操作的前提，注意区分上述（1）和（2）。

　　下面贴干货：

 int[][] newPop = new int[PopSize][N];

 //5%的精英策略

 for (int p = 0; p < 0.05*PopSize; p++) {

     for (int q = 0;q < N; q++) {

         newPop[p][q] = BS[q];

     }

 }

 //95%的轮盘赌策略

 for (int p = (int)0.05*PopSize; p < PopSize; p++) {

     double rand = Math.random();

     for (int r = 0; r < PopSize; r++) {

         if (rand > cusFit[r] && rand <= cusFit[r+1]) {

             for (int q = 0;q < N; q++) {

                 newPop[p][q] = Pop[r][q];

             }

         }

     }

 }

 //扰动操作

 for (int p = 1; p < PopSize; p++) {

     double R = Math.random();

     int[] S = new int[N];

     for (int i = 0; i < N; i++) {

         S[i] = newPop[p][i];

     }

     int[] S0 = new int[N];

     int[] S1 = new int[N];

     if (R < 0.33) {

         S0 = Sharking.Swap(S);

         if (GA.Pop.fit(S0) < GA.Pop.fit(S)) {

             System.arraycopy(S, 0, S1, 0, N);

         }else {

             System.arraycopy(S0, 0, S1, 0, N);

         }

     }else if (R > 0.67) {

         S0 = Sharking.Insert(S);

         if (GA.Pop.fit(S0) < GA.Pop.fit(S)) {

             System.arraycopy(S, 0, S1, 0, N);

         }else {

             System.arraycopy(S0, 0, S1, 0, N);

         }

     }else {

         S0 = Sharking.Flip(S);

         if (GA.Pop.fit(S0) < GA.Pop.fit(S)) {

             System.arraycopy(S, 0, S1, 0, N);

         }else {

             System.arraycopy(S0, 0, S1, 0, N);

         }

     }

　　求解结果如下，总迭代次数为200次，有效进化次数7次，误差19.13%。没有多次运行，感觉结果一般，但明显比第一版的遗传算法求解效果好很多。再接再厉~~~~

巴特西

遗传算法 | Java版GA_TSP （2）

最新文章

热门文章