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

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

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

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

1蚁群算法

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

2并行蚁群算法

关于并行蚁群算法文献[5]中提出PAPI算法，该算法中为了减少处理器之间通信次数，从而增加处理器用于计算的事件，采取了让蚁群在运行固定次数之后才进行信息素的交流办法，得到了比较好的加速比。文献[6]中使用了一种最简单的并行蚁群算法，各蚁群在运算时候没有信息交流，这样各个蚁群之间是独立进行的，并且实现了MMAS蚁群算法，从算法结果上来看，该方法体现了一定的效率。……