基于ACO的TSP问题求解.doc

《最优化方法与设计》实验报告 基于蚁群优化算法求解TSP问题研究 摘要 研究了现有的最有效的蚁群优化算法(ACO)解决旅行商(TSP)问题，实现了蚂蚁系统(AS)，精华蚂蚁系统(EAS), 基于排列的蚂蚁系统(ASrank ),最大最小蚂蚁系统(MMAS)和蚁群系统(ACS)五种ACO算法，并且在TSPLIB中对算法进行了测试比较，实验并分析在这五种ACO算法中如何有效的设置参数，并且对这五种ACO算法运行过程的行为及性能进地了分析与比较。 关键字 蚁群算法 旅行商问题 组合优化 1 意义和目标 蚁群优化(Ant Colony Optimization)是由Macro Dorigo于1991年在米兰理工大学发明的，它模拟蚂蚁的觅食行为来求解问题，是一种非常有效的元启发式算法。短短十几年时间，蚁群优化算法就因为它出色的性能很快得到了广泛的认可，它的算法得到不断的改进，并逐渐形成了一系列成熟的算法框架。它的应用从求解TSP问题扩展到优化问题领域的各个方面。而TSP问题是最古老的、受到最广泛研究的组合优化问题之一。几乎所有的元启发式算法都以TSP作为测试算法性能的问题。这些元启发式算法包括禁忌搜索(tabu search)、进化算法(evolutionary algorithm)、模拟退火(simulated annealing)和迭代局部搜索(iterated local search)。所以学习并研究ACO在求解TSP问题的性能很有意义，并且在TSP中能获取最优性能的ACO算法版本，往往在求解其他问题时具有世界级的性能。 本实验的目标是研究ACO算法，并且用ACO求解TSP问题，用C语言实现目前有效的ACO算法，包括蚂蚁系统(Ant System)，精华蚂蚁系统(elitist strategy for ant system, EAS)，基于排列的蚂蚁系统(AS rank, RAS)，最大最小蚂蚁系统(MAX-MIN Any System, MMAS)和蚁群系统(ant colony system, ACS)。并在TSPLIB中测试这些算法的各项性能，总结并分析每种算法的行为和在不同参数下算法性能的对比。 2 国内外研究现状 旅行商问题(traveling salesman problem, TSP)是一个被学术界广泛研究的问题，第一篇关于TSP及其相关问题的文献可以追溯到19世纪(Schrjiver 2002)。自20世纪50年代以来，关于TSP的研究工作在运筹学和计算机科学领域都得到了进一步的加强。20世纪80年代早期，TSP的解决方法主要集中在构建启发式方法，迭代改进算法，以及一些确定性算法。自20世纪80年代以来，越来越多的元启发式算法被应用来解TSP问题。在2002年的“第八届DIMACS TSP实现挑战赛”(8th DIMACS Implementation Challenge on the TSP)集中研究了用启发式算法求解TSP问题的经典算法。目前为止，最有效的求解TSP的方法为带Lin-Kernighan方法的迭代算法(Helsgaun,2002)以及一种专门用于求解TSP的路径合并方法(tour-merging approach, Applegate,1999)。另外，使用确定性求解TSP问题也取得了相当不错的结果。在2002年春季，已经求得确定最优解的规模最大的TSP是一个包含15112个城市的实例。但是确定性算法在求解大规模的NP-难问题时，在时间上依然是不可行的。 第一个ACO算法是蚂蚁系统，1991年由Macro Dorigo发明以来已经形成了一系列改进算法，这些改进算法有精华蚂蚁系统(Dorigo, 1992)，Ant-Q(Gambardella Dorigo, 1995)，蚁群系统(Dorigo Gambardella(1997)，最大最小蚂蚁系统(Stutzle Hoos, 1996)，基于排列的蚂蚁系统(Bullnheimer, Hartl Strauss, 1997)。实验证明，在用ACO求解TSP问题时加入局部搜索可以显著提高解的质量，以及缩短算法找到更优的解的时间。蚁群优化元启发式算法的发展主要是由实验进行的， 我们目前还无法从理论上对蚁群优化算法进行完整的证明，但是已经可以证明一些ACO算法的解收敛和一些ACO算法的值收敛。证明值收敛可以理解为证明算法可以生成至少一次问题的最优解，证明解收敛可以理解为证明算法能够到达反复生成同一个最优解的状态。收敛性证明告诉我们随机算法的偏向性不会造成求不出最优解的情况。但是它没有告诉我们算法的收敛速度如何，也就是找到一个最优解的计算时间仍是未知的。(Marco Dorigo Thomas Stutzle 2004) 3算法理论分析 旅行商问