Abstract:Ant colony optimization algorithm is a new simulated evolutionary algorithm, which has the faculty of global optimization. An adaptive parallel ant colony optimization algorithm (APACO) is presented. It dynamically adjusts the parameters according to the searching phases, thus the convergence is accelerated to a certain extent. The adaptive migration rule could not only enrich the diversity of the colonies but also reduce the communication between colonies. Finally, the CHN144 problem of China in Nonnumerical Parallel Algorithm: the Simulated Annealing Algorithm by Lishan Kang is applied to calibrate the algorithm. Results show that the proposed algorithm improves the searching speed with good global convergence.
[1] Dorigo M, Maniezzo V, Colorni A. The Ant System: Optimization by a Colony of Cooperating Agents. IEEE Trans on Systems, Man and Cybernetics, 1996, 26(1): 2941 [2] Kang Lishan, Xie Yun, You Shiyong, et al. NonNumerical Parallel Algorithm-the Simulated Annealing Algorithm. Beijing, China: Science Press, 2000: 149153 (in Chinese) (康立山,谢 云,尤矢勇,等.非数值并行算法——模拟退火算法.北京:科学出版社, 2000: 149153) [3] Stützle T, Hoos H. MAXMIN Ant System and Local Search for Combinatorial Optimization Problems // Vos S S, Osman M I H, Roucairol C, eds. MetaHeuristics: Advances and Trends in Local Search Paradigms for Optimization. Boston, USA: Kluwer Academic, 1999: 313329 [4]Tsai C F, Tsai C W, Tseng C C. A New Hybrid Heuristic Approach for Solving Large Traveling Salesman Problem. Information Sciences, 2004, 166(1/2/3/4): 6781 [5] Chu S C, Roddick J F, Pan J S. Ant Colony System with Communication Strategies. Information Sciences, 2004, 167(1/2/3/4): 6376 [6] Favuzza S, Graditi G, Sanseverino E R. Adaptive and Dynamic Ant Colony Search Algorithm for Optimal Distribution Systems Reinforcement Strategy. Applied Intelligence, 2006, 24(1): 3142 [7] Wu Qinghong, Zhang Jihui, Xu Xinhe. An Ant Colony Algorithm with Mutation Features. Journal of Computer Research and Development, 1999, 36(10): 12401245 (in Chinese) (吴庆洪,张纪会,徐心和.具有变异特征的蚁群算法.计算机研究与发展, 1999, 36(10): 12401245) [8] Chen Ling, Shen Jie, Qin Ling, et al. An Adaptive Ant Colony Algorithm Based on Equilibrium of Distribution. Journal of Software, 2003, 14(8): 13791387 (in Chinese) (陈 崚,沈 洁,秦 玲,等.基于分布均匀度的自适应蚁群算法.软件学报, 2003, 14(8): 13791387) [9] Stützle T. Parallelization Strategies for Ant Colony Optimization // Eiben A E, Back T, Schoenauer M, et al, eds. Lecture Notes in Computer Science. Berlin, Germany: SpringerVerlag, 1998, 1498: 722741 [10] Foster I. Designing and Building Parallel Programs. Reading, USA: AddisonWeslley, 1994 [11] Matsumura T, Nakamura M, Okech J, et al. A Parallel and Distributed Genetic Algorithm on LooselyCoupled Multiprocessor System. IEICE Trans on Fundamentals of Electronics, Communications and Computer Sciences, 1998, 81(4): 540546 [12]Yu Bin, Cheng Chuntian, Yang Zhongzhen, et al. CoarseGrain Parallel Ant Colony Optimization Algorithm. Systems Engineering and Electronics, 2006, 28(4): 626629 (in Chinese) (于 滨,程春田,杨忠振,等.一种改进的粗粒度并行蚁群算法.系统工程与电子技术, 2006, 28(4): 626629)