基于MPI的并行蚁群算法的实现

2012-04-29 02:38:49曹明甘云王胜炎刘文佑邓盼文彭东海
电脑知识与技术 2012年12期
关键词:蚁群算法

曹明 甘云 王胜炎 刘文佑 邓盼文 彭东海

摘要:蚁群算法是新兴的仿生进化算法,具有并行计算、正反馈等特点,与其它各种启发式算法相比该算法具有明显的优越性。该文将实现蚁群算法的并行化,并用来求解TSP问题,结果证明能显著提高蚁群算法的收敛速度。

关键词:蚁群算法;并行;TSP;MPI

中图分类号:TP18文献标识码:A文章编号:1009-3044(2012)12-2863-02

1蚁群算法

蚁群算法是在现实世界的蚁群行为的基础上提出来的。现实世界中的各种蚂蚁、蜜蜂等有群居习惯的昆虫,个体昆虫行为虽然很简单,但是由数量众多的个体所组成的群体却能显现出相当复杂有序的群体行为[1-3]。科学家通过仔细的观察发现,蚂蚁和蚂蚁之间经过信息素等自身分泌的物质进行消息传递。运动中的蚂蚁可以在走过的路径上留下信息素,并且这种信息素能影响其他蚂蚁对路径的选择,这样信息素就对蚁群行为的影响形成所谓的正反馈现象[4],该条路径走过上的蚂蚁越多,信息素浓度就越高,后面的蚂蚁选择该路径的可能性就越大。蚂蚁和蚂蚁之间能够通过这种信息素的交流,找到一条从蚁巢到达食物的最短路径。

2并行蚁群算法

关于并行蚁群算法文献[5]中提出PAPI算法,该算法中为了减少处理器之间通信次数,从而增加处理器用于计算的事件,采取了让蚁群在运行固定次数之后才进行信息素的交流办法,得到了比较好的加速比。文献[6]中使用了一种最简单的并行蚁群算法,各蚁群在运算时候没有信息交流,这样各个蚁群之间是独立进行的,并且实现了MMAS蚁群算法,从算法结果上来看,该方法体现了一定的效率。文献[7]中对ACS做了并行实现,使用的是数据并行的方法,把一个蚁群中的所有蚂蚁平分为q个子蚁群,然后使用q个处理器来并行计算,所有的子蚁群都有自己的数据结构,使用的是相同的蚁群算法,该算法使用了局部和全部的信息素更新方法,在一定的迭代次数后利用蚁群搜索到的最好路径对信息素矩阵进行更新。

2.1并行蚁群基本思路

蚁群算法并行化的基本思路是把n只蚂蚁分为numprocs个蚁群,每个蚁群分配1个处理机。每个子蚁群中的蚂蚁个数可以相等,也可以不相等,如果处理机性能相同,一般令各子蚁群的蚂蚁个数相等。初始化完成后,由每个蚁群分别进行解的搜索,根据并行策略进行蚁群之间的通信,每个蚁群根据从其它蚁群获取的有关信息,对本蚁群的状态进行修改。当达到算法的终止条件时,由其中1个处理机收集各蚁群的最优解,并输出所找到的全局最优解。

2.2并行蚁群算法描述

BEGIN

系统初始化;

1)初始化MPI库,使用MPI_Comm_rank()

获取进程号myid,MPI_Comm_size()获取

参与计算的进程数numprocs;

2)蚂蚁总的数量初始化为n,蚁群的迭代次数为D;

3)设置蚁群算法的基本参数;

4)各个蚁群进程中设置每只蚂蚁的初始位置;

5)初始化最优路径长度;

WHILE(蚁群迭代次数

1)FOR(i=myid*n/numprocs;i<(myid+1)*m/ numprocs;i++)

2)搜索禁忌表初始化;

3)搜索禁忌表中没有的节点;

①根据概率来选择节点;

②蚂蚁移动到选择的节点,然后在搜索禁忌表中增加该节点;

③利用局部信息素更新方法来更新路径上的信息素;

4)蚂蚁随机分配到一个起始节点;

5)利用局部信息素更新方法,对蚂蚁所走过的各条路径上的信息素作局部调整; END FOR

6)查找在本次循环中蚁群搜索到的最优路径,更新全局最优路径;

7)利用全局信息素更新方法对最优路径上的信息素做更新;

8)使用MPI_Barrier()函数的路障机制对集合中的进程同步;

9)使用MPI_Reduce()函数的规约操作来收集局部进程中的最优路径信息;

10)使用MPI_Bcast()函数进行广播操作统一局部进程中的最优路径信息;

END WHILE

使用MPI_Reduce()函数的规约操作来得到当前进程集合中的搜索到的最优路径;输出最短路径的城市顺序和长度;

END

3算法实现

以湖南人文科技学院曙光TC4000超级计算机群为运行平台。曙光TC4000是基于Linux的超级服务器系统,由1个管理登陆节点、10个计算节点共65个节点组成,节点全部采用64位双路六核CPU架构势。软件环境是Linux Suse 10sp2,并行开发环境为MPI,编译环境为C。

为了验证并行算法的效率,使用来自于国际通用的TSP数据库TSPLIB中的Ei151, Ei176,Eil101这3个实例,分别用并行蚁群算法和串行蚁群算法程序在曙光TC4000上运行30次,得到各项数据的平均值,如表1所示。

从表1我们可以看到,并行蚁群算法能显著加快收敛速度,减少执行时间;3个实例的结果都得到了较为理想的加速比,而且,随着问题规模不断的扩大,加速比逐渐提高。

但是也看到算法得到的结果与TSPLIB公布的最优解还有一定的差距,并行蚁群算法的效率有待于进一步的提高,以后的工作将要从并行的策略入手,提出改进措施来解决蚁群容易陷入局部最优的问题。

参考文献:

[1] Kennedy J, Eberhart R C.Swarm Intelligence.San Francisco, CA: Morgan Kaufmann Publishers, 2001.

[2] Bonabeau E, Dorigo M, Theraulaz G.Swarm Intelligence: From Natural to Artificial Systems.Santa Fe Institute in the Scien- ces of the Complexity,Oxford University Press,New York, Oxford,1999.

[3] Bonabeau E, Dorigo M, Theraulaz G.Inspiration for optimizati- on from social insect behaviour,Nature, 406:39-42, July 2000.

[4] Dorigo M,Maniezzo V, Colomi A.Positive feedback as a sea- rch strategy,Technical Report 91-016, Dipartimento di Elettr- onica,Politec nico di Milano,Italy,1991

[5] Bullnheimer G.Kotsis, Strauss C.Parallefization strategies for the ant system.Applied Optimization 1998,24:87-100.

[6] Stutzle T,Parallefization strategies for ant colony optimiza- tion. Lecture Notes in Computer Science 1998 (1498),722- 741.

[7]陈峻,沈洁.基于分布均匀度的自适应蚁群算法.软件学报,2003,14(08):1379-1387.

猜你喜欢
蚁群算法
测控区和非测控区并存的配电网故障定位实用方法
遗传模拟退火算法
价值工程(2016年36期)2017-01-11 09:20:00
CVRP物流配送路径优化及应用研究
软件导刊(2016年11期)2016-12-22 21:53:31
云计算中虚拟机放置多目标优化
软件导刊(2016年11期)2016-12-22 21:30:28
基于蚁群算法的一种无人机二维航迹规划方法研究
蚁群算法基本原理及综述
一种多项目调度的改进蚁群算法研究
科技视界(2016年18期)2016-11-03 00:32:24
能量高效的WSN分簇路由协议研究
蚁群算法求解TSP中的参数设置
蚁群算法聚类分析研究