摘要
基于片上多核处理器(Chip Multi-processor,CMP)的多种并行蚁群算法,包括并行最大最小蚂蚁系统、并行蚁群系统及两者的混合等5个并行算法,提出一种在CMP的每个处理器核心上模拟一个子蚁群,整体蚁群共享同一信息素矩阵,实现信息素隐式交流的方法.用多线程实时优先级实现该算法,并用若干旅行商问题实例进行了测试,分析了不同并行策略的影响.测试结果表明,基于CMP的并行蚁群具有相对于核心数目的线性加速比,异种蚁群混合策略在解的稳定性上更具优势。
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.
出处
《吉林大学学报（理学版）》
CAS
CSCD
北大核心
2010年第5期787-792,共6页
Journal of Jilin University:Science Edition
基金
国家自然科学基金(批准号:60873207
60433020)
关键词
蚁群优化
共享信息素矩阵
并行计算
片上多核处理器
ant colony optimization
sharing one pheromone matrix
parallel computing
chip multiprocessor
