蚁群算法

1. 蚁群算法的原理

蚁群算法是对自然界蚂蚁的寻径方式进行模似而得出的一种仿生算法。蚂蚁在运动过程中，能够在它所经过的路径上留下一种称之为外激素(pheromone)的物质进行信息传递，而且蚂蚁在运动过程中能够感知这种物质，并以此指导自己的运动方向，因此由大量蚂蚁组成的蚁群集体行为便表现出一种信息正反馈现象：某一路径上走过的蚂蚁越多，则后来者选择该路径的概率就越大。

为了说明蚁群算法的原理，先简要介绍一下蚂蚁搜寻食物的具体过程。在蚁群寻找食物时，它们总能找到一条从食物到巢穴之间的最优路径。这是因为蚂蚁在寻找路径时会在路径上释放出一种特殊的信息素。当它们碰到一个还没有走过的路口时．就随机地挑选一条路径前行。与此同时释放出与路径长度有关的信息素。路径越长，释放的激索浓度越低.当后来的蚂蚁再次碰到这个路口的时候．选择激素浓度较高路径概率就会相对较大。这样形成一个正反馈。最优路径上的激索浓度越来越大．而其它的路径上激素浓度却会随着时间的流逝而消减。最终整个蚁群会找出最优路径。

蚂蚁从A点出发，速度相同，食物在D点，可能随机选择路线ABD或ACD。假设初始时每条分配路线一只蚂蚁，每个时间单位行走一步，本图为经过9个时间单位时的情形：走ABD的蚂蚁到达终点，而走ACD的蚂蚁刚好走到C点，为一半路程。

本图为从开始算起，经过18个时间单位时的情形：走ABD的蚂蚁到达终点后得到食物又返回了起点A，而走ACD的蚂蚁刚好走到D点。

假设蚂蚁每经过一处所留下的信息素为一个单位，则经过36个时间单位后，所有开始一起出发的蚂蚁都经过不同路径从D点取得了食物，此时ABD的路线往返了2趟，每一处的信息素为4个单位，而 ACD的路线往返了一趟，每一处的信息素为2个单位，其比值为2：1。

寻找食物的过程继续进行，则按信息素的指导，蚁群在ABD路线上增派一只蚂蚁（共2只），而ACD路线上仍然为一只蚂蚁。再经过36个时间单位后，两条线路上的信息素单位积累为12和4，比值为3：1。

若按以上规则继续，蚁群在ABD路线上再增派一只蚂蚁（共3只），而ACD路线上仍然为一只蚂蚁。再经过36个时间单位后，两条线路上的信息素单位积累为24和6，比值为4：1。

若继续进行，则按信息素的指导，最终所有的蚂蚁会放弃ACD路线，而都选择ABD路线。这也就是前面所提到的正反馈效应。

2. 蚁群算法与TSP问题

初始的蚁群算法是基于图的蚁群算法，graph-based ant system,简称为GBAS，是由Gutjahr W J在2000年的Future Generation Computing Systems提出的，课本的参考文献2。算法步骤如下：

STEP 0 对n个城市的TSP问题，

N{1,2,...,n} A{(i ,j)| i,jN}ij(i,j ) 赋信息素初值 ( 0 ) 1 | ，假设m只蚂蚁在工作，| A所有蚂蚁都从同一城市 出发。当前最好解是 w  (1,2,,n)

城市间的距离矩阵为 d ij ) n  n ，给TSP图中的每一条弧 (STEP 1 （外循环）如果满足算法的停止规则，则停止计算并输出计算得到的最好解。否则使蚂蚁s从起点 i 0 出发，用 L (s ) 表示蚂蚁s行走的城市

 s集合，初始 L ( s ) 为空集， 1  m 。

STEP 2 (内循环) 按蚂蚁L ( s ) N 的顺序分别计算。当蚂蚁在城市i，若

( s, l  L )  N 或 { l | ( i , l )  A L ( s )} 完成第s只蚂蚁的计算。否则，若

L(s)N且T{l|(i,l)A,lL(s)}{i0}(k1) ，则以概率 pij  ij ,j T ， pij0,jTij(k1)到达j， l T 若 L(s)N且T{l|(i,l)A,lL(s)}{i0}L(s)L(s){j},i:j

则到达 i 0,L (s)  L ( s ) { i0 }, i :  i 0 ; 重复STEP 2。

STEP 3 对 1 s  ，若 L ( s ) N ，按 L ( s ) 中城市的顺序计算路径程度；m若 ( s )  N ，路径长度置为一个无穷大值（即不可达）。比较m只蚂蚁中的路径长度，L记走最短路径的蚂蚁为t。

若 f ( L ( t ))  f ( ( W )) ，则 记 W  L ( 。用如下公式对W路径 t )L上的信息素痕迹加强，对其他路径上的信息素进行挥发。 k1(k)(1)(k1)(i,j)为W上的一条弧ijk1ij W (k)(1)(k1)(i,j)不是W上的一条弧k1ijij

得到新的 ( ，重复步骤STEP 1。

ijk),k:k1

在STEP 3 中，挥发因子 对于一个固定的 K  1 ，满足

lnk

1,kKk ln(k1) 并且  kk1

经过k次挥发，非最优路径的信息素逐渐减少至消失。

3.初始的蚁群优化算法—基于图的蚁群系统（GBAS） 可以验证，下式满足：

,k0ij(k)1

(i,j)A

即 是一个随机矩阵。

四个城市的非对称TSP问题，距离矩阵和城市图示如下：

010.51

 1011D (dij)1.5501

1110



 假设共4只蚂蚁，所有蚂蚁都从城市A出发，挥发因子

  k 1 , k  1 , 2, 3 。此时，观察GBAS的计算过程。 矩阵 2共有12条弧，初始信息素记忆矩阵为：

ij

执行GBAS算法的步骤2，假设蚂蚁的行走路线分别为：

第一只W1:ABCDA,f(W1)4;

第二只W2:ACDBA,f(W2)3.5;

第三只W3:ADCBA,f(W3)8; 第四只W4:ABDCA,f(W4)4.5;

当前最优解为，这个解是截止到当前的最优解，碰巧是实际最优解。

按算法步骤3的信息素更新规则，得到更新矩阵

124161240

160124124

(1)((1))ij

124112016 0 12416124

这是第一次外循环结束的状态。 重复外循环，由于上一次得到的W2已经是全局最优解，因此按算法步骤3的信息素更新规则，无论蚂蚁如何行走，都只是对W2路线上的城市信息素进行增强，其他的城市信息素进行挥发。得到更新矩阵

1485241480

 5240148148 (2)(ij(2))1481480524

148524148

0

这是第一次外循环结束的状态。

01121121121120112112(0)((0))11211201121121121120重复外循环，由于W2全局最优解，GBAS只记录第一个最优解，因此一但得到了全局最优解，信息素的更新将不再依赖于以群的行走路线，而只是不断增强最优路线的信息素，同时进行挥发。第三次外循环后得到的信息素矩阵为：

ij

4.蚁群算法在电力系统中的应用

1961148196011480196196(3)((3))1961960114819611481960

5.参考文献

[1]段海滨.蚁群算法原理及其应用.北京科学出版社.2005.

[2]丁同奎，张丽华，陈歆技，库永恒.基于蚁群算法的配电网故障定位与隔离[J].继电器2005.12.16

[3]林昭华，侯云鹤，熊信艮，鲁丽娟.广义蚁群算法用于电力系统无功优化[J].华北电力大学学报.2003，30（2）：6-9.