40 2010，46（29） Computer Engineering and Applications 计算机工程与应用 基于混合遗传模拟退火算法求解 TSP 问题 杜宗宗，刘国栋 DU Zong-zong，LIU Guo-dong 江南大学 通信与控制工程学院，江苏 无锡 214122 College of Communication and Control Engineering，Jiangnan University，Wuxi，Jiangsu 214122，China E-mail：duzongzong@163.com DU Zong-zong，LIU Guo-dong.Solution of TSP problem based on hybrid genetic simulated annealing algorithm.Computer Engineering and Applications，2010，46（29）：40-42. Abstract：TSP is a classical NP-hard combinatorial optimization problem.Genetic algorithm is a method for solving this prob- lem.But it is hard for genetic algorithm to find global optimization quickly and prevent premature convergence.This paper，in order to solve the problem，considers the characteristic of TSP，and puts forward a genetic simulated annealing algorithm，a hybrid of genetic and simulated annealing algorithm.In order to solve the inconsistency between diversity and convergent speed，this paper also adopts part greedy method to produce original population.The original population produced by this method is superior to the randomly produced original population.The simulation results demonstrate that，the proposed algo- rithm achieves considerable improvements，with respect to the basic genetic algorithm，in convergence speed，search quality and optimal solution output rate. Key words：hybrid genetic algorithm；simulated annealing algorithm；traveling salesman problem 摘 要：TSP 问题是典型的 NP-hard 组合优化问题，遗传算法是求解此类问题的一种方法，但它存在如何较快地找到全局最优解， 并防止“早熟”收敛的问题。针对上述问题并结合 TSP 问题的特点，提出将遗传算法与模拟退火算法相结合形成遗传模拟退火算 法。为了解决群体的多样性和收敛速度的矛盾，采用了部分近邻法来生成初始种群，生成的初始种群优于随机产生初始种群。 仿真实验结果证明，该算法相对于基本遗传算法的收敛速度、搜索质量和最优解输出概率方面有了明显的提高。 关键词：混合遗传算法；模拟退火算法；旅行商问题 DOI：10.3778/j.issn.1002-8331.2010.29.011 文章编号：1002-8331（2010）29-0040-03 文献标识码：Ａ 中图分类号：TP301.6 1 引言 旅行商问题（Traveling Salesman Problem，TSP）可描述 为：已知 N 个城市之间的相互距离，现有一推销员必须遍访这 N 个城市，并且每个城市只能访问一次，最后又必须返回出发 城市。如何安排他对这些城市的访问次序，使其旅行路线总 长度最短。旅行商问题是一个典型的组合优化路径规划问 题，其可能的路径数目是与城市数目 N 呈指数型增长的，一般 很难精确地求出其最优解，因而寻找其有效的近似求解算法 具有重要的理论意义。另一方面，很多实际应用问题，经过简 化处理后，均可化为旅行商问题，因而对旅行商问题求解方法 的研究具有重要的应用价值。 近年来，遗传算法由于它强大的优化能力已经被广泛应 用于 TSP 问题的求解中[1-3]。遗传算法就其本质而言是处理复 杂问题的一种鲁棒性强的启发式随机搜索方法。它是求解 TSP 问题的一种理想方法。遗传算法中一个较难解决的问题 是如何较快地找到最优解、保证全局收敛性、提高局部寻优能 力并防止“早熟”收敛问题。 将传统遗传算法[4]进行改进，运用一种基于混合遗传模拟 退火算法的路径规划方法可以有效解决上述问题。将基于启 发式知识的遗传算子的设计方法、运用模拟退火算法对遗传 算法进行优化的方法、采用了部分近邻法来生成初始种群应 用于 TSP 问题的求解中。仿真结果表明使用该方法可以达到 满意的规划效果和收敛速度，说明混合遗传模拟退火算法的 环境适应性较强。 2 混合遗传模拟退火算法 2.1 混合遗传模拟退火算法的基本思想 模拟退火算法是将退火思想引入组合优化领域，提出的 一种大规模组合优化问题的有效近似算法，该算法模仿固体 物质的退火过程。众所周知，高温物体降温时其内能随之下 降，如果降温过程充分缓慢，则在降温过程中物质体系始终处 于平衡状态，从而降到某一低温时其内能为最小。模仿退火 过程的寻优方法称为模拟退火算法。 遗传算法虽然能从概率的意义上以随机的方式寻求到全 作者简介：杜宗宗（1983-），男，硕士研究生，研究方向为机器人路径规划；刘国栋（1950-），男，教授，博导，研究方向为机器人控制、智能控制等。 收稿日期：2009-03-25 修回日期：2009-05-25 

杜宗宗，刘国栋：基于混合遗传模拟退火算法求解 TSP 问题 2010，46（29） 41 局最优解，但它在实际应用过程中也可能会产生一些问题。 这些问题中最主要的是局部寻优能力差、收敛速度较慢、易陷 入局部极值点等。而另一方面，模拟退火算法却具有较强的 局部搜索和摆脱局部最优点的能力。所以使用遗传算法与模 拟退火算法相结合的方法，是解决上述问题的有效途径。 由于遗传算法初始种群直接影响着收敛速度的快慢，所 以在不影响种群多样性的前提下，提出部分近邻法生成初始 种群。称这种将遗传算法与模拟退火算法相结合并采用部分 近邻法生成初始种群的算法称为混合遗传模拟退火算法。 2.2 编码方式 求解 TSP 问题的各种编码中，多数以遍历城市的次序排 列进行编码的，即整数编码[5-7]。这种方法简单、自然、容易理 解。如城市编号为[3，2，5，4，7，1，6，9，8]表示从 3 号城市出 发，经过 2、5、4、7、1、6、9、8 后，最终又回到了城市 3。随机生成 的个体都可能是问题的一个解。 2.3 适应度函数 TSP 问题的一个个体 X =[ v v 1 v 2 体所代表路径确切距离的倒数，也即 ] n 的适应度定义为个 fit = n - 1 å d( 1 ) i + 1 v v i + d( v ) v 1 n i = 1 为路径第 i 个顶点（城市），d( i ) v i 其中 v 且 d( 度函数最大化并认为使得该函数取得较大值的解为较优解。 2.4 初始种群生成方法 ，在后面的运行过程中，算法试图使适应 为两点间的距离，而 = d( v j v i ) ) v v v j j i ) i + 1 v v 1 v 2 表示城市 v 1 的距离，对所有的城市 v 1 产生初始种群的方法有两种，一种是完全随机的方法产生 的，它适用于对问题的解没有任何先验知识的情况；第二种是近 邻算法，设有 n 个城市的TSP问题，城市集合 X =[ ] v ， v n 1 d( ，将 到城市 v i + 1 其他的 n - 1 个城市按照与 v 的距离排序得到这些城市对 v 1 1 的近邻排序名次；把每一个城市的附近城市按邻近程度大小 从 大 到 小 排 列 好 放 在 一 个 二 维 数 组 中 ，命 名 为 neighbor[n][n - 1] 。从任意城市出发，每次选择尚未经过的城 市中对当前城市的近邻排名最前者作为下一个城市，直至遍 历所有 n 个城市，再返回出发点，这样就构成一个初始个体。 以每一个城市分别作为出发点，用这样的方法可以生成 n 个 初始个体。 用近邻算法生成的初始种群具有相当好的品质，但生成 的初始种群多样性很小，从这样的初始种群开始进化，不一定 能够收敛到全局最优解。 设计了混合算法生成初始群体即初始群体的一半个体是 随机产生，另一半个体是由先验知识近邻算法生成。这样可结 合具体问题，从问题中获取更多信息，从而使得算法更快更好找 到最优解。即由近邻算法产生 M/2 个初始个体，然后再随机 产生 M/2 个初始个体，得到一个种群规模为 M 的初始群体。 2.5 模拟退火算法的参数设置 2.5.1 初始温度的选取 通常初温 T 需要足够高，以确保算法从一开始就具有较 强的遍历性，避免陷入局部最优解；然而初温过高，又会大大 = kδ 的形 增加运行时间，降低运行效率[8]。初温的确定选择 T 0 0 max - fit 式，其中 k 为充分大的数，可以选 k =10，20，100 等试验值；δ = fit 为初始种群中最小的目标适应度值。 2.5.2 温度更新函数的选取 为初始种群中最大的目标适应度值，fit ，fit max min min 温度更新函数，即温度的下降方法，用于在外循环中修改 温度值。遗传算法的理论一般要求温度下降到零，整个系统 以概率 1 收敛到全局最优解[9]。本文采取的温度更新函数为： T(t) = T /(1 + αt) 。这种温度下降的特点是开始时，温度下降是 比较快的，越往后，降温速率较小，因此寻优重点在低温区。 式中 α 可以改善退火曲线形态。 2.5.3 算法的终止准则 0 采用零度法，即遗传模拟退火的最终温度为零，因而最为 简单的原则是：给定一个比较小的正实数 ε ，当温度 T £ ε 时， 算法停止。 2.6 遗传算子 2.6.1 选择算子 选择算子采用确定式采样选择的基本思想是按照一种确 定的方式来进行选择操作[10]，假设种群规模为 M ，其具体的操 作过程如下： 步骤 1 计算种群中各个个体在下一代种群中的期望生存 数目 = N i i (i = 12M ) Mfit å M fit i i = 1 其中 fit i 为每个个体的适应度。 的整数部分 [N i 步骤 2 用 N ] 确定各条对应个体在下一 代种群中的生存数目。其中 [x] 表示取不大于 x 的最大整数， 由该步共可确定出下一代中的 å ] 个个体。 [N M i i i = 1 步骤 3 按照 N i 的小数部分对个体进行降序，顺序取前 M M - å [N i = 1 ] 个个体加入到下一代群体中。至此可完全确定出 i 下一代种群中的 M 个个体。 2.6.2 交叉算子 应用遗传算法求解 TSP，通常把染色体表示成所有城市的 一个排列在这种表示方法下，传统的杂交算子产生的向量很 可能不是从头到尾的一个排列，即产生了无意义的路径。为 了排除这一情况，必须要定义保持编码有效性的杂交算子。 采用贪婪交叉算子，这种交叉算子可以使交叉后的子代 在保证可行性的同时，并很好地继承了父代的优秀基因，例 如：交叉的两个个体为： [3，2，5，4，7，1，6，9，8] [4，5，2，9，3，6，8，1，7] 先任意选定两个个体中第一个城市作为起始城市。假如 选择第一个个体中的城市 3 作为子代个体的起始城市。 根据 9 个城市之间 9×9 的距离矩阵，比较两个个体中 3 到 下一个城市的距离。即比较 3 与 2 和 3 与 6 的距离。不妨假设 3 与 2 的距离小于 3 与 6 的距离，那么子代染色体的第二个城市 即为 2。 同理，再根据距离矩阵比较 2 在两个个体中到下一个城市 的距离，距离较短的下一个城市即为第三个城市。 

42 2010，46（29） Computer Engineering and Applications 计算机工程与应用 如此反复直到个体结束，得出一个子代个体。再以另一 个个体的第一个基因作为起始基因，按照同样的办法得出另 外一个子代个体。 这种算子可以极大地加快算法的收敛速度，减小了交换 操作的盲目性，提高了算法的执行效率。 2.6.3 变异算子 采用启发式变异算子。假设变异的个体为：[1，2，3，4，5， 6，7，8，9]。 随机选择 3 个点，设 2，6，8 任意交换位置可以得到 5 个不 同个体： = p j 1, ì ï expæ í ï èç î fit(sj) - fit(cj) T fit(cj) £ fit(sj) , fit(cj) > fit(sj) ö ø÷ （4）由 2.6.3 节中定义的变异算子进行子代路径变异操作， (gen) 新个体，再以下面公式的概率 (gen) 。 (gen) 个体。最后得到变异退火之后的新种群 P 对第 i 个个体变异得到 P 接受 P mi m mi p(i Þ i′) = 1, ì ïï í exp ïï î æ çç è fit(i) - fit(i′) T ö ÷÷ ø fit(i′) £ fit(i) , fit(i′) > fit(i) 其中，i 为变异前状态，i′ 为变异后状态。 c m m 为 0.7，变异概率 p m c 步骤 5 操作流程结束。 lis 机制来接受和舍弃新解。 3 仿真实验结果及分析 因交叉操作是其主要操作，取 0.7 < p < 0.9 ，变异概率取 操作流程采取内外双层循环，模拟退火部分采用 Metorpo- < 0.2 。 0.01 < p 2.6.5 遗传算法终止代数 m 从中选择最好的作为新的个体。 2.6.4 遗传算子的参数选择 A1：[1，2，3，4，5，8，7，6，9] A2：[1，6，3，4，5，2，7，8，9] A3：[1，8，3，4，5，6，7，2，9] A4：[1，6，3，4，5，8，7，2，9] A5：[1，8，3，4，5，2，7，6，9] 大部分文献中仍需要指定最大终止进化代数，这使得算 法的鲁棒性质受到限制。若最大终止进化代数设定过小，算 法尚未收敛便已经终止，所得结果的品质就比较差；若最大终 止进化代数设定过大，算法己经收敛后仍要无意义地计算很 多代，浪费计算时间。为此，取消最大终止进化代数这一控制 参数，代之以最大容许停滞代数 Q ，当连续 Q 次迭代的最优解 没有改进时，迭代过程中止。 2.7 模拟退火算法操作流程 P(gen) = P T ，转向步骤 3；若满足终止条件，则转向步骤 5。 （5）比较相继两代的最优个体有无改善，若有改善，将停 滞代数计数器 tolerance 重置为 0，转到步骤 1；若无改善则， tolerance 置1，P(gen + 1) = P (gen) ，gen = gen + 1，转到步骤4。 步骤 4 温度终止条件判断。若不满足温度终止条件，则： (gen) ，gen = 0 ；按温度更新函数来更新温度参数 通过模拟 30 个城市地图情况下的计算机仿真来证明改进 算法的性能。在仿真中，算法相关参数设定如下：种群规模 M 为 100，染色体交叉概率 p 为 0.02，最大容 许停滞代数 Q 为 50，起始温度参数 k 为 100，温度更新参数 α 为 0.1，温度终止参数 ε 为 0.1。 针对 30 个城市实现 TSP 问题，假设 30 个城市的坐标为： {87，7；95，25；83，46；71，44；64，60；68，58；83，69；87，76；74， 87；71，71；58，69；54，62；51，67；31，84；41，94；5，91；7，64；22， 60；25，62；18，54；4，50；13，40；18，40；24，42；25，38；41，26； 45，21；44，35；58，15；62，32}，运用 Matlab7.0 仿真多次，种群进 化到 500 代、1 500 代时的典型结果分别如图 1 与图 2 所示。 【≮习 步骤 1 设置种群规模大小 M ；最大容许停滞代数 Q ；输 入城市的坐标数据。遗传代数计数器初始化：gen = 0 ；设置初 始温度参数 T = T ；生成初始种群 P(gen) ，种群中的每一个个 体 代 表 一 条 旅 行 商 所 走 的 路 径 ；初 始 化 停 滞 代 数 计 数 器 tolerance =0。 步骤 2 用近邻算法生成 M/2 个初始个体，再用随机法生 成另外 M/2 个初始个体。评价 P(gen) 中各条路径的适应值： fit ,fit 1 ，并计算城市间的距离矩阵。 2 步骤 3 对现有种群实施如下操作，直到产生出下一代新 （2）由 2.6.2 节中定义的交叉算子进行子代路径交叉操作： (gen) 交叉 （3）根据下面两个公式的接受概率 p (gen) 、P (gen) 、P P 退火之后的新种群 P (gen) 还是拒绝 P (gen) 。 (gen) 中第 i 个个体 P (gen) 和 P 由 P 得到新个体 P 的适应度函数值。 （1）由 2.6.1 节中定义的选择算子从父代路径中进行子代 (gen) 和第 j 个个体 P si (gen) ，并计算 P 和 p 来确定是接受 i (gen) ，最后得到交叉 j 路径选择操作：P (gen) ¬ selection[P(gen)] 。 100 90 80 70 60 50 40 30 20 10 0 100 90 80 70 60 50 40 30 20 10 0 10 20 30 40 50 60 70 80 90 100 图 1 进化代数为 500 时的路径 (gen) 和 P (gen) cj ci fit(ci) £ fit(si) ,,fit M 0 s ci cj ci cj 的种群： ci cj / m 度 长 / m 度 长 长度/m s sj = p i 1, ì ï expæ í ï èç î c T fit(si) - fit(ci) ö ø÷ , fit(ci) > fit(si) 10 20 30 40 50 60 70 80 90 100 长度/m 图 2 进化代数为 1 500 时的路径 （下转 46 页） 

46 2010，46(29) ComputerEngineeringandApplications计算机工程与应用 对于典型实例，Two—stage Inver-over EA和GT算法的计 算结果如表l所示，表l中一卯，表示30次计算得到已知最优解 参考文献： 【l】Lawer E，L咖J，Ronnooy K A，et a1．The traveling salesman 的次数，f表示30次计算平均运行时间(ms)，偏差盯的计算公 式为： ∑(s一‰) 揣2≈而：=_×100％ (4) 其中，T为独立实验次数，Si为每次实验得到的最优解路径长度， 咒。为已知最砌酾鞘圣长度。可以看出，Two．stage Inver-ovcr EA 在求解质gt上和运行时间上相对于GT算法有明显优势。 表1 Two·stage lnver-ovc[EA和GT霸【i去在爨旺型实饲t：自嫩膏《1生能比较 5小结 对Invcr-over算子进行了改进，提出了1％Illvcr-ovcT算子 和2u-Inver-over算子，实现了基于改进Inver-over算子的二阶 段演化算法，实验结果表明本文提出的算法有较好的计算性 能。下一步的主要研究工作是：(1)研究算法参数对算法性能 的影响，寻找各参数与求解问题之间的联系，设计出适合于 求解问题的参数；(2)设计效率更高的基因库来指导改进 Inver-over算子和初始种群的产生。 problem[M]．New York：Wiley-Imemational Pubficafion，1985． 【2】C'Ⅲcy M R，Johnson D S．Computc'rs and incacmbility：A guide to the theory of NP-completeness[M]．San Francisco：Freeman W H， 1979． [3】Clarke G，Wright J W．Scheduling of vehicles from a central de- pot to a number of delivery poin捃[J]．Operations Research，1964。 12：568．581． [4】Christofides N．Worst．．ca∞analysis of a咖hfur碰c for the tray- eling salesman problem，Technical Report No．388[R]．Pittsburgh， PA：Graduate School of Industrial Administration，Carnegie Mel· lon University，1976． 【5】K．irkpatrick S，Gelatt C D，Vecchi M P．Optimization by simulated anuealing[J]．Science，1983。220(4598)：671-680． [6]Guo T，Michalewicz Z．[nvor-ovo[openaor for the TSP[C]／／LNCS 1498：Proceedings of the 5th International Confe础nce oll Paral- lel Problem Solving from Nature Conf．Bcrlin：Spriager-Verlag， 1998：803．812． [7】Reinelt G．TsPLm—-A traveling salesman problem library[J]．OR- SA Journal on Computing，1991，3(4)：376—384． 【8】谢大同，李程俊，康立山．基于改进Inver-over算子的并行TSP演化 算法[J】．计算机工程与{殳计，2007，28(10)：2248．2249． 【9】杨辉，康立山，陈毓屏．一种基于构建基因库求解TSP问题的遗传 算法fJ]计算机学报，2003，26(12)：1753．1757． [10】卿．1ll轩，康立山，陈毓屏．基于基因库求解TSP的改进的反序．杂 交算法[J】计算机工程与应用，2005，41(7)：37．39． [11】江雷，陈贤富．一种衡量TSP问题种群多样性的新方法明．微电子 学与计算机，2004，21(8)：10-12． (上接42页) 参考文献： 用标准遗传算法与本文所采用的混合遗传模拟退火算法 【l】刘金琨．机器人控制系统的设计与MATLAB仿真[M】．北京：清华大 相比较，统计结果如表1、表2所示。 学出版社，2008． 表l成功率对比表(％) 表2路径长度对比表 图1 图2 丽酾画——汀——百 改进算法 91 94 图I 图2 标准算法 528．536 8 441．798 4 改进算法 487．040 8 412．372 5 4结束语 介绍了一种基于混合遗传模拟退火算法的TSP问题求解 方法。为了适应机器人的路径规划，采用了局部搜索能力较 强的模拟退火算法对遗传算法进行优化。从而避免了传统遗 传算法收敛较慢、局部寻优能力差、易陷入局部极值点、容易 “早熟”等缺点，使得遗传算法和模拟退火算法在路径规划中 达到优势互补的目的。为了初始种群在保持多样性的同时提 高遗传进化的收敛速度，采用了部分近邻法来生成初始种 群。在仿真结果中，搜索最优路径的成功率都高于标准算法， 体现了该算法对地图较好的适应能力。在种群规模较大且进 化代数充足的情况下，混合遗传模拟退火算法的成功率更高、 路径总长度更短。仿真结果表明相比一般的遗传算法，使用 这种混合遗传模拟退火算法可以达到满意的规划效果和收敛 速度。 【21 Tu J，Yang S．Genetic algorithm based path plann／ng for a mobile robot[C]／／Proceedings of IEEE Intelligem Conference on Robot- ics and Automation，Taiwan，2003：1221．1226． 【3】Zhang Wcn-dong，Bai Yah-ping．A hybrid elastic net method for solvmg the traveling salesman problem[J]．International of Software Engineering and Knowledge Engineering，2005，15(2)：447-453． 【4】Whifley D．Scheduling problems and traveling galcslmqn：The ge- nctic edge recombination operator[C]／／Proeeedings of 3rd national Conference on Genetic Algorithms，US，1989：133—140． Inter- 【5J文Ⅱ海，郝志峰，林智勇敢进遗传交叉算子求解TSP问题川．华南理 工大学学报，2002，30(12)：71．73． 【6]李艳萍，张挺．一种求解TsP问题的新型遗传算法明．太原理工大学 学报．2008．39(3)：268．271． 【7]彭丹平，林志毅，王江晴．求解TSP的一种改进遗传算法叨．计算机 工程与应用，2006，42(13)：91．93． 【8]黄席樾，蒋卓强．基于遗传模拟退火算法的静态路径规划研究田． 重庆工学院学报，2007，21(6)：53—57． 【9]薛宏智．遗传算法在TSP上的应用及改进【D】．西安：长安大学，2006． [10】孙秀云．移动机器人的路径规划及其运动控制器的研究【D】济南： 山东大学，2005．