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

摘要

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