4.3蚁群算法在线视频

本单元主要讲授蚁群算法

人工蚁群算法就是一种

新型的群体智能优化算法

该算法是由意大利学者

M.Dorigo

等人于1991年首先提出的

称之为蚁群系统

并应用该算法求解旅行商问题

分配问题等

取得了较好的结果

受其影响

蚁群系统模型逐渐

引起了其它研究者的注意

D.Costa在

M.Dorigo

等人研究成果的基础上

提出了一种求解分配类型问题的

一般模型

并用来研究图着色问题

I.C.Parmee

研究了求解连续空间优化问题的蚁群系统模型

虽然这些成果仅是初步的

但是这些研究已显示出蚁群算法的一些优点

仿生学家经过大量细致观察研究发现

蚂蚁个体之间是通过

一种称之为外激素

的物质进行信息传递的

而且蚂蚁在运动过程中

能够感知这种物质

并以此指导自己的运动方向

因此

由大量蚂蚁组成的蚁群的

集体行为便表现出一种信息正反馈现象

当蚂蚁碰到一个还没有走过的路口时

就随机的选择一条路径前行

同时释放与路径长度有关的信息素

蚂蚁走的路越长

则是释放的信息素越少

当后来的蚂蚁再次碰到这个路口时

选择信息量较大的路径的概率相对较大

这样便形成了一个正反馈机制

最优路径上的信息量越来越大

而其他路径上的信息

却随时间组件减少

最终整个蚁群会找出最优路径

我们以求解n个城市的TSP问题

为例说明蚁群系统模型

对于其它问题

可以对此模型稍作修改便可应用

TSP即旅行商问题

对于给定的一组城市

每个城市之间的距离已知

求一条只经过各城市一次的

总长度最小的闭合路线

设城市数为n

城市i与城市j之间的距离为

dij,i,j=1,2,…,n

蚂蚁数为m

城市i与城市j之间路径上

在t时刻的信息素为τij(t)

初始时刻每条路上的信息素为常数

蚁群算法的寻优主要通过转移概率

信息素更新2个主要算子加以实现

转移概率

假设tabu k表示蚂蚁k已经访问过的城市列表

称之为禁忌表

C是n个城市的集合

那么allowed k表示蚂蚁k还能去的城市集合

蚂蚁k在面临路径选择的时候

按照（4.3-1）所示的从

城市i转移到城市j的转移概率

来决定下一个要去的城市

信息素更新

在每只蚂蚁完成对所有n个城市的

访问后

即一次循环结束后

按式（4.3-2）
（4.3-3）对路径上残留的

信息素进行更新

M.Dorigo介绍了k只蚂蚁在本次循环中

留在路径（i，j）上的信息素量的

3种不同的计算方法

分别称为ant-cycle算法

ant-density算法

ant-quantity算法

对于ant-cycle算法

如式（4.3-4）所示

ant-density算法及ant-quantity算法

与ant-cycle算法的区别在于

ant-density算法及ant-quantity算法

中每走一步

都要更新残留的信息素的浓度

而非等到所有蚂蚁完成对

所有n个城市的访问以后

上述3种方法中

ant-cycle算法的效果最好

蚁群算法的步骤如下.

蚁群算法的参数设置

目前尚无理论上的研究

已公布的实验结果都是

针对特定问题而言的

就TSP问题

从实验结果可知参数的取值范围如下

蚁群算法具有如下优点:

较强的鲁棒性

模型稍加修改便可以应用于其它问题

分布式计算

具有本质并行性

易于并行实现

易于与其它方法结合

该方法可以与多种启发式算法结合

以改善算法的性能

该算法的一个缺陷是计算时间较长

随着计算机的发展和计算速度的提高

可以弥补这一缺陷

蚁群算法的研究还不成熟

远未象遗传算法

粒子群算法等算法那样

形成系统的分析方法和坚实的数学基础

有许多问题有待进一步研究

本次课程到此结束

谢谢大家

再见