Adaptive Parallel Ant Colony Algorithm And Its Application

Ant colony algorithm (ACA) has emerged recently as a new meta-heuristic for complicated problems in combinatorial optimization. Inspired by the collective behavior of real ants, Dorigo, Maniezzo et al first advanced an ant colony system and the ant colony optimization algorithm(ACO) to solve several discrete optimization problems. ACA has exhibited its excellent performance and efficiency in experiments for solving a great lot of combinatorial optimization problems. After being extended and improved by many researchers, ACA is in its boosting stage.Many simulation experiments indicate that ACA can obtain satisfactory solution for middle or small-scale applications within reasonable time. But for large or super-large scale tasks,the sequential ACA takes less effect. A critical problem of simple ACA is pre-maturity in its process of optimization. The reason of pre-maturity is that the movements of the individuals in ant colony are stochastic at the initial stage of search. Although they can evolve to the optimal path by interchange information, they can hardly find an optimum one from a mass of paths within a short time when the problem scale is large enough. Blindly accelerating the convergence speed will make the ants'local search and lead to premature and stagnation of the algorithm. These hinder the application of ACA grievously. Therefore, parallel technology and traditional ACA should be combined to improve ACA's efficiency and reduce the pre-maturity by utilizing the inherent parallelism of ACA.In this paper, by analyzing the principle and the performance of ant colony algorithm, we indicate that the critical factors influencing the performance of parallel ant colony algorithm are the strategies of choosing the partner, the context and the time interval of information exchange between the processors. To improve these three factors, we present several adaptive strategies, and propose adaptive parallel ant colony algorithm accordingly. In choosing the partner of information exchange for each processor, in order to avoid randomly choosing the partner of information exchange, several different adaptive strategies for information exchange between processors are proposed, such as selection based on sorting and selection based on the convergence coefficient of the sub colony on each processor, which can make each processor choose a proper processor to communicate. In deciding the context of information exchange...