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

摘 要：旅行商问题（Traveling Salesman Problem，简称TSP）已经被证明为NP难题。通过应用遗传算法求解TSP问题，给出了遗传算法中各算子的实现方法，并用遗传算法（Genetic Algorithm，简称GA）和穷举法分别求解了15个城市的TSP问题，结果表明，遗传算法具有明显的优越性。引入模拟退火的思想对遗传算法的变异算子进行改进，并求解了50个城市的TSP，得到了满意的结果。

关键词：遗传算法；TSP；模拟退火

中图分类号：TP312 文献标识码：A 文章编号：16727800（2013）002005503

0 引言

本文在分析遗传算法的基础之上求解TSP问题，并与穷举法所得结果进行比较。表明了遗传算法在求解此问题上的优越性。针对遗传算法的不足，结合模拟退火思想对遗传算法进行改进，取得了理想的试验结果。

1 算法设计

TSP问题的模型是简单而易于描述的。实际应用中，像印刷电路板工艺这样的应用可能是和模型比较接近的。但是模型中的城市之间的距离代表的是某个解的耗费，实际中不一定是欧氏距离，有可能点与点之间的耗费需要另外用权值给出。而且在实际中，两个城市之间的消耗不一定是对称的，例如乘船到另一城市和返回的费用可能是不同的。

这里对TSP问题模型进行简化，在500×500的平面内随机生成了一些点，用它们来代表城市。假设每个城市和其它任意一个城市之间都以欧氏距离直接相连。

1.1 遗传算法的总体框架

遗传算法的简单通用的特点，主要是指其主要框架简单通用，可以说是万变不离其中。其基本结构可以概括为：①初始化种群；②对种群每个个体进行评估；③选择（竞争生存机会）；④变化（重组、杂交与变异）；⑤如不满足终止条件，转②；否则结束。

其中变化算子的设计是最重要的，既要考虑保留种群在演化中产生的好的基因，又不能使种群过早地局限于某个局部。其次是选择算子，选择策略意味着什么样的个体能够存活并参与繁殖下一代。如果参与繁殖的父体都很“好”，意味着种群里面的差异小，则很有可能会陷入局部最优。

1.2 算法的详细设计

1.2.1 解空间的表示方式

遗传算法对解空间的表示大多采用二进制编码形式，但是二进制编码方式不适合TSP问题的解的表示，因为它要求特殊的修补算子来修复变化算子所产生的非法路径（即不可行路径）。给出城市编号，用十进制数编码来表示解更合适，例如：近邻表示、次序表示和路径表示等等。

这里采用了最简单的路径表示法。它是最自然、最接近人类思维的表示法。例如，有6个城市的TSP问题，可将6个城市从1～6编号，下面的路径（闭合的）：

5124365

表示从城市5出发，经过1，2，4，3，6最后回到城市5的一条路径，可以自然地用一维数组来表示：

（5， 1， 2， 4， 3， 6）

相应地，50个城市的TSP问题，如果种群规模为500，解空间就用二维数组来表示：path＼[500＼]＼[50＼]。

1.2.2 种群初始化

种群的规模选择应适当，盲目的增大种群规模不能使算法得到改进，反而大大增加了计算的开销。例如，20个城市TSP与50个城市的TSP问题，20个城市的TSP问题可以选择小规模的种群（例如500），而50个城市则要选大一些的种群（例如3 000）。

以20个城市为例，说明初始化种群的方法：种群初始化时，先产生1，2，…，20的一条规则路径，然后在这条路径中随机选两个数，将它们交换位置，这样做若干次（本文采用500次），保证这条路径变成了一条随机的路径。

以这条随机路径为基础，对一些随机的位，做两两交换（做100次两两交换），这样产生了一个个体；同样地产生种群里其它的个体。

1.2.3 适应度函数与最优解的保存

用个体（一条闭合路径）的周长（平面欧氏距离）作为该个体的适应值。求得种群中所有个体的适应值后，将适应值最大的个体保存起来，到演化完毕时，这个个体就是最后要求的解。

1.2.4 选择（竞争）策略

这里采用了选择策略。但是因为这是一个最小化问题，必须对适应值做相应调整以适应这种选择策略。可以采用一个映射对适应值进行规范：F′=Fmax-F

（1） 其中，F是适应度函数求出的适应值，Fmax为其中的最大值，F′是规范后的适应值。然后，用F′来构造，概率为：P＼[i＼]=F′＼[i＼]/∑F′＼[i＼]

（2） 表示了某一个体被选入下一代的概率。对P做逐级累加存入数组P＼[i＼]：P＼[0＼]=0

P＼[i＼]=P＼[i-1＼]+F′＼[i＼]

（3） 这个P＼[i＼]正是构造好的。最后产生一个（0，1）之间的随机数r模拟转动，检查这个值落在P＼[i＼]的哪个区段，如P＼[k＼]

1.2.5 杂交算子

杂交是希望不同的个体在产生下一代时，能够结合各自的优势基因，产生更好质量的下一代。在遗传算法里面，可以用单体杂交，双体杂交和多体杂交。但要保证种群的规模不变，须保证n个个体杂交产生n个后代，后代产生之后要代替其父体的位置。

常用的杂交算子有PMX、OX、CX等，这几个算子细节见文献＼[1＼]。本试验实现了OX算子，采用了双体杂交，每次选两个个体杂交，产生两个后代。

1.2.6 变异算子

变异可以看作是外界对种群的影响。变异是为了引入新的因素，希望个体在外界的作用下，能够自我优化，产生好的基因。

变异算子采用了简单的倒序变换，以8个城市为例，随机的产生两个小于8的整数，对某个个体进行分割，将分割段倒序并放回原来的位置即可。

（1，3，|4，6，5，2，8，|7）

（1，3，|8，2，5，6，4，|7）

由于这种变异算子仍能保持个体中的路径片段，即倒序前后这个切割段的路径是一样的，只是两端点与整个路径的连接颠倒了，这使得变异不是漫无边际，而是有所取舍的。这种简单反序可以保证后代仍然是一条合法途径。

1.2.7 模拟退火的基本思想

模拟退火算法来源于固体退火原理，将固体加温至充分高，再让其徐徐冷却。加温时，固体内部粒子随温升变为无序状，内能增大，而徐徐冷却时粒子渐趋有序，在每个温度都达到平衡态，最后在常温时达到基态，内能减为最小。在遗传算法中，引入模拟退火的思想，在变异算子中，让变异的父体和变异产生的后代之间竞争生存机会。在演化的前期，种群的质量较差，因此给变异产生的后代较多的生存机会（从1向1/2递减），而随着演化向末期推进，将他们的生存机会减到平衡状态（各占1/2）。

变异产生的后代的生存概率表示为：1-Gc/（2*Gt）

（4） 其中，Gt是遗传算法要演化的总代数，Gc是当前演化到第几代。这样，在初始时，Gc为0，后代获得的生存机会为1，类似于温度高、能量大；向后推进时，父辈与子女的生存机会差距逐渐减小；最后趋于平衡。

1.2.8 算法的流程

引入模拟退火思想对遗传算法进行改进，算法的流程如图1所示。

2 试验分析

所有的试验在一台奔腾4（主频为2.4G）的WINDOWS平台的PC机上进行，这个算法计算量大（耗CPU），但只占用较少的内存。

对于解的质量，首先使用15个城市的TSP问题进行分析。由于20个以上城市的TSP问题用穷举法在短时间内无法求得，因此这里选择了15个城市来做了穷举搜索的尝试。

使用穷举搜索法（Exhaustive Search Algorithm，简称ESA），15个城市的TSP问题用4m15s求得了最优解。如图2所示，长度是875.689 149，解路径是：0，9，12，6，1，10，11，5，3，14，8，4，13，2，7。

使用遗传算法来求15个城市的TSP，在几秒钟内就可以求得结果，而且得到最优解的概率也很大。图3为使用OX算子，种群规模500，演化600代，在1s内求得和穷举法同样的最优解的情形。解的路径长度为875.689 149，由于路径是闭合的环路，出发点在哪里不影响解的质量，所以这条路径和穷举搜索法求出的解是一样的。通过大量的试验观察还发现，最优解和较好的次优解在图形上均没有交叉的情形出现。

当然，遗传算法并不能保证在1秒钟内总能求得最优解。但是通过增加演化代数（1 000代）和增加种群规模（1 000个），试验40次，每次耗时6s，40次均求得了最优解，而且演化到300代时已经取得了最优解的情形超过90%。可见遗传算法收敛速度快，而且能够一直向最优解逼近。

采用OX杂交算子对50个城市的TSP问题的进行测试。种群规模选择4 000，演化代数选择了10 000。测试进行了5次，每次耗时约10m30s，得到的结果分别为1 709.7、1 812.9、1 744.1、1 749.3、1 766.0。从图形上看也还不是很理想，路径中会出现一个或二个交叉，图4所示是5次试验中最好的结果，长度为1 709.7，路径中有一个交叉。

使用模拟退火的思想对算法进行改进后，在同样的条件下进行了3次试验。每次耗时仍为10m30s左右，得到的结果分别为1 680.3、1 660.2、1 672.3。从数值上看，得到了更优的解，从图形表现上看，3次试验所得路径都没有出现交叉，质量更好。图5所示是3个结果之一。

3 结语

遗传算法的效率与变化算子和选择策略的设计有很大关系。好的杂交算子能够使后代尽可能保留父辈中的优秀的基因。而如果变异算子设计得不好，又很容易使问题求解陷入解空间的某一局部。因此，必须仔细考虑各个算子的设计。

只要设计出合适的算法，对于一些常规搜索算法无法或很难求解的问题，例如，像TSP这样的组合优化问题，遗传算法能够给出令人满意的次优解。遗传算法还可以和其它的智能搜索策略结合起来使用，可以加快求解过程或优化解的质量，本文使用模拟退火算法的思想对变异算子进行了改进，也是这方面的一个尝试。

参考文献：

＼[1＼] ZBIGNIEW MICHALEWICZ， DAVID B. FOGEL.如何求解问题――现代启发式方法＼[M＼].北京：中国水利水电出版社，2003.

＼[2＼] 朱福喜，汤怡群，傅建明.人工智能原理＼[M＼].武汉：武汉大学出版社，2002.

＼[3＼] FISCHETTI M.， SALAZAR J.J.， TOTH P. Branchandcut algorithm for the symmetric generalized traveling salesman problem＼[J＼]. Operations Research，1997（3）.

＼[4＼] MERZ P. A comparison of mimetic recombination operators for the traveling salesman problem＼[C＼]. Proceedings of the Genetic and Evolutionary Computation Conference （GECCO），2002.

＼[5＼] JUNG S， MOON BR. The nature crossover for the 2D Euclidean TSP＼[C＼]. Proceedings of the Genetic and Evolutionary Computation Conference （GECCO），2000.

＼[6＼] 吴斌，史忠植.一种基于蚁群算法的TSP问题分段求解算法＼[J＼].计算机学报，2001（12）.

＼[7＼] 朱亨荣，刘伟铭，宋丹.改进遗传算法求解TSP问题＼[J＼].株洲工学院学报，2004（2）.

＼[8＼] 王斌，李元香，王治.一种求解TSP问题的单亲遗传算法＼[J＼].计算机科学，2003（5）.

＼[9＼] 王霄.PCB数控钻孔最佳走刀路线的建模与求解＼[J＼].计算机应用与软件，2000（17）.