Multi-Colony Ant Algorithm Using Both Generative Adversarial Nets and Adaptive Stagnation Avoidance Strategy

Abstract

Aiming at Travel Salesman Problem (TSP) that ant colony algorithm is easy to fall into local optima and slow convergence, a multi-colony ant algorithm using both generative adversarial nets (GAN) and adaptive stagnation avoidance strategy (GAACO) is proposed. First, to improve the convergence speed of the algorithm, we introduce a GAN model based on the game between convergence speed and solution quality. Then, to overcome premature convergence, an adaptive stagnation avoidance strategy is proposed. The strategy consists of two parts: (1) information entropy. It is used to measure the diversity of GAACO; (2) a cooperative game model. When the value of information entropy is less than threshold value, the cooperative game model will be used to select the appropriate pheromone matrix for different colonies to improve the accuracy. Finally, to further accelerate the convergence of the algorithm, the initial pheromone matrix is preprocessed to increase the pheromone of the optimal path for each iteration in the early stage. And according to reinforcement learning method, each colony increases the pheromone of the global optimal path at the end of each iteration. Extensive experiments with numerous instances in the TSPLIB standard library show that the proposed methods significantly outperform the state-of-the-art multi-colony ant colony optimization algorithms, especially in the large-scale TSPs.

Keywords

• Generative adversarial nets
• cooperative game
• information entropy
• travel salesman problem