基于异构平台的并行最大最小蚁群算法

来源：同济大学学报·自然科学版杂志2016年第12期北京时间：

作者：黄震华

单位：同济大学电子与信息工程学院 上海 200092,同济大学电子与信息工程学院 上海 200092,同济大学电子与信息工程学院 上海 200092

摘要：最大最小蚂蚁系统（Maxmin Ant System，MMAS）是一种性能优良的启发式算法，常用于解决组合优化问题.当解决的目标问题规模较大、迭代轮次较多时，最大最小蚁群算法存在运行时间长的缺点.试验以开源串行包ACOTSP为基准，利用GPU多线程并发的优势，采用并行蚂蚁策略将MMAS在CPUGPU协同异构计算平台上并发实现.算法在GPU上运行时的影响因素，如数据传输、内存层次、库函数调用等,也得到有效分析，并作出针对性优化.试验最终取得了高达13倍的加速，表明并行MMAS策略具有高效性和实用性.

关键词：并行计算, 异构平台, 最大最小蚁群系统, 加速比

基金资助：国家自然科学基金(61272268)；上海市青年科技启明星计划 (15QA1403900)；霍英东教育基金会高等院校青年教师基金(142002)；教育部新世纪优秀人才支持计划(NCET-12-0413)；同济大学中央高校基本科研业务费专项资金。