一种求解TSP问题的改进遗传蚁群算法

徐练淞　潘大志

摘要：旅行商问题（TSP）是一种经典的组合优化问题。传统的蚁群算法运用正反馈和分布式计算机制，具有较强的鲁棒性。但是该算法搜索时间长、易出现早熟停滯现象。因此本文根据旅行商问题的模型特点，在蚁群算法的基础上针对TSP问题提出了一种新型的改进蚁群算法：即变参数选择城市策略，并且在交叉策略中选择PMX（Partially Matched Crossover）交叉策略。实验结果表明，与传统基本蚁群算法和遗传算法相比，能够较快地找到最优解，解的质量也相对较好，因此提高了蚁群算法对TSP问题的求解-效率。

关键词：蚁群算法；群体智能；旅行商问题；遗传算法