求解TSP问题的锦标赛选择模拟退火算法.pdf

求解TSP问题的锦标赛选择模拟退火算法木2求解TSP问题的模拟退火算法l引言幻甜儿P馏叻(s)=∑饥J刚][Jp+l】】+饥s【Ⅳ]】[s[1】]蔡荣英钟一文幽摘要：模拟退火算法是一种典型的智能优化算法，它的一个主要缺点是收敛速度慢。针对这一问题，提出了一种基于锦标赛选择策略的求解旅行商问题的模拟退火算法，在从邻域中选择候选解时，随机产生两种方案，根据领域的启发式信息，从中选择一种好的方案去生成候选解。仿真结果表明，锦标赛选择模拟退火算法明显优于传统的模拟退火算法。关键词：模拟退火算法锦标赛选择旅行商问题(1)福建农林大学计算机与信息学院，福建福州350002模拟退火(simulatedAnnealing，SA)算法是一种典型的智能优化方法，SA算法的思想最早是由Me仃opolis等11】提出的，SA算法依据Metropolis准则接受新解，因此，除接受优质解外，还在一定范围内接受劣质解，使SA算法具有从局部最优解中逃逸的能力。SA算法在开始时温度f值较大，可以接受较差的劣质解，随着f值的减小，只能接受较好的劣质解，最后在，值趋于零时，就不再接受任何劣质解了。这就使SA算法既可以从局部最优的“陷阱”中跳出，从而有可能求得优化问题的全局最优解，同时又不失简单性和通用性，因此SA算法在许多领域都得到了很好的应用，比如在VLSI、生产调度、控制工程、机器学习、神经网络、图像处理等领域。在使用sA算法的过程中也发现，尽管从理论上证明了sA算法能收敛到全局最优解，但其收敛速度较慢，与此相反，启发式算法通常基于某种贪婪策略，有较快的收敛速度，但易于陷入局部最优解，那么，能否在SA算法中嵌入一定的贪婪策略，在保持其全局寻优的前提下，加快SA算法的收敛速度昵?基于这个思想，针对旅行商问题(TraVelingProblem，TSP)，本文研究了在从当fj{『解的邻域结构中产生下一个解时，使用锦标赛选择策略来提高获取优质解的概率，从而提高SA算法的总体性能，仿真表明，这种策略是有效的。TSP是一个典型的NP一困难的组合优化问题。假设有一个推销员必须遍历Ⅳ个城市，每个城市必须且只能访问一次，最后返回到出发城市，TSP问题就是要找到访问这些城市的顺序，使旅行线路的总长度最短。对一个包含Ⅳ个城市的TsP问题，可以用一个Ⅳ×Ⅳ的二维数组d来存储城市间的距离，其中每个元素研司D1表示城市f和，之间的距离，用一个包含Ⅳ个元素的一维数组s来存储推销员访问城市的顺序，其中每个元素s[司表示第f个访问的城市，求解TsP问题的目标就是要找到某个城市访问顺序s，使其路径长度最小，即最小化：’基金资助：福建省青年入彳。科技创新幕金(2006F3013)，福建省自然科学基金(2008J0316)．作者简介：集荣英(1969．)，女，福建南半人，高级教师，从事运筹与优化，智能优化的研究；钟一文，男，教授，博士；电话：[phone]：E—mail；[e-mail]
如果fo“儿删(啪<fD“吐绷g珐O)否则，如果exp【一(fD砒印g曲国)一fD材儿删已O))／嘲r锄dom【o，l】式中‰是其他城市到城市s阴的最大距离。3锦标赛选择策略p，=(4。。一dp[f】][s[／】】)／∑(吐。双一dp【f]】【s【七]】)生成一个二维的排名表翮七，其中阳聍粗司D．]】表示城市／到城市f的距离在所有到城市f的城市的排名，排胁”儿已，咖如)表示由解s所对应的路径长度。产生新的候选解町=缈明魄和)；退温“J=砒，缎d哟；／触，c憎盘￡P是退温函数B=饥s[(f—l+Ⅳ)％Ⅳ】】[s[棚／幻甜儿P馏叻0)|生文献中对求解TSP问题的模拟退火算法的研究多集中在相关参数的设置上，特别是对邻域结构及其大后，上述文献基本上都是采用等概率的方式从邻域中随机产生下一个候选解，文献[5】提出了一个基于领域在选择插入位置时，使路径中相邻城市之间的距离大的两个城市以较大的概率被选取，在它们之间插(2)假设已经选定在位置f插入，选择插入的城市时，使距离城市s阴近的城市以较大的概率选为下一个访(3)仿真结果表明，上述比例选择策略的使用能有效地提高SA算法的性能15】，但上述方式存在以下不足：图l是求解TSP问题的基本SA算法，其中函数g绷e阳把(s)表示从当前解s产生一个候选解，函数小的研究。文献【2．4]研究了不同邻域结构的大小对sA算法性能的影响，文献【5．7】研究了不同的邻域结构(不同形式的逆转邻域、插入邻域和交换邻域及它们的混合)对sA算法性能的影响。当确定了邻域结构知识的启发式方式，其基本思想是在插入邻域中选择插入位置和插入城市时，根据TSP问题中边的信息，使用比例选择策略，优先破坏长的边，优先插入短的边：入其他城市，即选择位置f为插入点的概率为：问点，