蚁群算法的三种并行模型分析  

Analysis on Three Parallel Models of Ant Colony Algorithm

作　　者：王磊[1] 曹菡[1] 王长缨[2] 

机构地区：[1]陕西师范大学计算机科学学院,西安710062 [2]福建农林大学计算机与信息学院,福州350002

出　　处：《计算机工程》2011年第12期170-172,175,共4页Computer Engineering

基　　金：陕西师范大学研究生培养创新基金资助项目(2010CXS012)

摘　　要：在单机多核下分别构造基于OpenMP和MPI的并行蚁群算法模型,在多核集群机下构造基于MPI和MPI+OpenMP的并行蚁群算法模型,并提出动态蚁群择优策略及分段周期交流策略。基于实际路网的路径寻优问题对上述模型进行比较,实验结果表明,在单机多核下,基于MPI的模型与基于OpenMP的模型相比,运行时间短,加速比高,在多核集群机下,基于MPI+OpenMP的混合模型相比基于MPI的模型,在进程数较多时仍具有较高的加速比。This paper constructs parallel model based on Open Multi-processing（OpenMP） and parallel model based on Message Passing lnterface（MPI） in multi-core environment, and constructs parallel model based on MPI and parallel model based on MPI＋OpenMP in the multi-core clusters. The preferred strategy of dynamic ant colony and the strategy of sub-cycle exchange are presented. Finding optimized path of road is used to compare the three models. Experimental results show that MPl-based model run faster and get higher speedup than OpenMP-based model. In multi-core environment, hybrid model of MP1＋OpenMP gets higher speedup than MP1-based model with more processes.

关 键 词：蚁群算法 多核 集群机 并行模型 信息交流策略 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]