TSP问题的遗传算法求解摘要：遗传算法是模拟生物进化过程的一种新的全局优化搜索算法，本文简单介绍了遗传算法，并应用标准遗传算法对旅行包问题进行求解。
关键词：遗传算法、旅行包问题一、旅行包问题描述：旅行商问题，即TSP问题（Traveling Saleman Problem）是数学领域的一个著名问题，也称作货郎担问题，简单描述为：一个旅行商需要拜访n个城市（1，2，…，n），他必须选择所走的路径，每个城市只能拜访一次，最后回到原来出发的城市，使得所走的路径最短。
其最早的描述是1759年欧拉研究的骑士周游问题，对于国际象棋棋盘中的64个方格，走访64个方格一次且最终返回起始点。
用图论解释为有一个图G=（V,E），其中V是顶点集，E是边集，设D=（d ij）是有顶点i和顶点j之间的距离所组成的距离矩阵，旅行商问题就是求出一条通过所有顶点且每个顶点只能通过一次的具有最短距离的回路。
若对于城市V={v1，v2，v3，...，vn}的一个访问顺序为T=(t1，t2，t3，…，ti，…，tn)，其中ti∈V(i=1，2，3，…，n)，且记tn+1= t1，则旅行商问题的数学模型为：min L=Σd(t(i),t(i+1)) （i=1，…，n）旅行商问题是一个典型组合优化的问题，是一个NP难问题，其可能的路径数为（n-1）！，随着城市数目的增加，路径数急剧增加，对与小规模的旅行商问题，可以采取穷举法得到最优路径，但对于大型旅行商问题，则很难采用穷举法进行计算。
在生活中TSP有着广泛的应用，在交通方面，如何规划合理高效的道路交通，以减少拥堵；在物流方面，更好的规划物流，减少运营成本；在互联网中，如何设置节点，更好的让信息流动。
许多实际工程问题属于大规模TSP，Korte于1988年提出的VLSI芯片加工问题可以对应于1.2e6的城市TSP，Bland于1989年提出X-ray衍射问题对应于14000城市TSP，Litke于1984年提出电路板设计中钻孔问题对应于17000城市TSP，以及Grotschel1991年提出的对应于442城市TSP的PCB442问题。
二、遗传算法简介遗传算法（Genetic Algorithm，GA）是借鉴生物界自然选择和自然遗传机制“适者生存”的一种高度并行、随机化和自适应的全局优化算法，其首先由Holland与1975年提出。
其将问题的求解表示成“染色体”的适者生存过程，通过“染色体“群的一代代不断进化，包括复制、交叉和变异等操作，最终收敛到”最适应环境“的个体，从而得到问体的最优解。
标准的遗传算法的只要步骤可描述为为：1、随机产生一组初始个体构成初始种群，并评价每一个体的适配值；2、判断算法的收敛准则是否满足。
若满足则输出搜索结果，否则执行下面步骤；3、根据适配值大小以一定的方式执行复制操作；4、按交叉概率pc执行交叉操作；5、按变异概率pm执行变异操作。
6、返回2执行新一轮的复制、交叉、变异。
在算法中，适配值是对染色体进行评价的一种指标，是遗传算法进行优化所用的主要信息，与个体的目标值存在一种对应关系；复制操作通常采用比例复制，即复制概率正比于个体适配值，适配值高的个体在下一代中复制自身的概率大，从而提高种群的平均适配值；交叉操作通过交换两父代个体的部分信息构成后代个体，使得后代继承父代的有效模式，从而有助于产生优良个体；变异操作通过随机改变个体的某些基因而产生新个体，有助于增加种群的多样性，避免早熟收敛。
遗传算法利用生物进化和遗传的思想实现优化过程，区别与传统优化算法1、算法进行全空间并行搜索，并将搜索重点集中于性能高的部分，从而能够提高效率并且不易陷入局部最小。
2、算法具有固有并行性，通过对种群的遗传处理可以处理大量的模式，并且容易并行实现；其主要设计如下：1、确定问题的编码方案。
2、确定适配值函数。
3、遗传算子的设计。
4、算法参数（种群数目、交叉与变异概率和进化代数等）的选取。
5、确定函数终止条件。
三、对TSP问题的遗传算法实现设计思路：1、初始化城市距离采用一个city_xy函数获取n个城市的TSP问题的坐标，保存在city矩阵中，并且用city_dis矩阵表示任意两个城市之间的距离，矩阵中的元素city_dis（i，j)代表第i个城市与第j个城市间的距离。
2、初始化种群通过randperm函数，生成一个一维随机向量（是整数1，2，3，4，5的任意排列），然后将其赋给二维数组group的第一列，作为一个个体。
如此循环N次，生成了第一代种群，种群的每个个体代表一条路径。
3、计算适应度采用的适应度函数为个体巡回路径的总长度的函数。
具体为adapt(1,i)=(n*maxdis-dis) (1) 在式（1）中，adapt(1,i)表示第i个个体的适应度函数，maxdis为城市间的最大距离，dis为个体巡回路径的总长度，这样定义的适应度，当路经越短时适应度值越大。
在适应度值的基础上，给出的计算个体期望复制数的表达式为adaptnum(1,i)=(N*adapt(1,i)/ sumadapt) (2) 其中，sumadapt为种群适应度之和。
4、复制采用优秀个体的大比例保护基础上的随机数复制法。
具体做法为在生成下一代个体时，先将最大适应度对应的路径个体以较大的比例复制到下一代，然后再用随机数复制法生成下一代的其他个体。
其中，有一个问题必须考虑，即若某一次生成的随机数过大，结果能复制一个或极少个样本。
为了避免这一情况，采用了限制措施，即压低了随机数的上限。
5、交叉采用的方法为按步长的单点交叉，为随机选择一对样本，再随机选择一个交叉点位置，按一定的步长进行交叉点的选择。
选择一个步长而不是将其设为1，是因为若某一位置处的城市代码因为进行了交叉而发生了改变，则其经过该处的两个距离都会改变。
这种交叉兼有遗传和变异两方面的作用，因为若交叉点处的城市编号都相同，则对两个个体而言交叉后样本无变化，否则样本有变化。
6、变异方法为随机两点I，J的交互位置法。
对于A= [1 2 3 4 5 6 7 8 9 10]，若I= 3, J=8，则变异后B= [1 2 8 4 5 6 7 3 9 10]虽然是简单的随机两点交互，但实际上已经有40%的距离发生了改变。
若用d ij表示城市i与j之间的距离，则变异后与变异前样本路径的距离差为B23十B34 + B78十B89一A23十A34 + A78 + A89可见，随机两点交互足以产生新的模式样本。
较大地提高变异率就会产生大量的新样本，全局最优样本出现的概率随之提高。
为了收敛到最优解，借鉴模拟退火算法的思想，采取了变异率由很大逐渐衰减到较小的数量，这样做也利于找到全局最优解。
7、将复制，交叉，变异后得到的种群group1重新赋给group,然后重复3，4，5，6步操作。
直至满足循环停止条件，即找到最优路径。
仿真实验：TSP实验数据点取为：10城市TSP（自己随机选取10个点）：0，0；12，32；5，25;8,45;33,17;25,7;15,15;15,25;25,15;41,12 30城市TSP问题（d=423.741 by D.B.Fogel）：41,94;37,84;54,67;25,62;7,64;2,99;68,58;71,44;54,62;83,6 9;64,60;18,54;22,60;83,46;91,38;25,38;24,42;58,69;71,71; 74,78;87,76;18,40;13,40;82,7;62,32;58,35;45,21;41,26;44, 35;4,5050城市TSP问题（d=427.855 by D.B.Fogel）：31，32；32，39；40，30；37，69；27，68；37，52；38，46；31，62；30，48；21，47；25，55；16，57；17，63；42，41；17，33；25，32；5，64；8，52；12，42；7，38；5，25；10，17；45，35；42，57；32，22；27，23；56，37；52，41；49，49；58，48；57，58；39，10；46，10；59，15；51，21；48，28；52，33；58，27；61，33；62，63；20，26；5，6；13，13；21，10；30，15；36，16；62，42；63，69；52，64；43，67对与10点TSP 问题，城市数比较少，每一代个体数目为200，进化代数取为1000代，算法执行结果为： 最优路径为：9 5 10 6 7 1 3 4 2 8 每一代的最小距离收敛图为：01002003004005006007008009001000每一代种群最短距离的收敛过程遗传代数每一代种群最短距离最后得到的最优路径为：闭合曲线即为最优路径x对于30城市TSP问题，每一代个体数目为200，将其遗传代数取为10000，算法执行结果为：最优路径为：6 2 1 20 21 10 15 18 3 911 7 8 14 19 24 25 26 27 2829 16 17 22 23 30 12 13 4 5其每一代的最小距离的收敛图为：01000200030004000500060007000800090001000040050060070080090010001100每一代种群最短距离的收敛过程遗传代数每一代种群最短距离得到的最优路径为：01020304050607080901000102030405060708090100闭合曲线即为最优路径xy对于50城市TSP 问题，每一代的个体数目选取为200，遗传代数为20000，则算法执行结果为：最优路径为：35 16 1 3 14 7 9 11 8 5 13 17 18 12 10 19 20 21 22 42 43 44 2 6 24 4 50 49 48 40 31 30 29 28 23 36 38 39 47 27 37 15 34 33 32 46 45 25 26 41 每一代最小距离收敛图如下：00.20.40.60.81 1.2 1.4 1.6 1.82x 104每一代种群最短距离的收敛过程遗传代数每一代种群最短距离最后得到的优化路径为：10203040506070010203040506070闭合曲线即为最优路径xy在30城市TSP 问题中，得到的最终的优化距离为425.3，与实际的最小值423.471相差很少，在50城市TSP 问题中，得到的最终优化解为474.1，与实际的最优路线的最小距离427.855相差较大。
这是由于标准遗传算法的缺点所确定的，标准遗传算法在前期搜索的效果比较良好，算法后期搜索比较缓慢，从收敛图中可以验证这一点。