蚁群优化算法是意大利学者M.Dorigo受蚂蚁觅食行为的启发,提出的一种新型的模拟进化优化算法,具有正反馈,分布式计算等特点,为求解复杂的组舍优化问题提供了一种新的思路。本文在介绍蚁群算法基本原理的基础上,对蚁群优化算法提出了改进,最后在髑P问题上的应用表明改进算法具有良好的性能。

科技信息Ｏ计算机与信息技术Ｏ

ＳＣＩＥＮＣＥ＆ＴＥＣＩ刖ＯＬＯＧＹＩｈＴＯ孙伽０Ｎ

２００７年第３１期

毋

蚁群优化算法的原理及改进

冯宝华

（南昌大学信息工程学院自动化系江西南昌３３００３１）

【摘要】蚁群优化算法是意大利学者Ｍ．Ｄｏｒｉｇｏ受蚂蚁觅食行为的启发，提出的一种新型的模拟进化优化算法，具有正反馈，分布式计算等

特点，为求解复杂的组舍优化问题提供了一种新的思路。本文在介绍蚁群算法基本原理的基础上，对蚁群优化算法提出了改进，最后在髑Ｐ问

题上的应用表明改进算法具有良好的性能。

【关键词】蚁群优化算法；ＴＳＰ（旅行商问题）

即舱Ｔｈｅｏｒｙ

ａｎｄ

Ｉｍｐｒｏｖｅｍｅｎｔｏｆ

Ａｎｔ

ＣｏｌｏｎｙＡｌｇｏｒｉｔｈｍ

【Ａｂｓｔｒａｃｔ］ＡｎｔＣｏｌｏｎｙＯｐｔｉｍｉｚａｔｉｏｎＡｌｇｏｒｉｔｈｍ（ＡＣＯ）ｉｓａｎｅｗｋｉｎｄｏｆｓｉｍｕｌａｔｅｄｅｖｏｌｕｔｉｏｎａｒｙｏｐｔｉｍｉｚａｔｉｏｎａ１９０ｒｉｔｈｍｗｉｔｈｔｈｅｃｈａｒａｃｔｅｒｉｓｔｉｃｏｆｐｏｓｉｔｉｖｅｆｅｅｄｂａｃｋａｎｄｄｉｓｔｒｉｂｕｔｅｄｃｏｍｐｕｔａｔｉｏｎ，ｗｈｉｃｈｂｍｕ曲ｔｆｏｒｗａｒｄｂｙｔｈｅｓｃｈｏｌａｒｏｆＩｔａｌｙＭ．Ｄｏｒｉｇｏ．Ｉｔｐｍｖｉｄ髓ａｎｅｗｍｅｔｈｏｄｆｏｒｃｏｍｐｌｉｃａｔｅｄ

ｃｏｍｂｉｎａｔｏｒｉａｌｏｐｔｉｍｉｚａｔｉｏｎｐｒｏｂｌｅｍｓ．ＴｈｅｔｈｅｏｒｙｏｆＡＣＯａｒｅ

ａｎａｌｙｚｅｄ

ｉｎｔｈｉｓ

ｐａｐｅｒ．Ｓｕｇｇｅｓｔｉｏｎｓ

ａｒｅ

ｇｉｖｅｎｆｏｒｔｈｅｉｍｐｒｏｖｅｍｅｎｔｏｆＡＣＯ．Ａｔ

ｌａｓｔ．ｎｅ

ｒｅｓｕｌｔｓｏｆ

ａｐｐｌｉｃａｔｉｏｎｉｎ

７Ｉ．ｓＰＰｒｏｂｌｅｍｓｓｈｏｗｔｈａｔｉｔ

ｈａｓ

ｂｅｔｔｅｒｐｅｒｆｏｒｍａｎｃｅ．

【ＫｅｙＷｏｒｄｓ］ＡｎｔＣｏｌｏｎｙＯｐｔｉｍｉｚａｔｉｏｎＡｌｇｏｒｉｔｈｍ；ＴＳＰ

０．引言：蚁群算法是２０世纪９０年代初期由意大利学者Ｍ．１０只选择后者。这一过程一宣继续下去．最终所有的蚂蚁都将选择由Ｄｏｒｉｇｏ等人通过模拟自然界中蚂蚁集体寻食的行为而提出的（Ａｎｔ蚁穴至食物源的最短路径。

ＣｏｌｏｎｙＡｌｇｏｒｉｔｈｍ）／”。这是一种基于种群的启发式仿生类并行智能进化１．２基本模型为了便于理解。我们以求解平面上ｎ个城市的

算法。蚁群算法最早成功应用于解决Ｎ—Ｐ难题中著名的旅行商问题鸭Ｐ问题为例说明基本蚁群系统模型。首先引进如下符号：设ｍ是蚁

（ＴｒａｖｅｌｉｎｇＳａｌｅｓｍａｎＰｒｏｂｌｅｍ，简称巧Ｐ＇．由于它采用分布式并行计算机群中蚂蚁的数量；也“√＝１，２，…ｎ）表示城市ｉ和城市，之间的距离，研制，易于与其它方法结合，具有较强的鲁棒性。最近几年蚁群算法已被为凼的倒数，表示由城市ｉ转移到城市ｆ的期望程度，也称为启发式

陆续应用到许多优化领域。

因子州‘）表示ｔ时刻在路径｛『上的信息量。初始时刻，各条路径上的信

１．蚁群算法原理息量相等，设ｒ“ｏ）＝ｃ（ｃ为常数）。蚂蚁从某城市出发，按照状态转移规１．１基本原理自然界中像蚂蚁这样几乎没有视力的昆虫有很则选择下一个城市，该规则也被称为“随机比率规则”。下式给出了蚂多，他们是如何找到由其巢穴到食物源之最短路径的？生物学家经过蚁从城市ｉ转移到ｆ的转移概率。

长期大量细致的观察研究后发现：最初单个蚂蚁的行为是随机的。蚂，．ａ，“．．Ｊ

蚁在运动过程中会在其经过的路径上留下一种叫做外激素坼｛爨萧Ｊ，ｓＥｔａｂｕ（ｋ）

（Ｐｈｅｗｍｏｎｅ）信息物质。蚂蚁个体之间的信息传递就是依靠这种物质”【０否则

进行的。一方面。每只蚂蚁在其走过的线路上留下一定量的信息物质。式中，ｔｏｂｕｓ）（＆＝１，２，…ｍ）为ｔａｂｕ表，用以记录蚂蚁ｋ已经走过的且留在路径上的信息物质随时间逐渐衰减。另一方面，后来的蚂蚁能城市，它随着进化过程做动态调整，蚂蚁在后来的运动中不能选择那够感知这种外激素并以路径上残留信息量的多少指导其行为．信息量些已记录在ｔａｂｕ表中的城市：ｓ表示蚂蚁＾下一时刻所允许转移的城越大的路径，被选中的概率也越大。显然，蚁群搜索食物源的过程是信市，即不在ｔａｂｕ表中的城市；ｄ，Ｂ分别表示蚂蚁在运动过程中所积累息量的一个正反馈过程。据此，蚁群可以快速地找到由巢穴到食物源的信息及启发式因子在蚂蚁选择路径的过程中所起的不同作用。蚂蚁的最佳路径。图１所示为真实蚁群系统搜索食物时的路线示意图。图按照上述状态转移规则选择城市并最终形成一条封闭路径．当所有的中Ａ是蚁巢，Ｅ是食物所在的位置，ＨＣ为障碍物。

蚂蚁完成了它们的闭合路径后，即一次迭代结束，利用全局信息更新规则来更新路径的信息量，再开始下一次迭代直到达到最大迭代次数或最大停滞次数。

ＡＣＯ的全局信息更新规则如下：

７ｌ（ｔ＋ｎ）－－－ｐ．丁轴＋厶７ｔ

Ｈ

Ｃ

△铲∑蚴）

Ｉ＝Ｉ

州％）：ｆ静若蚂蚁走过路ｉｊ

【０

否则

其中：

ｐ一表示信息残留的程度，即旧的信息素相对于新增加的信息所占的比重。

图１

蚁群搜索食物路线示意图

Ｑ一取为常数，其值与吲ｏ）△吩＝ｏ有关。

厶一第ｋ只蚂蚁在本次循环中所走过的路径的长度。设Ｄ和Ｈ，Ｂ和Ｈ之间的距离均为２个单位．Ｄ与Ｃ、Ｂ与Ｃ之间的＾一当前迭代次数。ｍ一最大迭代次数。距离为１个单位，在一个时间单元内有３０只蚂蚁由Ａ到达Ｂ点．同样在每次迭代的初始时刻，设△昝＝０有３０只蚂蚁由Ｅ到达Ｄ点，蚂蚁运动的速度是１单位距离／单位时间．１．３基本蚁群优化算法优缺点

每只蚂蚁在其走过的路径上留下一个单位的信息量。假设初始时刻ｔ＿指数下降法确定基本蚁群算法的优点：

０时各条路径均无蚂蚁走过，位于Ｂ和Ｄ点的各３０只蚂蚁选择所走１）较强的鲁棒性：蚁群优化算法虽是基于ＴＳＰ提出的，但只需对路线的概率是相同的，按照统计规律，即有１５只蚂蚁选择ＤＨ（ＢＨ）．另该模型稍加修改，便可应用于其他问题；

外１５只选择路径（ＢＣ）。由ｄ（ＤＨ）＝ｄ（ＢＨ）＝２ｄ（ＤＣ）＝２ｄ（ＢＣ），所以经过１个２）分布式计算：蚁群优化算法是一种基于种群的进化算法，具有单位时间后，走过路径ＢＣ和ＤＣ的蚂蚁个数是走过ＢＨ、ＤＨ蚂蚁个数本质并行性，易于并行实现。

的两倍。这些蚂蚁留在路径上的信息量前者也是后者的２倍。在ｔ＝ｌ基本蚁群算法的不足之处：

时，新的３０只蚂蚁位于Ｂ点和Ｄ点，根据信息量的多少，他们选择路径搜索时间较长；易出现停滞现象，即搜索到一定程度后．所有个体ＤＣ（ＢＣ）的概率是选择ＤＨ（ＢＨ）的两倍，即有２０只蚂蚁选择前者，而只有

发现的解完全一致，不能对解空间进一步进行搜索，容易限于局部最

万　

方数据