第26卷第5期 计算机仿真 2009年5月 文章编号：1006—9348(2009)05一0205一04 基于一种改进遗传模拟退火算法的TSP求解 乔彦平，张骏 (西北工业大学自动化学院，陕西西安7100r72) 摘要：快速收敛于全局最优解是遗传算法的一个研究重点。在对遗传算法和模拟退火算法研究的基础上，分析了两种算法 各自的优缺点，对已有的遗传模拟退火算法进行_r改进。结合遗传算法和模拟退火算法的优点，给出r一种并行的多层搜 索结构，提高了算法的效率；同时，在此基础上，提出一种种群早熟评价指标。最后，将此改进算法应用到旅行商问题l||，并 分别对10个城市和30个城市的旅行商问题进行了仿真，用于验证算法的可行性和快速性。仿真结果表明。改进的遗传模 拟退火算法能够较快的收敛于全局最优解。 关键词：遗传算法；模拟退火算法；旅行商问题；过早收敛 中图分类号：TPl8 022 文献标识码：B Traveling Salesman Problem Solving Based on an Improved Genetic Simulated Annealing Algorithm QIAO Yan—ping，ZHANG Jun (College of Automation，Northwestern Polytechnical University， Xi’all Shanxi 710072，China) in the global optimal solution is a focus of genetic algorithm．Based on the study of ABSTRACT：Rapid convergence genetic algorithm and simulated annealing algorithm，the paper analyses the major merits and shortcomings of the two algorithms，and gives an improved genetic simulated annealing algorithm，which combines the major merits of the two algorithms．Especially，it gives a parallel searching structure of multi layers，and gives a new criterion for judging the premature convergence in this improved algorithm．At last，the algorithm is applied in the traveling salesman problem (TSP)，and it is simulated with both of 10一city TSP and 30一city TSP to prove the algorithm’S feasibility and effi— ciency．The results of the simulation indicate that the improved algorithm has a rapid convergence in the global opti— mal solution． KEYWORDS：Genetic algorithm；Simulated anneMing algorithm；Traveling salesman problem(TSP)；Premature convergence 1 引言 法被广泛地用于求解TSP问题，其中GA是比较成功也是受 旅行商问题(Traveling Salesman Problem，TSP)是一个具 关注较多的一种算法心】。但是，对于TSP这样的NP难问 有广泛应用背景和重要理论意义的组合优化问题，同时，旅 题，单一机制的优化算法很难实现全局优化，且效率也较低。 行商问题是一个典型的NP难问题…。TSP问题可以描述 多种优化机制的相互结合，是能较大程度提高全局优化能力 为：给定一个城市的集合，寻找一条从某一个城市出发，然后 遍历其他各个城市，且每个城市能且仅能经过一次，最后回 到出发城市的最短路径。 TSP问题模型在如路径规划等实际问题中有着十分广 泛地应用，因此，对于TsP问题的求解长期受到许多领域的 研究人员的关注。目前，遗传算法(Genetic Algorithm，GA)、 模拟退火算法(Simulated Annealing Algorithm，SA)等优化算 收稿日期：2008—04—14修回日期：2008—04—29 的有效途径之一。 遗传算法是模拟自然界生物优胜劣汰、适者生存的自然 遗传法则的一种优化算法。虽然GA有较强的全局搜索能 力，但是它在实际应用中过分依赖于种群的多样性，并容易 产生过早收敛的现象，而且在后期搜索效率降低。SA算法 起源于统计方法，首次被Kirkpatric【31等引人到优化问题中。 sA有较强的局部搜索能力，但是对参数有较强的依赖性H1。 本文综合GA和sA的特点，对已有的混合遗传算法做 了改进，首先，针对遗传算法虽然把握搜索过程的总体的能 ．．．——205．．．—— ˝ • ‰ ˚ 

力强，但其局部搜索能力较弱的特点，利用SA较强的局部搜 “早熟”现象，提高算法的寻优效率。在搜索进程上，首先在 索能力来对种群进行优化；其次，引入一种新的早熟评价准 一定温度下对种群进行交叉和变异操作，产生的种群P。(t) 则，对于早熟的个体，利用SA在搜索过程中能随机接受劣化 作为sA退火操作的初始种群，经过Metropolis接受准则得到 解的能力，对它们采用模拟退火交叉变异操作进行进化，产 生新的个体；同时，结合最优保存策略，形成一种改进的遗传 新的种群P2(t)。设种群规模为L，则由GA和sA分别产生的 种群P，(t)、P2(f)组成的种群规模为2L，对该种群进行选择 模拟退火算法(Improved Genetic and Simulated Annealing AI． 操作，选择复制其中的L个个体作为新的种群P3(t)，通过早 gorithm，IGSA)。 2 TSP问题模型 熟判断，对早熟种群进行模拟退火交叉、变异操作，对非早熟 种群进行传统遗传操作，产生的种群P(t+1)作为下一代进 化的初始种群。同时，在算法种引入最优保存策略。 髑P模型㈨的数学描述为：给定点的集合P={l，2，…， 2)早熟评价指标 n}，以及n个点两两之间的距离集合D={dFf，i,j=1，…， 本文根据已有的遗传算法种群多样性评价指标，并结合 凡。问题求解的目标是要找出一个包含所有n个点，且每个点 上述的算法在搜索进程上的特点，给出一种早熟评价指标。 只经过一次的最小回路。数学模型如下： min∑∑d#％ i；l，=I “t∑～=1，i=1，…，，l； J；1 ∑％=1√=1，…，rt； f=l ∑茗F≤I S l一1，对所有P的真子集S JES ％=[0，1]，i=1，…，n；j。=1，…，／／, (2) (3) (4) 3 改进的遗传模拟退火算法 3．1 遗传算法 如前所述，设种群P。(t)的平均适应度为^。彳一为 P。(t)中个体的最大适应度；同样五。以。。为种群P2(t)的平 均适应度和最大适应度以。以一为种群P3(t)的平均适应 度和最大适应度。然后，分别定义△。=工一一五。，△：=正一一 厶，A3=六一一五。，令A=(△1+△2+△3)／3。则，当△小于 一定数值的时候，就认为遗传出现了“早熟”现象。在这里当 △小于某一定数值时则说明种群的适应度趋于相似化，种群 的多样性能下降，出现“早熟”现象。 3)“早熟”现象的处理办法 根据以上给出的早熟评价指标，当种群出现“早熟”现象 时，需要对此进行处理。处理的原则就是尽可能的提高种群 多样性，引入变异个体，使搜索跳出局部最优区域。但是，也 遗传算法最早由John Holland在上世纪的七十年代提 不能通过一味地提高变异概率来达到此目的，因为，这样可 出，它是模拟生物进化过程而形成的全局搜索算法。遗传算 能引入过多劣质个体，降低算法的效率。在此，利用3．2节 法的基本思想是利用某种编码技术对个体进行编码，然后对 由多个个体组成的种群进行选择、交叉、变异操作，通过寻求 分析所得的模拟退火算法在搜索过程中能随机接受某些劣 化解的特点，采用模拟退火交叉和变异来处理种群的“早熟” 种群进化过程中的最优个体，得到所求解问题的最优解旧J。 现象H J。 传统遗传算法最为严蘑的问题是“早熟”问题。由于种 3．4算法描述 群规模是有限的，经过遗传操作以后，再按照适应度的规则 根据以上的分析，给出改进算法的实现步骤： 进行选择，使得高于平均适应度的个体大概率的被选入下一 Stepl设置编码长度，种群规模，初始温度，冷却参数，进 代，这样不断地进化，当某些个体在种群中占有一定优势时， 化代数等； 遗传算法会强化这种优势，使得搜索范围变窄，出现“早熟”。 Step2进行代数计数器初始化，t=0； 究其原因t要是：选择复制的种群在经过固定交叉概率和变 异概率的进化以后不能很好的保证种群的多样性。 3．2模拟退火算法 Step3随机产生初始群体P(t)； Step4计算P(t)中个体的适应度，进行最优个体保存； step5对群体P(t)进行交叉、变异操作，得到新的群体 模拟退火算法的概念最初是为研究组合优化问题而提 Pl(t)； 出的。通过设定初始温度和初态，伴随温度的下降，结合概率 step6采用模拟退火规则产生新的种群P2(t)； 突变型在解空间中进行随机搜索，获得最优解。在搜索过程 Step7个体的选择复制操作，P3(t)=Re—Produce[P 中，sA算法利用Metropolis准则，可以选取两种新方案：一是 优于原方案的新方案；二是虽然次于原方案，但目标函数比 较接近原方案的新方案，即新方案的整体水平优于原方案。 可见。SA有随机接受劣化解的能力。 3．3 改进的遗传模拟退火算法 1)在搜索结构上，改变传统的遗传模拟退火算法的两 层并行搜索结构，为了更好的保持进化种群的多样性和避免 ．．．——206．．．—— (t)，P2(t)]； Step8计算种群P3(t)的适应度，根据早熟判别标准，针 对非早熟和早熟情况分别用传统遗传操作和模拟退火操作 产生新的种群P(t+1)； ste汐终止条件判断，若不满足终止条件，则t=t+l，转 step4，继续进化过程，否则，输出当前最优个体，算法结束。 ˝ • ‰ ˚ 

4仿真实验 为了验证改进的遗传模拟退火算法能快速收敛于全局 最优的特性，参照有关文献给出30个点作为仿真研究对象。 这30个点分别代表30个城市。它们在平面内的坐标如表 1 o 表1仿真数据 9—10—4—2—1；运行时间：O．8337。 量优路径 X 图2基于IGSA的lO个城市的最优路径 最优路径长度：1．6737；最优路径：1—6…9 7 8—10 —5—4—2—3一l；运行时间：O．2888。 4．2实验二仿真结果 仿真实验分两次进行，第一次取仿真数据表的前10组 数据作为仿真数据，分别采用遗传算法和改进的遗传模拟退 火算法求解，得到的最优路径分别如图l、图2所示。第二次 实验针对所给的30组数据进行仿真，得到的最优路径分别 如图3、图4所示。 4，1实验一仿真结果 量优路径 图3基于GA的加个城市的最优路径 最优路径长度：4．115l；最优路径：I一7—9—11—6—15 —17—16—20—22—24—26—28—25—21—23—27—29—18 一19一14一12一13—10一8—5—4—2—30—3—1；运行时间： 6．0784。 最优路径长度：4．1151；最优路径：l一7—9—11—6—15 一17一16—20—22—24—26—28—25—21—23—27—29—18 一19—14—12一13—10—8—5—4—2—30一3—1；运行时间： 5．0164。 4．3实验结果分析 表2仿真结果比较 圈1基于GA的10个城市的最优路径 最优路径长度：1．6737；最优路径：1—6—7…5 8 3— ·--——207---—— ˝ • ‰ ˚ 

5结论 本文对已有的遗传模拟退火算法进行了改进，采用多层 并行搜索结构，并给出了一种早熟评价指标。最后将算法用 于求解TSP问题，能够较快的收敛的全局最优解。但是，对 于算法的理论分析以及在求解大规模TSP问题方面还有待 于进一步解决。 参考文献： [1]韩丽霞，王宇平．解旅行商问题的一个新的遗传算法[J]．系 统工程理论与实践，2007，12：145—150 [2]刘军，王介生．旅行商问题(TSP)的伪并行遗传算法[J]．控制 图4基于IGSA的-30个城市的最优路径 理论与应用，2007，24(2)：279—282． 对于TSP问题而言，寻求一种优化算法的目的就是要通 过这种算法能够快速准确地找到问题的最优解。但是，在一 般情况下算法的“快速收敛”和“全局最优”是一对矛盾体。 GA要保证算法的全局最优性就要保持种群个体的多样性， 以避免算法进入局部最小，而这是以牺牲快速性为代价的； 同样，要使得算法能够快速收敛，就希望算法快速的朝着最 优状态转移，这就降低了个体的多样性，导致算法出现甲．熟 现象。 文中的改进遗传模拟退火算法，结合了SA算法较强的 局部搜索特性，采用多层并行搜索结构提高了算法的收敛速 度，同时，又结合了一种抑制早熟的处理办法，使算法避免陷 入局部最优。从表2的仿真结果数据可以看出，对于求解中 小规模的TSP问题，该改进的遗传模拟退火算法较好地解决 了GA中快速收敛和全局最优的矛盾问题，算法以较快的速 度收敛于全局最优解，取得r预期的效果。 [3] S Kirkpatriek，C D Gelatt，Jr．M P Vecehi．Optimization by Simu- lated Annealing[J]．Science，1983，220：671～689． [4] 高海昌，冯博琴，朱利．智能优化算法求解TsP问题[J]．控制 与决策。2006。21(3)：241—252． [5] 吴值民，等．退火单亲遗传算法求解旅行商问题及MATLAB实 现[J]．解放军理工大学学报，2007，8(1)：44—48． [6]王蕾，沈庭芳，招扬．一种改进的自适应遗传算法[J]．系统工 程与电子技术，2002，24(5)：75—78． [7] 梁霞．一种改进的自适应遗传算法及其在车间调度中的应用 [D]．大连：大连交通大学硕士学位论文，2006． [作者简介] 乔彦平(1984一)，男(汉族)，陕西榆林人，西北工 、池大学自动化学院硕士研究生，研究方向：自主任务 规划与调度方法研究； 张骏(1964一)，男(汉族)，I』J东枣庄人，西北工 业大学自动化学院教授，博上生导师，研究方向：复 杂控制、智能控制等。 (上接第197页) 从仿真结果和实时控制可见，最优模糊PID控制方法 具有很好控制效果，有效地解决经典PID控制方法中控制参 数整定困难及整定不准的问题。ter$adaptive method[J]·Fuzzy Sets and Systems，1996· 【J]．Fuzzy Sets and Systems，1993． [4]W Z Qiao and M Mizumoto．PID type fuzzy controller and pmalm! 参考文献： [1]张磊．最优模糊推理方法及其在智能控制中的应用[D]．北京 航空航天大学博士论文，2005． [2]J Carvajal，G Chen and H Ogmen．Fuzzy PID controller：design， performance evaluation and stability analysis[J]．Information Sci． erlces，2000． [3]s zHe，STanand PZWang．Fuzzy self—tuning ofPID controller [作者简介】 牟永欣(1969．1l一)，男(汉族)，北京市人，工程 师，主要从事锅炉管道、空调系统、智能大厦工程等 研究。 —--——208·-——— ˝ • ‰ ˚