人工智能课程项目报告
基于遗传算法求解TSP问题
班级，学号，姓名
摘要：巡回旅行商问题（TSP）是一个组合优化方面的问题，从理论上讲，使用穷举法不但可以求解TSP问题，而且还可以得到最优解。但是，利用穷举法所耗费的时间巨大的，当问题的规模很大时，穷举法的执行效率较低，不能满足及时的需要。
遗传算法是计算机科学人工智能领域中用于解决最优化的一种搜索启发式算法，是进化算法的一种。该算法通过模拟生物学交叉、变异等方式，是当前向最优解的方向进化，因此使用于TSP问题的求解。
关键词：人工智能；TSP问题；遗传算法
本组成员：林志青，韩会雯，赵昊罡
本人分工：掌握遗传算法的基本原理，编写遗传算法中部分匹配交叉、循环交叉和循序交叉的具体实现过程。
1 引言
旅行商问题，即TSP问题，是一个最优解的求解问题。假设有n个城市，并且每个城市之间的距离已知，则如何只走一遍并获得最短路径为该问题的具体解释。
对于TSP问题的解决，有穷举法、分支限界法等求解方式，该文章主要介绍遗传算法求解过程。 遗传算法简称GA，在本质上是一种求解问题的高效并行全局搜索方法。遗传算法从任意一个初始化的群体出发，通过随机选择、交叉和变异等遗传操作，使群体一代一代的进化到搜索空间中越来越好的区域，直至抵达最优解。
在遗传算法中，交叉操作为主要操作之一，包括部分匹配交叉、循环交叉和顺序交叉等。
2 算法原理与系统设计
执行遗传算法，根据需要设定相应的交叉因子、变异因子和迭代次数，并选择相应的交叉算法，当程序图形显示并运算时会得到当前的最优解，判断是否获得最终的最优解，若已得到所需结果，则停止运行，否则继续执行。具体流程图如下所示：
1
人工智能课程项目报告
开始设定交叉因子、变异因子和迭代次数选择交叉操作部分分配交叉法循环交叉法顺序交叉法是否获得最优解？是是否停止运行？是否结束 部分匹配交叉（PMX）：先随机生成两个交叉点，定义这两点间的区域为匹配区域，并交换两个父代的匹配区域。如下图所示：
父代A：872 | 130 | 9546 父代B：983 | 567 | 1420 交换后变为：
temp A: 872 | 567 | 9546 temp B: 983 | 130 | 1420 对于 temp A、tempB中匹配区域以外出现的数码重复，要依据匹配区域内的位置逐一进行替换。匹配关系：1<——>5 3<——>6 7<——>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数字相同，放到子代的对应位置，得到下一代。
2
人工智能课程项目报告
交叉后：
子代A: 856 | 139 | 7420 子代B: 821 | 567 | 3904 循环交叉法（CX）：根据父代中的相应位置的基因得到相应的循环因子，该循环因子为子代的一部分，其余的因子从另一个父代中查找，找到不同于循环因子的基因并放到子代的对应位置，形成新的子代。
父代A：1 2 3 4 5 6 7 8 9 父代B：5 4 6 9 2 3 7 8 1
交叉过程：随机选择一个城市，如1，找到在父代B中对应的城市为5，再再返回到父代A中的城市5，对应的父代B中的城市为2，依次查找，直达最终的城市为1为止。因此父代A的循环因子为1?5?2?4?9?1，另一子代的处理过程相似。
交叉后：
用循环的基因构成子代A，顺序与父代A一样 1 2 4 5 9 ，用父代B剩余的基因填满子代A： 1 2 6 4 5 3 7 8 9
3 系统实现
部分匹配交叉：
//先随机产生两个交叉点，定义这两点间的区域为匹配区域，并用交换两个父代的匹配区域。 double rand = Math.random();
if(rand int m = (int)(Math.random()*cityNum); int n = (int)(Math.random()*cityNum); while(m==n) n = (int)(Math.random()*cityNum); if(m>n){ int temp = m; m = n; n = temp; } int tempA[] = new int[n-m]; int tempB[] = new int[n-m]; for(int e=m;e tempA[e-m] = population[a].gene[e]; tempB[e-m] = population[b].gene[e]; } for(int e=m;e population[a].gene[e] = tempB[e-m]; population[b].gene[e] = tempA[e-m]; } //对于tempA、tempB中匹配区域以外出现的数码重复，要依据匹配区域内的位置逐一进行替换 for(int e=0;e int p; 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];} } 3 人工智能课程项目报告 for(int e=n;e int p; 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];} } 顺序交叉： //选择一定长度的基因段进行交换 double rand = Math.random(); if(rand int m = (int)(Math.random()*cityNum); int n = (int)(Math.random()*cityNum); while(m==n) n = (int)(Math.random()*cityNum); if(m>n){ int temp = m; m = n; n = temp; } int tempA[] = new int[n-m]; int tempB[] = new int[n-m]; for(int e=m;e tempA[e-m] = population[a].gene[e]; tempB[e-m] = population[b].gene[e]; } int temp[] = new int[cityNum]; for(int e=0;e //剩余部分从另一个父代中按照顺序进行选取，并随机选取未在上述交换序列中的数字按位置 //存放到子代中 if(m==0){ int q = n; for(int e=0;e if(Search(population[b].gene[e], tempA)==-1){ population[a].gene[q] = population[b].gene[e]; q++; } } q=n; for(int e=0;e if(Search(temp[e], tempB)==-1){ population[b].gene[q] = temp[e]; q++; } } } else{ int q=0; for(int e=0;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); } 4 人工智能课程项目报告 else{ q++; } } } q=0; for(int e=0;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中的位置，继续寻找下一基因，直到和最开始的基因相同 int q = (int)(Math.random()*cityNum); int v = population[a].gene[q]; tempA[q] = 1; int t=0; while((t=population[b].gene[q])!=v){ q = Search(t, population[a].gene); tempA[q] = 1; } //将染色体B中不属于循环因子的基因按位置填充到下一代染色体中 for(int e=0;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;