Content area
Full Text
Appl Intell (2011) 34: 6473 DOI 10.1007/s10489-009-0179-6
Study on hybrid PS-ACO algorithm
Bing Shuang Jiapin Chen Zhenbo Li
Published online: 14 May 2009 Springer Science+Business Media, LLC 2009
Abstract Ant colony optimization (ACO) algorithm is a recent meta-heuristic method inspired by the behavior of real ant colonies. The algorithm uses parallel computation mechanism and performs strong robustness, but it faces the limitations of stagnation and premature convergence. In this paper, a hybrid PS-ACO algorithm, ACO algorithm modied by particle swarm optimization (PSO) algorithm, is presented. The pheromone updating rules of ACO are combined with the local and global search mechanisms of PSO. On one hand, the search space is expanded by the local exploration; on the other hand, the search process is directed by the global experience. The local and global search mechanisms are combined stochastically to balance the exploration and the exploitation, so that the search efciency can be improved. The convergence analysis and parameters selection are given through simulations on traveling salesman problems (TSP). The results show that the hybrid PS-ACO algorithm has better convergence performance than genetic algorithm (GA), ACO and MMAS under the condition of limited evolution iterations.
Keywords Ant colony optimization Particle swarm
optimization Hybrid PS-ACO TSP
1 Introduction
Ant colony optimization (ACO) is a recently developed, evolution based approach which has been inspired by the
B. Shuang ( ) J. Chen Z. Li
National Key Laboratory of Nano/Micro Fabrication Technology, Key laboratory for Thin Film and Microfabrication of Ministry of Education, Research Institute of Micro/Nano Science and Technology, Shanghai Jiao Tong University, Shanghai 200030, Chinae-mail: mailto:[email protected]
Web End [email protected]
behavior of real ant colonies, in particular, by their foraging behavior [1, 2]. ACO has been successfully applied to several NP-hard combinatorial optimization problems [3], such as traveling salesman problems (TSP) [3, 4], quadratic assignment [5], vehicle routing [6], sequential ordering [7] and scheduling [8].
The ACO algorithm uses pheromone as an indirect communication medium among the individuals of a colony of ants, and the procedure of converging to the global optimum is a dynamic positive feedback of pheromone. Once a better solution is found, exploitation of the solution will be made by increasing the associated pheromone trails, while the pheromones trails of other solutions will be evaporated. If one...