CAJ | 학술논문

为了解决传统蚁群算法求解TSP问题的求解时间较长、易于局部收敛的问题，提出了一种基于变异和启发式选择的蚁群优化算法。利用较优路径中城市相互之间的邻接特点，避免了大范围搜索求解，使得能具有较好的初始解，将算法的时间复杂度大大降低；同时为了加快算法的收敛速度，对于路径的启发式选择进行重新定义；引入变异机制，充分利用2-交换法简洁高效的特点，既提高了变异效率，也改进了变异质量。实验结果证明，在一些经典TSP问题上新算法表现出很好的性能。
위료해결전통의군산법구해TSP문제적구해시간교장、역우국부수렴적문제，제출료일충기우변이화계발식선택적의군우화산법。이용교우로경중성시상호지간적린접특점，피면료대범위수색구해，사득능구유교호적초시해，장산법적시간복잡도대대강저；동시위료가쾌산법적수렴속도，대우로경적계발식선택진행중신정의；인입변이궤제，충분이용2-교환법간길고효적특점，기제고료변이효솔，야개진료변이질량。실험결과증명，재일사경전TSP문제상신산법표현출흔호적성능。
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 adja-cent 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.