蚁群算法原理简介及伪代码实现

摘要：自1992年Marco Dorigo提出蚁群算法以来，蚁群算法得到了快速发展，并广泛应用于车辆调度问题、车辆路径问题、分配问题、子集问题、网络路由问题蛋白质折叠问题、数据挖掘、图像识别、系统辨识等。

关键词：智能算法；蚁群算法；模式识别

中图分类号：TP311 文献标识码：A 文章编号：1009-3044（2014）10-2353-03

蚁群算法是一种近年来快速发展起来的一种智能算法。这种算法由Marco Dorigo于1992年提出，其灵感源于蚁群在寻找食物的过程中总是能找到一条从食物到蚁穴之间的最短或最优路径这一现象。蚁群算法具有鲁棒性强、全局搜索、并行分布式计算、易于与其它问题结合等优点。广泛应用于车辆调度问题、车辆路径问题、分配问题、子集问题、网络路由问题蛋白质折叠问题、数据挖掘、图像识别、系统辨识等。

1 蚂蚁的觅食策略―不等长双桥实验

下图表示蚂蚁觅食时选择行走路径的过程，图1 （a）为蚂蚁选择不同的路径觅食；图1 （b）显示绝大多数蚂蚁选择了最短的路径；最终有80%以上的蚂蚁最终选择了最优路径如图1 （c）显示。

该结果的原因是蚂蚁能够分泌并感知一种信息素，以进行信息传递。蚂蚁会在途经的路径上留下这种信息素，其它蚂蚁和自身都能够感知这种信息素，并以此指导自己的运动方向。在该实验中，选择最短的路径的蚂蚁先回蚁巢，这样在最短路径会有更多的信息素，从而诱使蚁穴中其它蚂蚁选择短路径，因此蚁群集的体行为便表现出一种信息正反馈现象。

大量蚂蚁的集体行为主要有三点：

1）正反馈： 这是基于信息素的释放和感知来实现的。某一路径上走过的蚂蚁越多，信息素就越浓，诱使其它蚂蚁选择短路径，从而能快速发现最优的解。

2） 负反馈： 负反馈是基于信息素的挥发来实现的。信息素的浓度随着时间的推移不断下降，从而避免某些路径上信息素过多，使算法早熟，陷入局部最优解。

3） 启发式信息： 在蚁群算法中构造一个启发信息，它有助于通过搜索过程找到可行解。

2 蚁群算法―商旅问题

蚁群智能算法中把具有简单功能的工作单元看作蚂蚁，即构造人工蚂群，来优先选择信息素浓度大的路径，来解决最优化问题。 人工蚁群具有一定的记忆能力；同时，人工蚁群在选择下一条路径的时候并不是盲目的，而是按一定算法规律有意识地寻找最短路径。例如在TSP问题（Travelling Salesman Problem 商旅问题）中，当前城市到下一个城市的距离可以预先知道。

nTSP问题引入

比如有一位商人，他想访问中国的某些城市，要求：

1） 所走路程最近。

2） 每个城市只能访问一次。

3） 从某城市出发，最后回到该城市。

nTSP问题引入原因：

1） 直观，易理理。

2） TSP是典型的组合问题，常用来验证一些算法的有效性。

3） 蚁群算法很适合这类最短路径问题问题。

n蚂蚁具有的特征：

1） 在从城市i到j的过程中在边（i，j）上释放信息素。

2） 禁止蚂蚁重复访问城市。

3） 访问下一个城市的概率是两城市间和连接两城市的路径上存有轨迹量的函数。

简单蚂蚁算法的流程图：

1） 蚁群A（t）初始化。

2） 对每只蚂蚁的适应度做评价。

3） 对蚂蚁所经历的路径按照一定的比例释放信息素。

4） 根据路径的信息素浓度和自己的判断选择合适的路径。

5） 信息素浓度会随着时间不断下降。

其中，信息素的浓度用[Q]表示，它是一个常数；第[k]只蚂蚁在本次循环中所走过的路径的总长度用[Lk]表示。

3 TSP问题蚁群算法伪代码实现

伪代码（Pseudocode）是一种算法描述语言。使用伪代码的目的是为了使被描述的算法可以容易地以任何一种编程语言（Pascal，C，Java，etc）实现。因此，伪代码必须结构清晰、代码简单、可读性好，并且类似自然语言。

Proceure AS

for each edge

set initial pheromone value t0

end for

while not stop

for each ant k

randomly choose an initial city

for i=1 to n

choose next city with probability

end for

end for

compute the length Ck of the tour constructed by the kth ant

for each edge

update the pheromone value

end for

end while

print result

end procedure

参考文献：

[1] 杜立峰，牛永洁. 蚁群算法在MATLAB中的实现.信息技术[J].2011（6）：115-118.

[2] 张丽，刘希玉，李章泉.基于蚁群算法的聚类优化[J].计算机工程，2010，36（9）：90-192.

[3] 朱峰，陈莉.一种改进的蚁群聚类算法[J].算机工程与应用，2010，45（6）：33-135.

[3] 程晔.基于蚁群优化神经网络的比较购物模型研究[D].安徽理工大学，2010.

[4] 刘志刚基于敏捷模式的生产车间计划与调度系统研究[D].西安理工大学，2006.

[5] 改进蚁群算法在乳品企业原奶车辆运输路径中的应用研究[D].东北农业大学， 2006.

[6] 杨丽.基于低压载波电力线数据传输协议的研究[D].华北电力大学（河北），2008.

[7] Dorigo M，Maniezzo V，Colomi A.Ant system：optimization by a col― ony of cooperating agents[J].IEEE Transactions on SMC，1996，26 （1）：12-41.

[8] Dofigo M，Gambardella L M.Ant colony system：a cooperative learning approach to the traveling salesman problem[J].IEEE Transactions on Evolutionary Computing，1997（1）：53-66.