基于CMP的多种并行蚁群算法及比较

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

基于CMP的多种并行蚁群算法及比较

何丽莉, 王克淼, 白洪涛, 胡成全

吉林大学计算机科学与技术学院, 长春 130012|吉林大学符号计算与知识工程教育部重点实验室, 长春 130012

收稿日期:2009-08-23 出版日期:2010-09-26 发布日期:2010-09-21
通讯作者: 何丽莉 E-mail:helili@jlu.edu.cn

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

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

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

摘要：

基于片上多核处理器（Chip Multiprocessor, CMP）的多种并行蚁群算法, 包括并行最大最小蚂蚁系统、并行蚁群系统及两者的混合等5个并行算法, 提出一种在CMP的每个处理器核心上模拟一个子蚁群, 整体蚁群共享同一信息素矩阵, 实现信息素隐式交流的方法. 用多线程实时优先级实现该算法, 并用若干旅行商问题实例进行了测试, 分析了不同并行策略的影响. 测试结果表明, 基于CMP的并行蚁群具有相对于核心数目的线性加速比, 异种蚁群混合策略在解的稳定性上更具优势.

关键词: 蚁群优化；共享信息素矩阵；并行计算；片上多核处理器

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

中图分类号:

TP18

何丽莉, 王克淼, 白洪涛, 胡成全. 基于CMP的多种并行蚁群算法及比较[J]. J4, 2010, 48(05): 787-792.

HE Li-Chi, WANG Ke-Miao, BAI Hong-Chao, HU Cheng-Quan. Multi Parallel Ant Colony Optimization AlgorithmsBased on CMP and Their Comparison[J]. J4, 2010, 48(05): 787-792.