蚁群算法及其应用研究进展(2)

第８期

倪庆剑等：蚁群算法及其应用研究进展

１３

径的蚂蚁越来越多，使得短路径上的信息素的强度越发大于较长路径上的信息素强度，从而使得后续的蚂蚁以较大的概率选择短路径，这种自身催化过程形成的信息正反馈机制使得蚁群最终可以找到新的最短路径。

１．２蚁群算法的基本原理

蚁群算法是通过模拟真实蚁群的觅食机理求解优化问题的，最早是Ｄｏ＾ｇｏ口。等提出的蚂蚁系统，被用来解决旅行商问题，后来经过Ｄｏｒｉｇｏ和Ｇａｍｂａｒｄｅｌｌａ等’４刮人的改进后称为蚁群算法（Ａｎｔ

ｃｏｌｏｎｙ

Ａｌｇ耐ｔｈｍ）或蚁群优化算法（Ａｎｔ

ｃｏｌｏｎｙ０ｐＩｉｍｉ—

ｚａｔｉｏｎ

Ａｌｇｏｒｉｔｈｍ）。

蚁群算法模拟真实蚁群的觅食机制”１，引入了信息素概念及相关的信息素更新机制。但与真实蚁群中的蚂蚁不同，蚁群算法中的蚂蚁被赋予了部分记忆，并且可以感知某些启发信息，这种记忆并非存储于蚂蚁个体，而是分布在路径上。蚁群通过感知路径上的信息素进行通信。蚂蚁之间的这种间接通信方式称为Ｓｔｉｇｍｅｒｇ），机制，个体之间并不直接进行信息交互，而是通过改变它们共同存在的环境进行交互，个体又通过对环境的改变去影响其它个体的行为，从而形成了一种正反馈机制。

蚁群算法最初被应用于对称旅行商问题（ｓｙｍｎｌｅｔｒｉｃＴｓＰ），下面以文献［５］中提出的蚁群系统求解对称旅行商问题说明蚁群算法的基本原理。

经典的对称旅行商问题简单描述如下：任给ｎ个城市ｙ＝ｈ，”：，…，％｝，ｎ个城市之间的边的集合Ａ＝｛（ｒ，ｓ）：ｒ，ｓ

Ｅ

ｌ，｝，

城市ｒ和ｓ的Ｅｕｃｌｉｄｅａｎ距离为６（ｒ，ｓ），６（ｒ，５）为边（ｒ，ｓ）的长度，这里占（，，ｓ）＝占（ｓ，，）。旅行商问题就是在有向图Ｇ（Ｉ，，Ａ）中

寻找一条长度最短的Ｈ锄ｉｌｔｏｎ回路，也就是寻找一条遍历所有

ｎ个城市有且仅有一次最后回到出发城市的最短路径。

在应用蚁群算法解决对称旅行商问题时。每一条边（ｒ，ｓ）都有一个信息素强度值ｒ（ｒ，ｓ），它由蚁群算法的信息索局部更新规则和全局更新规则进行更新。

蚁群算法的工作过程简单描述如下：将ｍ个蚂蚁按照某种初始化规则分布在凡个城市，然后每个蚂蚁根据状态转移规则选择遍历的城市，蚂蚁倾向于选择那些长度较短且信息素强度较高的路径。单个蚂蚁在遍历过程中根据信息素局部更新规则在路径上释放一定数量的信息素，同时蚂蚁经过路径上的信息素随着时间的推移而蒸发。当所有的蚂蚁都完成了它们的遍历过程之后，每个蚂蚁都建立了一条Ｈａｍｉｌｔｏｎ回路，这条回路就是单个蚂蚁找得的旅行商问题的解。此时可以计算出此次迭代的最短路径，再应用信息素全局更新规则对获得最短路径的蚂蚁所经历的边上的信息素进行更新。此后算法反复迭代直至满足终止条件后结束。可见，蚁群算法的求解过程主要由三个规则控制，即状态转移规则，信息素全局更新规则，信息素局部更新规则。

（１）状态转移规则位于城市ｒ的蚂蚁通过状态转移规则

选择要访问的城市。

５＝｛

ｆａｒ舯ａ）【吲Ｉ（，）｛［ｆ（，，“）］．［叼（ｒ，Ⅱ）川

ｉｆ

ｇ≤％…

Ｌｌ，

【Ｓ

ｏｔｈｅｎｖｉ∞

式（１）中＾（ｒ）表示蚂蚁盂在当前位置ｒ能访问的城市的集合，蚂蚁被赋予了记忆能力，可以记录蚂蚁已经过的城市，这种

记忆一般通过设置禁忌表来实现。可＝÷，是城市间距离的倒

。

数，表达了启发式信息。口（口＞０）是描述状态转移时信息素和

万方数据

启发式信息（距离）相对重要性的参数。ｑ是服从均匀分布的［０，１］之间的随机数，％是一个参数（０≤９０≤１）。Ｓ是由式（２）给出的概率分布选出的一个随机变量。

ｍ（¨）：？；、［下（Ⅲ）］．［，７（Ⅲ）］９…～”…

“㈧：ｆ岩黑踹ｍ圳ｒ，

ｒ：纛沁

（２）

由式（１）和（２）决定的状态转移规则被称为伪随机比例规则（Ｐｓｅｕｄｏ—Ｒａｎｄｏｍ．ＰｒｏｐｏｎｉｏｎａｌＲｕｌｅ）。状态转移规则使得蚂蚁倾向于选择短的且信息素强度高的路径。参数ｑ。决定了“勘探”（探索问题未知解空间以寻找那些可能最优的区域）和“开采”（充分利用已有的有效信息寻找可能最优的区域）之间的相对重要性：当位于城市ｒ的蚂蚁选择下一个将要访问的城市时，它选择一个随机数０≤ｇ≤ｌ，如果ｑ≤ｑｏ，则根据启发信息和信息素强度取最好的边，否则按照式（２）的随机比例规则选一条边。

（２）信息素全局更新规则

蚁群算法中只有那些属于最短

路径上的边的信息素才被得到增强。这种规则和伪随机比例规则的使用都是为了让算法的寻优过程更具有指导性：最短路径的寻找始终是在当前找到的最短路径的附近进行。在所有的蚂蚁遍历完凡个城市之后，按照式（３）进行全局更新。

ｒ（ｒ，３）＋－（１一ｎ） 下（ｒ，ｓ）＋ａ △丁（ｒ，ｓ）

（３）

△ｆ（，。５）：』‘ｔａ）’１，ｉ‘（７，５）∈ｇ幻６口‘一６部‘一幻盯

（４）

【Ｏ，ｏｔｈｅｒｗｉｓｅ

口是信息素的蒸发系数。ｋ是实验开始至今的全局最短路径长度，也有用此次迭代得到的最优路径的长度￡。。来代替ｋ的。实验表明这两种情况下算法的性能差别较小，取ｋ的性能

略微占优”Ｊ。

（３）信息素局部更新规则单个蚂蚁在遍历的过程中应用

信息索局部更新规则对它所经过的边按照式（５）进行信息素更

新。

ｒ（ｒ，ｓ）＋－（１一ｐ） ｒ（ｒ，ｓ）＋ｐ △ｆ（ｒ，ｓ）

（５）

式（５）中，ｐ为参数，Ｏ＜ｐ＜１。实验表明，取△７Ｉ（ｒ，５）＝ｙ ⅡＩａ】【；。』＾（，）＿ｒ（ｓ，：）（Ｏ≤ｙ＜１为参数）及△丁（ｒ，ｓ）＝ｒｏ（ｆｏ为路径的初始信息素量）时算法效果较好∞１。局部更新规则使得被蚂蚁经过的路径减少了一部分信息素，使得这些边被后来的蚂蚁经过的可能性减少，增强了算法的“勘探”能力，从而有效避免算法进入停滞状态（所有的蚂蚁收敛到同一路径）。

总之，蚁群算法先通过状态转移规则选择蚂蚁下一步将访问的城市，在建立解的过程中应用信息素局部更新规则更新经过的路径上的信息素，在遍历所有城市之后，根据信息素全局更新规则对所有的路径上的信息素进行更新。蚁群算法的改进及其理论研究

蚁群算法的理论研究主要集中在如下几个方面：蚁群算法

的参数设置，蚁群算法的改进，蚁群算法收敛性及工作机制的研究，蚁群算法与其它算法的融合。

蚁群算法的参数设置对蚁群算法的性能有着重要的影响。总的来说，蚁群算法中的参数包括初始蚁群中蚂蚁的数目ｍ，式（１）和（２）中的卢和９０，式（３）中的ａ，式（５）中的ｐ和下。等等。

２

２．１蚁群算法参数设置的研究