作者投稿和查稿 主编审稿 专家审稿 编委审稿 远程编辑

计算机工程 ›› 2010, Vol. 36 ›› Issue (19): 200-202. doi: 10.3969/j.issn.1000-3428.2010.19.070

• 人工智能及识别技术 • 上一篇    下一篇

基于MPI的并行最大最小蚂蚁系统

刘彩云a,陈 忠a,熊 杰b   

  1. (长江大学 a. 信息与数学学院;b. 电子信息学院,湖北 荆州 434023)
  • 出版日期:2010-10-05 发布日期:2010-09-27
  • 作者简介:刘彩云(1975-),女,副教授、硕士,主研方向:并行计算;陈 忠,教授、博士;熊 杰,讲师、硕士
  • 基金资助:
    国家自然科学基金资助项目“基准面旋回理论解析与定量层序地层模型”(40572078);国家“118”专项基金资助子项目“天然气水合物资源综合评价软件研制与开发”(GZH200200202-3)

Parallel Max-Min Ant System Based on MPI

LIU Cai-yuna, CHEN Zhonga, XIONG Jieb   

  1. (a. School of Information and Mathematics; b. School of Electronics and Information, Yangtze University, Jingzhou 434023, China)
  • Online:2010-10-05 Published:2010-09-27

摘要: 现有蚁群系统在求解大规模组合优化问题时所需的计算时间较长。针对该不足,提出基于消息传递接口的粗粒度异步协作并行最大最小蚂蚁系统,能在保证解质量的前提下,降低并行计算中的通信开销。在曙光4000L并行机上进行的数值实验结果表明,该系统具有较优的并行加速比和加速效率,且适合于大规模TSP问题的求解。

关键词: 并行最大最小蚂蚁系统, 消息传递接口, 部分异步并行实现, 粗粒度, 多蚁群协作

Abstract: Existing Colony system for the large scale optimization combination problem needs long computation time. Aiming at this shortage, this paper presents coarse grained asynchronous parallel implementation Parallel Max-Min Ant System(PMMAS) based on Message Passing Interface(MPI) which can reduce the cost of communication of parallel computation and guarantee the quality of solution. Numerical experiment result which is obtained on the dawn 4000L parallel computer indicates that the system has well speedup and speedup efficiency, and it is suitable for large-scale under the prerequisite of solving Traveling Salesman Problem(TSP).

Key words: Parallel Max-Min Ant System(PMMAS), Message Passing Interface(MPI), Partially Asynchronous Parallel Implementation(PAPI), coarse grained, multi-ant colony collaboration

中图分类号: