基于聚类集成的蚁群算法求解大规模TSP问题

ACA（Ant Colony Algorithm）是一种可以有效求解组合优化的TSP（Travelling Salesman Problem）问题的方法。然而，当TSP问题的规模较大时，该算法的求解性能将会明显减弱。本文针对大规模TSP问题提出一种基于聚类集成的蚁群算法IAPACA（Improved AP Ant Colony Algorithm）的求解方法。利用AP（Affinity Propagation）聚类对大规模旅行商问题进行处理，将大规模旅行商问题分为若干子问题，并对每个子问题用蚁群算法进行寻优。然后用改进的集成方案对子问题进行组合，得到问题的结果。最后进行TSPLIB标准库测试算例的实验仿真，实验结果表明，基于聚类集成的蚁群算法具有更好的求解效果。

Ant Colony Algorithm Based on Clustering Integration for Solving Large-scale TSP Problems

Ant Colony Algorithm (ACA) is a Travelling Salesman Problem (TSP) to effectively solve the combination optimization. However, with the increased scale of TSP, traditional ACA has failed to effectively solve a large-scale TSP. The paper proposes a solving method based on Improved AP Ant Colony Algorithm (IAPACA) for large-scale TSP. With the AP clustering, the TSP is divided into sub-problems, for which the optimal solution is sought. Then the consequence of the problem is acquired through combination of the sub-problems with improved scheme. Finally an experiment simulation for test calculating example from TSPLIB standard library is conducted. The experimental results show that IAPACA has better effect than that of the traditional ACA.