TSP问题的蚁群算法优化及并行策略研究硕士学位论文.doc

学校代码:10491研究生学号:12003566中国地质大学硕士学位论文基于TSP问题的蚁群算法优化及并行策略研究ADissertationSubmittedtoChinaUniversityofGeosciencesfortheDegreeofMasterofEngineeringTheResearchonOptimizationandParallelizationStrategiesofAntColonyAlgorithmforSolvingTravelingSalesmanProblemMasterCandidate:puterApplicationTechnologySupervisor::所呈交的论文是本人在导师的指导下独立进行研究所取得的研究成果。除了文中特别加以标注引用的内容外,本论文不包含任何其他个人或集体已经发表或撰写的成果作品。对本文的研究做出重要贡献的个人和集体,均已在文中以明确方式标明。本人完全意识到本声明的法律后果由本人承担。作者签名: 日期:年月日学位论文版权使用授权书本学位论文作者完全了解学校有关保留、使用学位论文的规定,同意学校保留并向国家有关部门或机构送交论文的复印件和电子版,允许论文被查阅和借阅。本人授权大学可以将本学位论文的全部或部分内容编入有关数据库进行检索,可以采用影印、缩印或扫描等复制手段保存和汇编本学位论文。涉密论文按学校规定处理。作者签名: 日期:年月日导师签名:日期:年月日研究生学位论文原创性声明我以诚信声明:本人所呈交的硕士学位论文是在罗忠文副教授的指导下,开展研究工作所取得的研究成果。文中关于TSP问题的蚁群算法新的优化策略是在罗忠文老师的指导下独立完成;算法运行数据结果、为确定各个关键参数的分析及其设定数据系本人研究和测试所得;文中蚁群算法的并行策略及算法的展望系本人独立完成,不包含他人研究成果。所引用他人之思路、方法、观点、认识均已在参考文献中明确标注,所引用他人之数据、图件、资料均已征得所有者同意,并且也有明确标注,对论文的完成提供过帮助的有关人员也已在文中说明并致以谢意。学位论文作者(签字):签字日期:年月日基于TSP问题的蚁群算法优化及并行策略研究摘要许多实际工程问题可以抽象为相应的组合优化问题,TSP问题是作为所有组合优化问题的范例而存在的,它已成为并将继续成为测试组合优化新算法的标准问题。从理论上讲,使用穷举法可以求解出TSP问题的最优解;但是对现有的计算机来说,让它在如此庞大的搜索空间中寻求最优解,几乎是不可能的。所以,各种求TSP问题近似解的算法应运而生了,本文所描述的蚁群算法(AC)也在其中。目前已出现了很多的启发式算法,而蚁群算法作为一种新型的启发式算法,已成功地应用于求解TSP问题。蚂蚁通过分泌信息素来加强较好路径上信息素的浓度,同时按照路径上的信息素浓度来选择下一步的路径:好的路径将会被越来越多的蚂蚁选择,因此更多的信息素将会覆盖较好的路径;最终所有的蚂蚁都集中到了好的路径上。蚂蚁的这种基于信息素的正反馈原理正是整个算法的关键所在。首先,本文简要介绍了几种启发式算法并引出蚁群算法,并对蚁群算法基本原理、几种算法模型和相应的数学公式作了详细阐述,同时对前人的研究结果进行了引用;此外针对蚁群算法的缺陷,还描述了前人对算法所作的一些典型的优化:如蚁群系统算法ACS(也称蚁群优化算法ACO)、最大最小蚁群系统算法MMAS、具有变异特征的蚁群算法等。然后,文章对蚁群算法中的关键参数的设置进行了深入的研究。对参数α、β、ρ、m的作用作了理论上的研究,对它们的最优化配置进行了分析;同时针对以往参数设定的不便,提出了一种全新的、比较适当的参数设置方案:通过将蚁群算法的参数设置问题描述成均匀设计中多因素多水平的试验设计,它能用较少的试验很快设置出参数值,并可使蚁群算法获得较优的运行性能。接着,本文提出了建立在蚁群系统算法ACS基础上的一种新的优化策略:采用新方案进行关键参数设置,以克服以往的参数设置困难、不准确的缺点;通过引入遗传算法中用到的杂交算子,使前面蚂蚁所留信息素尽量少对后面的蚂蚁产生误导,增强算法的搜索能力;通过全局最小信息素浓度的设置,来扩宽算法的搜索空间;采用更高效的信息素更新和路径选择机制,以加快算法的收敛速度,使其更容易收敛到全局最优解。并对该优化策略进行了初步实验,证明了其有效性和可行性,也为蚁群算法的优化提供了一个新途径。在此之后,文章对蚁群算法的并行策略进行了初步的探讨,深入分析了两种不同的并行策略:同步策略和部分异步策略;另外,还提出了一种新的模式学****并行蚁群算法,并