A Multimodal Ant Colony Optimization Framework for Multi-Solution Traveling Salesman Problem
提出多模态蚁群优化框架，通过动态小生境策略和独立信息素矩阵，在单次运行中找出多条最优路径，实验表明结合排序蚁群算法效果最佳。
This paper devises a multimodal ant colony optimization (MACO) framework to solve multi-solution traveling salesman problems (MSTSPs), which aim to find multiple optimal routes in a single run. Specifically, a dynamic niching strategy is designed to partition the ant colony into exclusive niches based on the route similarity measured by the common edges between two routes. Subsequently, MACO maintains a pheromone matrix for each niche and lets the ants in each niche construct their routes independently based on the associated pheromone matrix. For effective pheromone update, this paper designs a niche and pheromone matrix association rule to match each newly partitioned niche with one pheromone matrix. To further improve optimization efficiency, this paper designs a dynamic critical edge strategy to dig out critical edges during the optimization. Then, these critical edges are cooperated with 2-opt to refine the route constructed by each ant. To preserve the found optimal routes, this paper devises an optimal route preservation strategy to store as many different high-quality routes as possible. Lastly, we instantiate MACO with four canonical ACOs, namely Ant System(AS), Elite AS(EAS), Rank-based AS(ASRank), and Max-Min AS(MMAS), and then conduct extensive experiments to compare them with six state-of-the-art algorithms on the only one MSTSP benchmark suite and the TSPLIB instances. The experimental results reveal that the four MACOs perform competitively with one latest algorithm, but significantly outperform the other five comparison algorithms. Further analysis discovers that ASRank is the most effective one among the four ACOs to cooperate with MACO in solving MSTSPs.