遗传算法求解TSP问题的实现与改进

1、遗传算法求解TSP问题的实现与改进摘要：旅行商问题(TravelingSalesmanProblem简称TSP)已经被证明为NP难题。通过应用遗传算法求解TSP问题，给出了遗传算法中各算子的实现方法，并用遗传算法(GeneticAlgorithm，简称GA)和穷举法分别求解了15个城市的TSP问题，结果表明，遗传算法具有明显的优越性。引入模拟退火的思想对遗传算法的变异算子进行改进，并求解了50个城市的TSP，得到了满意的结果。关键词：遗传算法；TSP；模拟退火0引言本文在分析遗传算法的基础之上求解TSP问题，并与穷举法所得结果进行比较。表明了遗传算法在求解此问题上的优越性。针对遗传算法的不足，

2、结合模拟退火思想对遗传算法进行改进，取得了理想的试验结果。1算法设计TSP问题的模型是简单而易于描述的。实际应用中，像印刷电路板工艺这样的应用可能是和模型比较接近的。但是模型中的城市之间的距离代表的是某个解的耗费，实际中不一定是欧氏距离，有可能点与点之间的耗费需要另外用权值给出。而且在实际中，两个城市之间的消耗不一定是对称的，例如乘船到另一城市和返回的费用可能是不同的。这里对TSP问题模型进行简化，在500X500的平面内随机生成了一些点，用它们来代表城市。假设每个城市和其它任意一个城市之间都以欧氏距离直接相连。遗传算法的总体框架遗传算法的简单通用的特点，主要是指其主要框架简单通用，可以说是万

3、变不离其中。其基本结构可以概括为：初始化种群；对种群每个个体进行评估；选择（竞争生存机会）；变化（重组、杂交与变异）；如不满足终止条件，转；否则结束。其中变化算子的设计是最重要的，既要考虑保留种群在演化中产生的好的基因，又不能使种群过早地局限于某个局部。其次是选择算子，选择策略意味着什么样的个体能够存活并参与繁殖下一代。如果参与繁殖的父体都很“好”，意味着种群里面的差异小，则很有可能会陷入局部最优。算法的详细设计解空间的表示方式遗传算法对解空间的表示大多采用二进制编码形式，但是二进制编码方式不适合TSP问题的解的表示，因为它要求特殊的修补算子来修复变化算子所产生的非法路径（即不可行路径）。给出

4、城市编号，用十进制数编码来表示解更合适，例如：近邻表示、次序表示和路径表示等等。这里采用了最简单的路径表示法。它是最自然、最接近人类思维的表示法。例如，有6个城市的TSP问题，可将6个城市从16编号，下面的路径（闭合的）：5宀1宀2宀4宀3宀6宀5表示从城市5出发，经过1，2，4，3，6最后回到城市5的一条路径，可以自然地用一维数组来表示：（5，1，2，4，3，6）相应地，50个城市的TSP问题，如果种群规模为500，解空间就用二维数组来表示：path50050。种群初始化种群的规模选择应适当，盲目的增大种群规模不能使算法得到改进，反而大大增加了计算的开销。例如，20个城市TSP与50个城市的

5、TSP问题，20个城市的TSP问题可以选择小规模的种群（例如500），而50个城市则要选大一些的种群（例如3000）。以20个城市为例，说明初始化种群的方法：种群初始化时，先产生1，2，,，20的一条规则路径，然后在这条路径中随机选两个数，将它们交换位置，这样做若干次（本文采用500次），保证这条路径变成了一条随机的路径。以这条随机路径为基础，对一些随机的位，做两两交换（做100次两两交换），这样产生了一个个体；同样地产生种群里其它的个体。适应度函数与最优解的保存用个体（一条闭合路径）的周长（平面欧氏距离）作为该个体的适应值。求得种群中所有个体的适应值后，将适应值最大的个体保存起来，到演化完毕

6、时，这个个体就是最后要求的解。选择（竞争）策略这里采用了轮盘选择策略。但是因为这是一个最小化问题，必须对适应值做相应调整以适应这种选择策略。可以采用一个映射对适应值进行规范：F二Fmax-F（1）其中，F是适应度函数求出的适应值，Fmax为其中的最大值，F是规范后的适应值。然后，用F来构造轮盘，概率为：Pi=Fi/刀Fi（2）表示了某一个体被选入下一代的概率。对P做逐级累加存入数组Pi：P0=0Pi=Pi-1+Fi（3）这个Pi正是构造好的轮盘。最后产生一个（0，1）之间的随机数r模拟轮盘转动，检查这个值落在Pi的哪个区段，如PkrPk+1，则选取个体k进入下一代。如此循环，保持种群的规模不变

7、。杂交算子杂交是希望不同的个体在产生下一代时，能够结合各自的优势基因，产生更好质量的下一代。在遗传算法里面，可以用单体杂交，双体杂交和多体杂交。但要保证种群的规模不变，须保证n个个体杂交产生n个后代，后代产生之后要代替其父体的位置。常用的杂交算子有PMX、OX、CX等，这几个算子细节见文献1。本试验实现了OX算子，采用了双体杂交，每次选两个个体杂交，产生两个后代。变异算子变异可以看作是外界对种群的影响。变异是为了引入新的因素，希望个体在外界的作用下，能够自我优化，产生好的基因。变异算子采用了简单的倒序变换，以8个城市为例，随机的产生两个小于8的整数，对某个个体进行分割，将分割段倒序并放回原来的

8、位置即可。（1，3，|4，6，5，2，8，|7）（1，3，|8，2，5，6，4，|7）由于这种变异算子仍能保持个体中的路径片段，即倒序前后这个切割段的路径是一样的，只是两端点与整个路径的连接颠倒了，这使得变异不是漫无边际，而是有所取舍的。这种简单反序可以保证后代仍然是一条合法途径。模拟退火的基本思想模拟退火算法来源于固体退火原理，将固体加温至充分高，再让其徐徐冷却。加温时，固体内部粒子随温升变为无序状，内能增大，而徐徐冷却时粒子渐趋有序，在每个温度都达到平衡态，最后在常温时达到基态，内能减为最小。在遗传算法中，引入模拟退火的思想，在变异算子中，让变异的父体和变异产生的后代之间竞争生存机会。在演

9、化的前期，种群的质量较差，因此给变异产生的后代较多的生存机会（从1向1/2递减），而随着演化向末期推进，将他们的生存机会减到平衡状态（各占1/2）。变异产生的后代的生存概率表示为：1-Gc/（2*Gt）（4）其中，Gt是遗传算法要演化的总代数，Gc是当前演化到第几代。这样，在初始时，Gc为0，后代获得的生存机会为1，类似于温度高、能量大；向后推进时，父辈与子女的生存机会差距逐渐减小；最后趋于平衡。算法的流程引入模拟退火思想对遗传算法进行改进，算法的流程如图1所示。2试验分析所有的试验在一台奔腾4（主频为2.4G）的WINDOWS平台的PC机上进行，这个算法计算量大（耗CPU）,但只占用较少的内

10、存。对于解的质量，首先使用15个城市的TSP问题进行分析。由于20个以上城市的TSP问题用穷举法在短时间内无法求得，因此这里选择了15个城市来做了穷举搜索的尝试。使用穷举搜索法（ExhaustiveSearchAlgorithm，简称ESA），15个城市的TSP问题用4m15s求得了最优解。如图2所示，长度是875.689149，解路径是：0，9，12，6，1，10，11，5，3，14，8，4，13，2，7。使用遗传算法来求15个城市的TSP,在几秒钟内就可以求得结果，而且得到最优解的概率也很大。图3为使用OX算子，种群规模500,演化600代，在1s内求得和穷举法同样的最优解的情形。解的路径

11、长度为875.689149，由于路径是闭合的环路，出发点在哪里不影响解的质量,所以这条路径和穷举搜索法求出的解是一样的。通过大量的试验观察还发现,最优解和较好的次优解在图形上均没有交叉的情形出现。当然，遗传算法并不能保证在1秒钟内总能求得最优解。但是通过增加演化代数（1000代）和增加种群规模（1000个），试验40次，每次耗时6s，40次均求得了最优解，而且演化到300代时已经取得了最优解的情形超过90%。可见遗传算法收敛速度快，而且能够一直向最优解逼近。采用OX杂交算子对50个城市的TSP问题的进行测试。种群规模选择4000，演化代数选择了10000。测试进行了5次，每次耗时约10m30s

12、,得到的结果分别为1709.7、1812.9、1744.1、1749.31766.0。从图形上看也还不是很理想，路径中会出现一个或二个交叉，图4所示是5次试验中最好的结果，长度为1709.7，路径中有一个交叉。使用模拟退火的思想对算法进行改进后，在同样的条件下进行了3次试验。每次耗时仍为10m30s左右，得到的结果分别为1680.31660.2、1672.3。从数值上看，得到了更优的解，从图形表现上看，3次试验所得路径都没有出现交叉，质量更好。图5所示是3个结果之一。3结语遗传算法的效率与变化算子和选择策略的设计有很大关系。好的杂交算子能够使后代尽可能保留父辈中的优秀的基因。而如果变异算子设计

13、得不好，又很容易使问题求解陷入解空间的某一局部。因此，必须仔细考虑各个算子的设计。只要设计出合适的算法，对于一些常规搜索算法无法或很难求解的问题，例如，像TSP这样的组合优化问题，遗传算法能够给出令人满意的次优解。遗传算法还可以和其它的智能搜索策略结合起来使用，可以加快求解过程或优化解的质量，本文使用模拟退火算法的思想对变异算子进行了改进，也是这方面的一个尝试。参考文献：ZBIGNIEWMICHALEWICZ，DAVIDB.FOGEL.如何求解问题现代启发式方法M.北京：中国水利水电出版社，2003.朱福喜，汤怡群，傅建明.人工智能原理M.武汉：武汉大学出版社，2002.FISCHETTIM.

14、，SALAZARJ.J.，TOTHP.BranchandcutalgorithmforthesymmetricgeneralizedtravelingsalesmanproblemJ.OperationsResearch，1997（3）.MERZP.AcomparisonofmimeticrecombinationoperatorsforthetravelingsalesmanproblemC.ProceedingsoftheGeneticandEvolutionaryComputationConference（GECCO），2002.JUNGS，MOONBR.Thenaturecrossoverforthe2DEuclideanTSPC.ProceedingsoftheG