蚁群算法的改进及其在TSP问题中的应用

本文根据已有的蚁群算法的一种――相遇算法提出了并行相遇算法。并行相遇算法改进了原有算法中两只蚂蚁选择城市时的不平等现象,在两只蚂蚁选择城市冲突时也找到了一种合理的解决方法:转换仲裁节点。在此基础上,在算法中加入了局部优化算法2-Opt以提高算法的性能。本文在加入局部优化算法2-Opt时,使两个算法在一定程度上并行:蚁群算法搜索到的路径为局部优化提供了优化的基础,局部优化在一定程度上对蚁群算法做必要的引导但同时避免在较大程度上影响其路径的多样性。笔者将以上算法针对四组不同的TSP实例进行了实验,并将实验结果与原有的相遇算法、最大最小蚁群算法和基本的蚁群算法进行了比较和分析。实验的初步结果比较令人满意。文中又提出了新的改进方法:将本文的算法与对较大规模TSP问题的分段结合,以改进算法的运行时间和解的质量。如何合理地将大规模TSP问题划分成若干小的TSP问题,并将此划分与本文算法相结合,将是作者未来的研究方向。