| 基于CMP的多种并行蚁群算法及比较 |
| |
| 引用本文： | 何丽莉,王克淼,白洪涛,胡成全.基于CMP的多种并行蚁群算法及比较[J].吉林大学学报(理学版),2010,48(5):787-792. |
| |
| 作者姓名： | 何丽莉 王克淼 白洪涛 胡成全 |
| |
| 作者单位： | 吉林大学 计算机科学与技术学院, 长春 130012,吉林大学 符号计算与知识工程教育部重点实验室, 长春 130012 |
| |
| 摘 要： | 基于片上多核处理器(Chip Multi-processor,CMP)的多种并行蚁群算法,包括并行最大最小蚂蚁系统、并行蚁群系统及两者的混合等5个并行算法,提出一种在CMP的每个处理器核心上模拟一个子蚁群,整体蚁群共享同一信息素矩阵,实现信息素隐式交流的方法.用多线程实时优先级实现该算法,并用若干旅行商问题实例进行了测试,分析了不同并行策略的影响.测试结果表明,基于CMP的并行蚁群具有相对于核心数目的线性加速比,异种蚁群混合策略在解的稳定性上更具优势。
|
| 关 键 词： | 蚁群优化 共享信息素矩阵 并行计算 片上多核处理器 |
| 收稿时间： | 2009-08-23 |
Multi Parallel Ant Colony Optimization Algorithms Based on CMP and Their Comparison |
| |
| HE Li-li,WANG Ke-miao,BAI Hong-tao,HU Cheng-quan.Multi Parallel Ant Colony Optimization Algorithms Based on CMP and Their Comparison[J].Journal of Jilin University: Sci Ed,2010,48(5):787-792. |
| |
| Authors: | HE Li-li WANG Ke-miao BAI Hong-tao HU Cheng-quan |
| |
| Institution: | 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 |
| |
| Abstract: | Multi parallel ant colony optimization algorithms basedon 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 byseveral 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 inthe stability of solutions. |
| |
| Keywords: | ant colony optimization sharing one pheromone matrix parallel computing chip multiprocessor |
| 本文献已被 CNKI 万方数据 等数据库收录！ |
| 点击此处可从《吉林大学学报(理学版)》浏览原始摘要信息 |
| 点击此处可从《吉林大学学报(理学版)》下载免费的PDF全文 |
|
