基于遗传算法求解TSP问题实验报告

人工智能课程项目报告1基于遗传算法求解TSP问题班级，学号，姓名摘要：巡回旅行商问题（TSP）是一个组合优化方面的问题，从理论上讲，使用穷举法不但可以求解TSP问题，而且还可以得到最优解。但是，利用穷举法所耗费的时间巨大的，当问题的规模很大时，穷举法的执行效率较低，不能满足及时的需要。遗传算法是计算机科学人工智能领域中用于解决最优化的一种搜索启发式算法，是进化算法的一种。该算法通过模拟生物学交叉、变异等方式，是当前向最优解的方向进化，因此使用于TSP问题的求解。关键词：人工智能；TSP问题；遗传算法本组成员：林志青，韩会雯，赵昊罡本人分工：掌握遗传算法的基本原理，编写遗传算法中部分匹配交叉、循环交叉和循序交叉的具体实现过程。1引言旅行商问题，即TSP问题，是一个最优解的求解问题。假设有n个城市，并且每个城市之间的距离已知，则如何只走一遍并获得最短路径为该问题的具体解释。对于TSP问题的解决，有穷举法、分支限界法等求解方式，该文章主要介绍遗传算法求解过程。遗传算法简称GA，在本质上是一种求解问题的高效并行全局搜索方法。遗传算法从任意一个初始化的群体出发，通过随机选择、交叉和变异等遗传操作，使群体一代一代的进化到搜索空间中越来越好的区域，直至抵达最优解。在遗传算法中，交叉操作为主要操作之一，包括部分匹配交叉、循环交叉和顺序交叉等。2算法原理与系统设计执行遗传算法，根据需要设定相应的交叉因子、变异因子和迭代次数，并选择相应的交叉算法，当程序图形显示并运算时会得到当前的最优解，判断是否获得最终的最优解，若已得到所需结果，则停止运行，否则继续执行。具体流程图如下所示：人工智能课程项目报告2开始设定交叉因子、变异因子和迭代次数选择交叉操作循环交叉法部分分配交叉法顺序交叉法是否获得最优解？是否停止运行？结束是是否部分匹配交叉（PMX）：先随机生成两个交叉点，定义这两点间的区域为匹配区域，并交换两个父代的匹配区域。如下图所示：父代A：872|130|9546父代B：983|567|1420交换后变为：tempA:872|567|9546tempB:983|130|1420对于tempA、tempB中匹配区域以外出现的数码重复，要依据匹配区域内的位置逐一进行替换。匹配关系：1——53——67——0子代A：802|567|9143子代B：986|130|5427顺序交叉法（OX）：从父代Ａ随机选一个编码子串，放到子代Ａ的对应位置；子代Ａ空余的位置从父代B中按B的顺序选取（与己有编码不重复）。同理可得子代B，如下所示：父代A:872|139|0546父代B:983|567|1420交叉过程：对于父代A，选择139进行遗传到下一代，其余部分从父代B中按照顺序随机选取，且不能和1、3、9数字相同，放到子代的对应位置，得到下一代。人工智能课程项目报告3交叉后：子代A:856|139|7420子代B:821|567|3904循环交叉法（CX）：根据父代中的相应位置的基因得到相应的循环因子，该循环因子为子代的一部分，其余的因子从另一个父代中查找，找到不同于循环因子的基因并放到子代的对应位置，形成新的子代。父代A：123456789父代B：546923781交叉过程：随机选择一个城市，如1，找到在父代B中对应的城市为5，再再返回到父代A中的城市5，对应的父代B中的城市为2，依次查找，直达最终的城市为1为止。因此父代A的循环因子为152491，另一子代的处理过程相似。交叉后：用循环的基因构成子代A，顺序与父代A一样12459，用父代B剩余的基因填满子代A：1264537893系统实现部分匹配交叉：//先随机产生两个交叉点，定义这两点间的区域为匹配区域，并用交换两个父代的匹配区域。doublerand=Math.random();if(randpc){intm=(int)(Math.random()*cityNum);intn=(int)(Math.random()*cityNum);while(m==n)n=(int)(Math.random()*cityNum);if(mn){inttemp=m;m=n;n=temp;}inttempA[]=newint[n-m];inttempB[]=newint[n-m];for(inte=m;en;e++){tempA[e-m]=population[a].gene[e];tempB[e-m]=population[b].gene[e];}for(inte=m;en;e++){population[a].gene[e]=tempB[e-m];population[b].gene[e]=tempA[e-m];}//对于tempA、tempB中匹配区域以外出现的数码重复，要依据匹配区域内的位置逐一进行替换for(inte=0;em;e++){intp;while((p=Search(population[a].gene[e],tempB))!=-1){population[a].gene[e]=tempA[p];}while((p=Search(population[b].gene[e],tempA))!=-1){population[b].gene[e]=tempB[p];}}人工智能课程项目报告4for(inte=n;ecityNum;e++){intp;while((p=Search(population[a].gene[e],tempB))!=-1){population[a].gene[e]=tempA[p];}while((p=Search(population[b].gene[e],tempA))!=-1){population[b].gene[e]=tempB[p];}}顺序交叉：//选择一定长度的基因段进行交换doublerand=Math.random();if(randpc){intm=(int)(Math.random()*cityNum);intn=(int)(Math.random()*cityNum);while(m==n)n=(int)(Math.random()*cityNum);if(mn){inttemp=m;m=n;n=temp;}inttempA[]=newint[n-m];inttempB[]=newint[n-m];for(inte=m;en;e++){tempA[e-m]=population[a].gene[e];tempB[e-m]=population[b].gene[e];}inttemp[]=newint[cityNum];for(inte=0;ecityNum;e++){temp[e]=population[a].gene[e];}//剩余部分从另一个父代中按照顺序进行选取，并随机选取未在上述交换序列中的数字按位置//存放到子代中if(m==0){intq=n;for(inte=0;ecityNum;e++){if(Search(population[b].gene[e],tempA)==-1){population[a].gene[q]=population[b].gene[e];q++;}}q=n;for(inte=0;ecityNum;e++){if(Search(temp[e],tempB)==-1){population[b].gene[q]=temp[e];q++;}}}else{intq=0;for(inte=0;ecityNum;e++){if(Search(population[b].gene[e],tempA)==-1){population[a].gene[q]=population[b].gene[e];if(q==m-1){q=q+1+(n-m);}人工智能课程项目报告5else{q++;}}}q=0;for(inte=0;ecityNum;e++){if(Search(temp[e],tempB)==-1){population[b].gene[q]=temp[e];if(q==m-1){q=q+1+(n-m);}else{q++;}}}}循环交叉：//从当前染色体A中随机找到基因位置，对应得到另一染色体B中相应位置的基因，//找到新基因在染色体A中的位置，继续寻找下一基因，直到和最开始的基因相同intq=(int)(Math.random()*cityNum);intv=population[a].gene[q];tempA[q]=1;intt=0;while((t=population[b].gene[q])!=v){q=Search(t,population[a].gene);tempA[q]=1;}//将染色体B中不属于循环因子的基因按位置填充到下一代染色体中for(inte=0;ecityNum;e++){if(tempA[e]==0){population[a].gene[e]=population[b].gene[e];}}q=(int)(Math.random()*cityNum);v=population[b].gene[q];tempB[q]=1;t=0;while((t=temp[q])!=v){q=Search(t,population[b].gene);tempB[q]=1;}for(inte=0;ecityNum;e++){if(tempB[e]==0){population[b].gene[e]=temp[e];}}4实验或测试结果部分匹配算法：人工智能课程项目报告6当前迭代次数：102539当前路径长度：144283顺序交叉法：当前迭代次数：111974当前路径长度：153466循环交叉法：人工智能课程项目报告7当前迭代次数：71302当前路径长度：1397145结论从上面的三个算法的实现效果来看，当迭代的次数有限时并没有得到最终的最优解，只是获得了当前情况下花费最短和适应度最高的路径。从中可以了解到，遗传算法能够向最优解的方向进行进化，但是进化的方向是随机的，即不一定在最开始迭代中就得到最优解的方向，而且不同的搜索算法所得到的最优解尽管不是最终的解，但是各算法的当前最优解是相近的，因此遗传算法不同方向的进化程度是相似的，并有达到最优解的可能性。该次求解过程中，主要考虑了交叉操作对问题求解的影响情况，仅仅是遗传算法中的一个部分（选择、交叉、变异），该操作对进化的贡献是有限的，因此要得到最终的路径，需要综合考虑各种操作对进化的影响。参考文献[1]王小平，曹立明.遗传算法理论应用于软件实现[M].西安：西安交通大学出版社，2002:129[2]余一娇.用简单遗传算法求解TSP问题的参数组合研究[j].华中师范大学学报（自然科学版），2002,36(1):25-26.[3]陈国良，等.遗传算法及其应用[M].北京：人民邮电出版社，1996[4]周明，孙树栋.遗传算法原理及应用[M].北京：国防工业出版社，1997