A novel ant colony optimization based on game for traveling salesman problem

摘要

Ant Colony Optimization (ACO) algorithms tend to fall into local optimal and have insufficient astringency when applied to solve Traveling Salesman Problem (TSP). To address this issue, a novel game-based ACO (NACO) is proposed in this report. NACO consists of two ACOs: Ant Colony System (ACS) and Max-Min Ant System (MMAS). First, an entropy-weighted learning strategy is proposed. By improving diversity adaptively, the optimal solution precision can be optimized. Then, to improve the astringency, a nucleolus game strategy is set for ACS colonies. ACS colonies under cooperation share pheromone distribution and distribute cooperative profits through nucleolus. Finally, to jump out of the local optimum, mean filtering is introduced to process the pheromone distribution when the algorithm stalls. From the experimental results, it is demonstrated that NACO has well performance in terms of both the solution precision and the astringency.