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