求解 TSP 算法的研究与改进

摘要
旅行商问题（Traveling Salesman Problem，简称TSP）是组合优化问题中的经典问题，也是一个NP完全问题。同时，它也是众多优化问题的简化形式，如基因组制图、行星探索、电路板钻孔、电路板焊接、交通调度、作业调度等。由于TSP问题是一个NP完全问题，求解难度大，它也被用作处理器测试和算法比较的标准。因此，对TSP的研究具有重要的理论和应用价值。蚁群算法是求解TSP的有效方法之一。它是由意大利学者Dorigo M等人提出，是一种基于种群的启发式进化算法，具有较强的鲁棒性、并行性、很好的可扩充性，且易于和其他的方法融合的优点。同时，它是一种结合了分布式计算、正反馈机制和遵循贪心原则的搜索算法。蚁群算法自提出之后，引起了许多学者的关注，并将其应用到各个领域的优化问题中。蚁群算法有多种变种，其中最大－最小蚁群算法求解TSP效果最好。本文深入分析了最大－最小蚁群算法运行过程中的算法数据，发现当算法陷入收敛之后，大部分蚂蚁开始构造相同的路径，这在很大程度上浪费了蚂蚁的探索能力。本文中通过让蚂蚁选择第一条边时不使用信息素，很好改善了这一现象。同时，对比研究TSP的真实最优环路与算法构造环路发现，包含真实最优边的环路一般都较短。环路长度和其包含的真实最优边数成反比，环路包含的真实最优边数越多，环路长度越短。据此，反过来可以认为较短环路中所包含的边为真实最优边的概率也大。受此启发，本文提出了一种基于优质边的求解策略。利用算法运行的历史信息选择优质边，也即为真实最优边可能性大的边。使用修改的选路规则，将蚂蚁的路径尽可能限制在优质边中，以试图降低算法的解空间。
本文还通过设置不同算法参数的对比实验，确定了改进算法的最合适参数。通过对改进算法的实验仿真，发现改进的算法加快了蚂蚁构造优质解的过程，同时也使得算法在很大概率上能找到最优解，提高了算法的求解性能，证明了算法改进的有效性。
关键词：蚁群优化；旅行商问题；优质边；智能计算；最大-最小蚁群算法
目录