TSP问题的蚁群算法优化及并行策略研究

学校代码：10491研究生学号：12003566中国地质大学硕士学位论文基于TSP问题的蚁群算法优化及并行策略研究硕士生：张礼学科专业：计算机应用技术指导教师：罗忠文副教授二○○六年五月ADissertationSubmittedtoChinaUniversityofGeosciencesfortheDegreeofMasterofEngineeringTheResearchonOptimizationandParallelizationStrategiesofAntColonyAlgorithmforSolvingTravelingSalesmanProblemMasterCandidate：ZhangLiMajor：ComputerApplicationTechnologySupervisor：AssociateProf.LuoZhongwenChinaUniversityofGeosciencesWuhan430074P.R.China研究生学位论文原创性声明我以诚信声明：本人所呈交的硕士学位论文是在罗忠文副教授的指导下，开展研究工作所取得的研究成果。文中关于TSP问题的蚁群算法新的优化策略是在罗忠文老师的指导下独立完成；算法运行数据结果、为确定各个关键参数的分析及其设定数据系本人研究和测试所得；文中蚁群算法的并行策略及算法的展望系本人独立完成，不包含他人研究成果。所引用他人之思路、方法、观点、认识均已在参考文献中明确标注，所引用他人之数据、图件、资料均已征得所有者同意，并且也有明确标注，对论文的完成提供过帮助的有关人员也已在文中说明并致以谢意。学位论文作者（签字）：签字日期：年月日作者简介张礼，男，1979年9月出生，2000年7月本科毕业于上海交通大学热能工程及其自动化专业，2003年9月进入中国地质大学（武汉）攻读计算机应用技术专业硕士学位。在读研期间，主要学习了算法设计与分析、高级计算机体系结构、组合数学、VisualC++、科学社会主义、自然辩证法、英语（含专业英语）等十几门课程，总学分34.5分，平均分为84.7分。在攻读硕士学位期间，曾在武汉中地数码科技股份有限公司（教育部GIS工程中心）进行实习，参与了多个软件项目的开发，主要从事国土资源部门基于MAPGIS平台的应用软件的研发，参与开发的项目有：湖南省衡阳市国土资源局国土资源电子政务系统、基于MAPGIS并内嵌RedOffice的公文流转开发等。2005年5月份，开始进入蚁群算法领域，并研究算法的优化及并行策略。在校期间，已发表论文十余篇，其中核心期刊一篇；以第一作者身份发表的论文主要有：（一部分公开期刊从略）1、基于MAPGIS工作流及RedOffice的公文流转开发.商场现代化（核心期刊）.2005年9月号，第20期（总第443期）.2、电子政务发展现状及策略分析.中国学术论坛.2005年第1期.3、蚁群算法的一种优化策略.知识与创新.2005年第11期.4、Oracle应用系统性能优化.学位（理论版）.2005年第2期.5、用SVG技术实现基于Web的GIS.知识与创新.2005年第11期.6、GML、VML和SVG的比较.经营与管理（增刊）.2005年增刊第082号.7、下一代网络NGN标准概述.知识与创新.2006年第2期.基于TSP问题的蚁群算法优化及并行策略研究硕士生：张礼导师：罗忠文副教授摘要许多实际工程问题可以抽象为相应的组合优化问题，TSP问题是作为所有组合优化问题的范例而存在的，它已成为并将继续成为测试组合优化新算法的标准问题。从理论上讲，使用穷举法可以求解出TSP问题的最优解；但是对现有的计算机来说，让它在如此庞大的搜索空间中寻求最优解，几乎是不可能的。所以，各种求TSP问题近似解的算法应运而生了，本文所描述的蚁群算法（AC）也在其中。目前已出现了很多的启发式算法，而蚁群算法作为一种新型的启发式算法，已成功地应用于求解TSP问题。蚂蚁通过分泌信息素来加强较好路径上信息素的浓度，同时按照路径上的信息素浓度来选择下一步的路径：好的路径将会被越来越多的蚂蚁选择，因此更多的信息素将会覆盖较好的路径；最终所有的蚂蚁都集中到了好的路径上。蚂蚁的这种基于信息素的正反馈原理正是整个算法的关键所在。首先，本文简要介绍了几种启发式算法并引出蚁群算法，并对蚁群算法基本原理、几种算法模型和相应的数学公式作了详细阐述，同时对前人的研究结果进行了引用；此外针对蚁群算法的缺陷，还描述了前人对算法所作的一些典型的优化：如蚁群系统算法ACS（也称蚁群优化算法ACO）、最大最小蚁群系统算法MMAS、具有变异特征的蚁群算法等。然后，文章对蚁群算法中的关键参数的设置进行了深入的研究。对参数α、β、ρ、m的作用作了理论上的研究，对它们的最优化配置进行了分析；同时针对以往参数设定的不便，提出了一种全新的、比较适当的参数设置方案：通过将蚁群算法的参数设置问题描述成均匀设计中多因素多水平的试验设计，它能用较少的试验很快设置出参数值，并可使蚁群算法获得较优的运行性能。接着，本文提出了建立在蚁群系统算法ACS基础上的一种新的优化策略：采用新方案进行关键参数设置，以克服以往的参数设置困难、不准确的缺点；通过引入遗传算法中用到的杂交算子，使前面蚂蚁所留信息素尽量少对后面的蚂蚁产生误导，增强算法的搜索能力；通过全局最小信息素浓度的设置，来扩宽算法的搜索空间；采用更高效的信息素更新和路径选择机制，以加快算法的收敛速度，使其更容易收敛到全局最优解。并对该优化策略进行了初步实验，证明了其有效性和可行性，也为蚁群算法的优化提供了一个新途径。在此之后，文章对蚁群算法的并行策略进行了初步的探讨，深入分析了两种不同的并行策略：同步策略和部分异步策略；另外，还提出了一种新的模式学习并行蚁群算法，并对它进行了具体的介绍。最后，本文对改进后的蚁群算法、以及蚁群算法的并行策略进行了总结性的阐述；同时对蚁群算法的进一步优化提出了自己的设想：引入种群入侵算子（也叫外变异算子）、权函数等；并对蚁群算法的研究前景进行了展望。关键词：TSP问题；蚁群算法；关键参数设置；优化策略；并行策略TheResearchonOptimizationandParallelizationStrategiesofAntColonyAlgorithmforSolvingTravelingSalesmanProblemMasterCandidate：ZhangLiSupervisor：Prof.LuoZhongwenAbstractManyactualengineeringproblemscanberegardedascombinationoptimizationproblems，andTSP（TravelingSalesmanProblem）isatypicalcombinationoptimizationproblem，ithasbecomeandwillcontinuetobecomeastandardproblemtotestanewalgorithmofcombinationoptimization.Theoreticallyspeaking，theenumerationcangetthebestanswerofTSP；buttoallcomputersnowadays，itishardlytoobtainthebestanswerinsuchhugeresearchingspacebyusingcommonenumeration.Soallkindsofalgorithmsemergedbecauseofdemand，theantcolonyalgorithm（AC）describedinthispaperisoneofthem.Presentlymanyheuristicalgorithmsappeared，andACalgorithmisaclassofheuristicalgorithmsthathavebeensuccessfullyappliedtosolvingTSP.Antsreinforcepheromoneintensitiesofbetterpathsbyexcretingchemicalsubstance（namelypheromone），synchronouslytheyselectnextpathsaccordingtopheromoneintensities：moreantswillselectbetterpaths，andmorepheromoneswillbelaidoverbetterpaths；atlastallantswillfocusonthebestpath.Thisisaformofbehaviorcalledautocatalyticbehavior，itisthekeytothesuccessofACalgorithm.Firstly，thispaperintroducesbrieflyseveralheuristicalgorithmsandeducesACalgorithm，expoundsfundamental、severalmodels、correspondingmathematicformula，synchronouslyreferstootherinvestigationconclusion；alsodescribessometypicaloptimizationsaimingatshortcomingsofACalgorithm：forexample，antcolonysystemalgorithm（ACS，namelyACO）、max-minantsystemalgorithm（MMAS）、antcolonysystemalgorithmwithmutationfeaturesetc.Then，thepaperinvestigatesthesettingsofimportantparametersaboutACalgorithm.Studytheoreticallythefunctionsofparameters（viz.α、β、ρ、m），analysestheiroptimumsettings；atthesametime，itpresentsakindofscheme：uniformdesignmethodisusedtoconverttheproblemofparameterestablishmentintoexperimentaldesignofmulti-factorandmulti-level，itcanobtainconvenientlyallparameters，andshowsgoodperformanceeffectiveness.Afterwards，anewoptimizationstrategybasedonACSalgorithmisprovided：anewmethodisusedtosetimportantparametersforovercomingformerdefects；acrossoveroperatorusedingeneticalgorithmiscontainedintheoptimizationstrategyforincreasingresearchingabilityofalgorithm；settingtheminimalpheromoneintensityforexpandingresearchingspace；adoptingnewpheromoneupdatingandpathselectingmethodsforquickeningconstringencyspeedofalgorithm.Inaddition，wedemonstratethefeasibilityandefficiencyofnewoptimizationstrategybymeansofexperimentalstu