求解TSP问题的改进模拟退火遗传算法.pdf

442010，46（5）ComputerEngineeringandApplications计算机工程与应用

求解TSP问题的改进模拟退火遗传算法

王银年，葛洪伟
WANGYin-nian，GEHong-wei

江南大学信息工程学院，江苏无锡214122
SchoolofInformationEngineering，JiangnanUniversity，Wuxi，Jiangsu214122，China
E-mail：[e-mail]

WANGYin-nian，GEHong-wei.ImprovedsimulatedannealinggeneticalgorithmforsolvingTSPproblem.ComputerEn－
gineeringandApplications，2010，46（5）：44-47.

Abstract：TheTravelingSalesmanProblem（TSP）isawell-knownNPcompleteproblem，whiletheGeneticAlgorithm（GA）isone
oftheidealmethodsinsolvingit.Becausetheproblemisaspecialsequence，thegeneralcross-operatorintheproblemsolving
effectisnotideal.Thegreedycross-3PMoperatorisproposed，whiletheannealingselectionmethodisintroduced，andanewsi-
mulatedannealinggeneticalgorithmGCBSAGA（GreedCross-3PMBasedonSimulatedAnnealingGeneticAlgorithms）isformed.The
algorithmcombinessimulatedannealingandgeneticalgorithmtogether，makinggeneticalgorithmintheearlystageplayapower－
fulglobalsearchfunction.Itiseasytoconvergetotheglobaloptimumsolution；Inthelaterstage，thesimulatedannealinggenetic
algorithmsareusedtodealwiththeoverallsituationofpre-optimumsolution.Anditmakesfulluseofsimulatedannealing’s
latterpartofthepoweroflocalsearchandeventuallyconvergestotheglobaloptimalsolution.Aftertheexperimentaldataverifi－
cationprovidedbytheinternationallyrecognizedTSPLIB，GCBSABAinthecaseeil76，eil101，pr144，st70arefoundtoprovide
betteroptimalpathsolutionthanTSPLIB.
Keywords：TravelingSalesmanProblem（TSP）；geneticalgorithms；simulatedannealing；greedcross-operator；annealingchoice

摘要：巡回旅行商问题（TSP）是最典型的NP的难题，遗传算法（GA）是解决这类问题的有效方法之一。由于该问题的解是一种特
殊的序列，一般的交叉算子在该问题的求解效果方面并不理想，提出了贪心的3PM交叉算子，同时又引入退火选择方法，形成一
种新的模拟退火遗传算法GCBSAGA（GreedCross-3PMBasedonSimulatedAnnealingGeneticAlgorithms）。该算法还将模拟退火
算法与遗传算法相结合，使得遗传算法在前期发挥着全局搜索的强大功能，很容易收敛到全局较优解；后期用模拟退火算法来处
理遗传算法前期的全局较优解，充分利用模拟退火算法后期局部搜索的强大功能，最终收敛到全局最优解。经过国际公认的
TSPLIB提供的实验数据的验证，GCBSAGA在实例eil76、eil101、pr144、st70均找到了比TSPLIB提供的最优路径更优的解。
关键词：巡回旅行商问题；遗传算法；模拟退火算法；贪心交叉算子；退火选择
DOI：10.3778/j.issn.1002-8331.2010.05.014文章编号：1002－8331（