Abstract: There are some shortcomings in the traditional ant colony algorithm as the algorithm costs too much time to get an optimal solution and easily falls into a stagnation behavior. To solve these problems, this paper puts forward a new ant colony algorithm based on mutation features and selected heuristic. The new algorithm uses the basic characteristics between the adjacent nodes in the optimal path, avoiding the large scope searching. It can get better initial solutions and greatly reduces the time complexity of the algorithm. It also uses the selected heuristic to accelerate the convergence process. With the 2-exchanged method, the mutation strategy not only enhances the mutation efficiency, but also improves the mutation quality. Combined with classic TSP instances, the MFSHACO algorithm shows good performance.

Key words: ants colony system, Traveling Salesman Problem（TSP）, mutation, selected heuristic

摘要： 为了解决传统蚁群算法求解TSP问题的求解时间较长、易于局部收敛的问题，提出了一种基于变异和启发式选择的蚁群优化算法。利用较优路径中城市相互之间的邻接特点，避免了大范围搜索求解，使得能具有较好的初始解，将算法的时间复杂度大大降低；同时为了加快算法的收敛速度，对于路径的启发式选择进行重新定义；引入变异机制，充分利用2-交换法简洁高效的特点，既提高了变异效率，也改进了变异质量。实验结果证明，在一些经典TSP问题上新算法表现出很好的性能。

关键词: 蚁群算法, 旅行商问题（TSP）, 变异, 启发式选择