Abstract:

The traditional ant colony algorithm has many problems in convergence and diversity when solving the traveling salesman problem (TSP). Therefore, this paper proposes a heterogeneous multi-ant colony algorithm that combines the competitive interaction strategy and the eliminating-reconstructing mechanism (CEACO) to overcome these shortcomings. Firstly, the algorithm uses a competitive interaction strategy, which adjusts the interaction period adaptively according to the Hamming distance of different groups in different periods. Competition coefficients are adopted to differentiate matching interaction objects for interaction. The matched objects interact with each other through the optimal solution and pheromone matrix. This mechanism achieves a balance between algorithm convergence speed and diversity. Secondly, the algorithm uses the eliminating-reconstructing mechanism, which periodically eliminates and reconstructs the poor-searching populations to improve the solution accuracy of the algorithm.Finally, several groups of simulation experiments prove that the algorithm outperforms other methods in improving the solution accuracy and convergence speed.

Key words: ant colony optimization(ACO), heterogeneous multiple population, competitive interaction, eliminating-reconstructing, traveling salesman problem