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