J4 ›› 2010, Vol. 48 ›› Issue (05): 787-792.

Previous Articles     Next Articles

Multi Parallel Ant Colony Optimization AlgorithmsBased on CMP and Their Comparison

HE Li li, WANG Kemiao, BAI Hongtao, HU Chengquan   

  1. College of Computer Science and Technology, Jilin University, Changchun 130012, China|Key Laboratory of |Symbolic Computation and Knowledge Engineering of Ministry of Education, Jilin University, Changchun 130012, China
  • Received:2009-08-23 Online:2010-09-26 Published:2010-09-21
  • Contact: HE Li li E-mail:helili@jlu.edu.cn

Abstract:

Multi parallel ant colony optimization algorithms based on chip multiprocessor (CMP) proposed in this paper include parallel MAXMIN ant system, parallel ant colony system and diffrent mixture strategies of both the systems. Each core of the CMP simulates a subant colony and the whole ant system shares one pheromone matrix. The implementation was obtained by the multi
threads with real time priority. The influence of the strategies was examined by several traveling salesman problem benchmarks from TSPLIB. Experiments show that parallel ACOs based on CMP have nearly linear speedup by the number of cores and the mixture of MAXMIN ant system and ant colony system has the advantage in the stability of solutions.

Key words: ant colony optimization, sharing one pheromone matrix, parallel computing, chip multiprocessor

CLC Number: 

  • TP18