遗传算法和模拟退火算法求解TSP的性能分析.pdf

第9卷91年第11月期计算机技术与发展V01．19,No．1J
200O0口PI玎ERTEamD(ANDDEVELDPMENTNOV．2009

遗传算法和模拟退火算法求解TSP的性能分析

汪松泉，程家兴2
(1．安徽大学计算机科学与技术学院，安徽合肥230039；
2．安徽大学计算智能与信号处理教育部重点实验室。安徽合肥230039)

摘要：旅行商问题(TravelingSalesmanProblem，)是一个典型的组合优化问题，并且是一个NP难题，其可能的路径总
数与城市数目是呈指数型增长的，所以一般很难精确地求出其最优解，因而寻找出有效的近似求解算法就具有重要的意
义。目前求解TSP问题的主要方法有模拟退火算法(SimulatedAnnealing，SA)、遗传算法(GeneticAlgorithm，GA)和神经网
络算法等。GA是模拟生物在自然环境中的遗传和进化过程而形成的一种自适应的全局优化概率搜索算法。SA算法用
于优化问题的出发点是基于物理中固体物质的退火过程与一般优化问题的相似性。文中将提出遗传算法和模拟退火算
法求解TSP问题，通过试验比较两者求解TSP问题的性能，结果表明GA的性能要优于SA的性能。
关键词：遗传算法；模拟退火算法；TSP
中图分类号：1P301．6文献标识码：A文章编号：1673—629X(2Oo9)1l一0097—04

PerformanceAnalysisonSolvingProblemofTSPbyGenetic

AlgorithmandSimulatedAnnealing

WANGSong．quan，CHENGJia-xing2

(1．SchoolofComputerScienceandTechnologyinAnhuiUniversity，Hefei230039，China；
2．MinistryofEdu．KeyLab．ofIntelligentComputing&SignalProcessing，AnhuiUniv．，Hefei230039，China)

Abstract：TSPisatypicalcombinationoptimizationproblem，whichisalsoanNPhard—problem．Itssizeisincreasedbyexponentialn．
So，itishardtofindaprecisionresult，anditisvimportanttosearchforthene氆rresdt．Currently，themainmethodofsolvingTSPhas

GA，SAandtheneuralnetworkalgorithm．GAisasimulationofthenat~alenvironmentinthebiogeneticandevolutionaryproces~ofthe

formationofanadaptivesearchalgorithmforglobaloptimizationprobability．SAsolvesoptimizationproblem，whichthestartingpointis

bE【sedonthephysicsoftheannealingprocessofsolidswiththegeneralsimilarityofoptimizationproblems．Proposedtwoeffectivemeth—

ods：geneticalgorithmandsimulatedannealing．throughtheexperiment，comparethetwoper~onrmneeanalysis．thercsuls~,howthatthe

GA’sperformanceissuperiortOtheperformanceofSA．

Keywords：geneticalgorithm；simtflatedannealing；travelingzalemaanproblem

O引言具有重要的应用价值【。
TSP(TravelingSalesmanProblem)问题是一个典型TSP问题描述为：设有n个城市的集合city=
的易于描述却难以大规模求解的NP一完全问题，对于{Cl。C2，⋯，}，对于城市Cf，G∈city，从G到C，的
这类问题很难用全局搜索法精确地求出其最优解，因距离记为d∈R，这里假设d=，即考虑对称
此应用的有效算法寻找其最优或近似最优解具有重要问题。P问题的解，就是在集合city中找到一个
的理论意义。另外，很多实际问题，如印刷电路板的钻不重复的全排列G1，2，⋯，．使其之间距离最短．
孔线路方案，连锁店的货物配送路线等经简化处理后也就是