求解TSP算法的研究与改进.pdf

《求解TSP算法的研究与改进.pdf》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、彳．forthedegreeofMasterResearchandImprovementaboutTSPAlgorithmByYinhouHuSupervisor：Prof．ShiqingWangComputerSoftwareandTheoryT^●’'●一'●上n／ormatlont：ngmeermgSCn00lMay2012学位论文原创性本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独立进行研究所取得的成果。除文中已经注明引用的内容外，本论文不包含任何其他个人或集体己经发表或撰写过的科研成果。对本文的研究作出重要贡献的个人

2、和集体，均已在文中以明确方式标明。本声明的法律责任由本人承担。学位论文懈扬矽吼日期：加7诨∥月歹佃学位论文使用授权声明本人在导师指导下完成的论文及相关的职务作品，知识产权归属郑州大学。根据郑卅l大学有关保留、使用学位论文的规定，同意学校保留或向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和借阅；本人授权郑州大学可以将本学位论文的全部或部分编入有关数据库进行检索，可以采用影印、缩印或者其他复制手段保存论文和汇编本学位论文。本人离校后发表、使用学位论文或与该学位论文直接相关的学术论文或成果时，第一署名单位仍然为郑卅I大学。保密

3、论文在解密后应遵守此规定。学位论文慨却谗肜日期：叼11年多月，日摘要旅行商问题(TravelingSalesmanProblem，简称TSP)是组合优化问题中的经典问题，也是一个NP完全问题。同时，它也是众多优化问题的简化形式，如基因组制图、行星探索、电路板钻孔、电路板焊接、交通调度、作业调度等。由于TSP问题是一个NP完全问题，求解难度大，它也被用作处理器测试和算法比较的标准。因此，对TSP的研究具有重要的理论和应用价值。蚁群算法是求解TSP的有效方法之一。它是由意大利学者DorigoM等人提出，是一种基于种群的启发式进化算法，具有较

4、强的鲁棒性、并行性、很好的可扩充性，且易于和其他的方法融合的优点。同时，它是一种结合了分布式计算、正反馈机制和遵循贪心原则的搜索算法。蚁群算法自提出之后，引起了许多学者的关注，并将其应用到各个领域的优化问题中。蚁群算法有多种变种，其中最大一最小蚁群算法求解TSP效果最好。本文深入分析了最大一最小蚁群算法运行过程中的算法数据，发现当算法陷入收敛之后，大部分蚂蚁开始构造相同的路径，这在很大程度上浪费了蚂蚁的探索能力。本文中通过让蚂蚁选择第一条边时不使用信息素，很好改善了这一现象。同时，对比研究TSP的真实最优环路与算法构造环路发现，包含真实

5、最优边的环路一般都较短。环路长度和其包含的真实最优边数成反比，环路包含的真实最优边数越多，环路长度越短。据此，反过来可以认为较短环路中所包含的边为真实最优边的概率也大。受此启发，本文提出了一种基于优质边的求解策略。利用算法运行的历史信息选择优质边，也即为真实最优边可能性大的边。使用修改的选路规则，将蚂蚁的路径尽可能限制在优质边中，以试图降低算法的解空间。本文还通过设置不同算法参数的对比实验，确定了改进算法的最合适参数。通过对改进算法的实验仿真，发现改进的算法加快了蚂蚁构造优质解的过程，同时也使得算法在很大概率上能找到真实最优解，提高了算

6、法的求解性能，证明了算法改进的有效性。关键词：蚁群优化：旅行商问题：优质边；智能计算；最大．最小蚁群算法0manyoptimizationproblemssuchaSgenomemapping，planetaryexploration,thedrillingofcircuitboards，circuitboardwelding，trafficscheduling，jobschedulingandSOon．SincetheTSPisanNP—completeproblemandhardtobesolved，itisalsousedaSas

7、tandardprocessortestsandstandardproblemforcomparethealgorithms．Therefore，theTSPstudyhaSbothimportanttheoreticalandpracticalvalues．Theearly1990s，inspiredbyantforagingbehaviorinnature，theItalianscholarbyDorigoM，etproposedtheantcolonyalgorithm．Itisapopulation-basedheuristic

8、evolutionaryalgorithm晰tllstrongrobustness，parallelism,scalability,flexibilityandeasytobeintegratedwimot