Entropy-Based Dynamic Heterogeneous Ant Colony Optimization

Abstract

To solve large-scale traveling salesman problem (TSP) with better performance, this paper proposes an entropy-based dynamic heterogeneous ant colony optimization (EDHACO). The allotropic mechanism and the heterogeneous colonies model are proposed to balance the convergence and the solution diversity. First, entropy is used to measure the diversity, and the entropy-based allotropic mechanism with three communication strategies can improve the adaptability of EDHACO. Then, the heterogeneous colonies with complementary advantages are proposed to balance the convergence speed and the diversity of the algorithm. Besides, two operators are proposed to improve the performance of the algorithm. The adaptive 3-opt operator can be used to accelerate the convergence, and the dynamic-pheromone-reset operator can be introduced to avoid trapping in a local optimum. Finally, EDHACO is applied to solve TSPs, and the experimental results suggest that it has better performance with higher stability and precision in TSP instances, especially in the large-scale TSP instances.

Keywords

• Entropy
• allotropic mechanism
• dynamic pheromone operator
• adaptive 3-opt operator
• travel salesman problem