用蚂蚁算法和模拟退火算法解大规模TSP问题的研究.pdfVIP

CN43—1258／TP 计算机工程与科学 2008年第 3O卷第 10期 ISSN 1007—130X COMPUTERENGINEERING8LSCIENCE Vo1．30，No．10，2008 文章编号 ：1007—130X(2008)10—0043—02 用蚂蚁算法和模拟退火算法解大规模 TSP问题的研究 ResearchonUsingtheAntAlgorithm andthe SimulatedAnnealingAlgorithm toSolvethe Large——ScaleTravelingSalesmanProblem 许智宏。宋 勃，董建波 XUZhi-hong，SONGBo，DONGJiawbo (河北工业大学，天津 300130) (HebeiUniversityofTechnology。Tianjin300130，China) 摘 要：TSP问题是一个NP完全问题。随着问题规模的增大，其解空间呈指数增长，无法在多项式时间内完成问题 的求解。近几十年来，人们提 出了许多基于生物理论的解决该问题的新方法。本文应用蚂蚁算法、模拟退火算法对TSP 问题进行求解。在求解过程中对各算法中参数的作用和设置方法作了一些分析，使用不同参数进行多次实验，验证参数设 置原则；对不同规模的TSP问题进行实验，比较两个算法的性能，分析造成其性能差异的原因，并提 出了改进建议。 Abstract：TheTravelingSalesmanProblem (TSP)isanon-polynomial-complete(NPC)problem．W iththescaleincrea- ses，thesolutionspacegrowsrapidly，making itimpossibletObesolved inapo lny omialtmie．During thepastseveraldec— ades，peoplefoundnew waystOsolvetheproblem basedonthemechanism ofbiologicaltheory．How tOusetheantalgo— rithrnandthesimulatedannealingalgorithm tOsolvethelarge-scaletravelingsalesmanproblem isstudied，andthefunctions oftheparametersandthemethodofconfiguringthem inthetwoalgorithmsareanalyzed．Aftertheexperimentswithdiffer- entscalesofTSPs，theefficienciesofthetwoalgoritmh sarecompared，andthereasonsforthedifferenceofefficienciesrae discussed．Finally，thesuggestionsformiprovingthealgorithmsaregiver~ 关键词：蚂蚁算法；模拟退火算法；TSP问题；NP完全问题 Keywords：antalgoritmh ；smiulatedannealing；TSP；non-polnyomial-completeproblem 中圈分类号：TP18 文献标识码 ：A 1 引言 2 算法的实现 旅行商 问题L1J(TravelingSalesmanProblem，简称 2．1 蚂蚁算法的具体实现 TSP)是一个经典的组合优化问题。它可以描述为：一个商 蚁群算法的步骤6【]如下： 品推销员要去若干个城市推销商品，从一个城市出发，需要