➢自然蚂蚁的智能特点
6 6
蚁群算法原理
➢人工蚂蚁的模型
7 7
蚁群算法原理
➢自然蚁群与人工蚁群
相似之处在于：都是优先选择信息素浓度大的路径。
两者的区别在于： （1）人工蚁群有一定的记忆能力，能够记忆已经
访问过的节点。 （2）人工蚁群选择路径时不是盲目的，而是按一
定规律有意识地寻找最短路径。例如在TSP问题中， 可以预先知道当前城市到下一个目的地的距离。
子集越大信息正反馈的作用不明显，搜索的随机性增强，造成收 敛速度变慢; 反之，子集越小，搜索的随机性减弱，虽然收敛速度较快，但是 会使算法的全局性能降低，影响算法的稳定性。
➢信息素挥发度 的选取
信息素挥发度 的大小对蚁群算法的收敛性能影响极大; · 当 比较小时，搜索的全局性好，但收敛速度变慢;
xallowk
0, s allowk
信息更新公式为：
ij (t 1) (1 )ij (t) ij
ij
n
k ii
,0 1
k 1
10 10
基本蚁群算法
针对蚂蚁释放信息素问题，M.Dorigo等人曾给出3中 不同的模型，分别为蚁周系统、蚁量系统和蚁密系统， 其计算公式如下：
1.Ant-cycle
蚁群优化算法
Ant Colony Optimization
1
算法介绍
• 群智能算法
群智能是一种由简单智能的个体通过某种形式的聚集协同而表现出智能行 为。它在没有集中控制，不提供全局模型的前提下寻找复杂的分布式问题求解 方案提供了基础。群智能算法通过模仿生物界的进化机理和群体协作行为而提 出的仿生类随机搜索算法。
k ii
Q 0,
/ Lk，第k只蚂蚁从城市i访问城市j 其他
2.Ant-quantity
k ii
Q / dij，第k只蚂蚁从城市i访问城市j
0,
其他
3.Ant-density
k ii
Q，第k只蚂蚁从城市i访问城市j 0, 其他
其中，Q为常数，表示蚂蚁循环一次所释放的信息素总量；L为第k只蚂蚁经
过路径的长度；d为城市间的距离。。
➢较强的鲁棒性 ·➢分布式计算
➢易于与其他方法结合
需要较长的搜索时间 容易出现停滞现
15 15
带精英策略的蚂蚁系统
➢带精英策略的蚂蚁系统（Ant System with elitist strategy,
ASelite）是最早的改进蚂蚁系统。
➢遗传算法中的精英策略
– 传统的遗传算法可能会导致最适应个体的遗传信息丢失 – 精英策略的思想是保留住一代中的最适应个体
8 8
求解组合优化问题的蚁群算法
9 9
基本蚁群算法
蚂蚁k(k=1,2，…,m)根据各个城市间连接路径上的信
息素浓度决定其下一个访问城市，设Pijk t 表示t时刻蚂蚁
k从城市i转移到城市j的概率，其计算公式为：
Pijk
(t
)
is
(t
)is
(t
)
, s allowk
is
(tห้องสมุดไป่ตู้
)is
(t
)
ACO首次被系统的提出
启发
自然界中真实蚁群集体行为
4 4
蚁群算法原理
➢如何找到最短路径 ？
• 信息素：信息素多的地方显然经过这里的蚂蚁多， 因而会有更多的蚂蚁聚集过来。
• 正反馈现象：某一路径上走过的蚂蚁越多，则后来 者选择该路径的概率就越大。
类比：
大肠杆菌在人体肠道内觅食的过程
5 5
蚁群算法原理
可以使蚂蚁系统找出更优的解 找到这些解的时间更短 精英蚂蚁过多会导致搜索早熟收敛
18 18
蚁群系统
➢ 蚁群系统的状态转移规则
一只位于节点r的蚂蚁通过应用下式给出的规则选择 下一个将要移动到的城市s：
s
arg
max {[
uallowedk
(r,
u)]
[(r, u)]
}, 如果q
q0按先验知识选择路径
➢蚂蚁的初始分布
所有蚂蚁初始时刻放在同一个城市; 蚂蚁分布在不同的城市中。
14 14
蚁群算法时间复杂度及优缺点
M.Dorigo曾经对经典的TSP问题求解复杂度进 行过深入的研究，所得到的经验结果表明，算法 的时间复杂度为O(NC·n2·m)，NC表示迭代次数， n表示城市数，m则表示参与搜索的蚂蚁数量。当 参与搜索的蚂蚁数量m大致与规模大小n相等时， 算法的时间复杂度变为O(NC·n3)
11 11
蚁群算法的主要特点
采用分布式控制 每个个体只能感知局部的信息 个体可以改变环境 具有自组织性 是一类概率型的全局搜索方法 优化过程不依赖于优化问题本身的严格数学性质 是一种基于多主体(Multi-Agent)的智能算法 具有潜在的并行性
12 12
蚁群算法参数选择
➢蚁群数量m的选择
m
ij
k ij
k 1
k ij
Q
Lk
, 如果蚂蚁k在本次循环中经过路径(i,j)
0, 否则
* ij
Q L*
, 如果边(i,j)是所找出的最优解的一部分
0, 否则
17 17
带精英策略的蚂蚁系统
➢ 表示精英蚂蚁引起的路径(i, j)上的信息素量的增加 ➢ 是精英蚂蚁的个数 ➢ L 是所找出的最优解的路径长度 ➢特点：
当 比较大时，收敛速度比较快，但是容易陷入局部最优。
13 13
蚁群算法参数选择
➢因子 和 的选取
启发式因子 的大小则反映了在蚁群路径搜索中的随机性因素作
用的强度;
启发式因子 的大小反映了在蚁群路径搜索中确定性因素作用的
强度。
➢总信息量Q的选取
总信息量Q越大，可以加强蚁群搜索时的正反馈性能，有助于算 法的快速收敛。
S , 否则
其中，S根据下列公式得：到
Pijk (t)
ij
(t)
ij
(t)
is
(t
)
is
(t
)
sallowedk
去 人工蜂群算法 细菌觅食算法 萤火虫算法 粒子群算法 人工鱼群算法 鸟群算法
2 2
蚁群算法的提出
Macro Dorigo
Gambardella
3 3
蚁群算法的发展
2001年至今
各种改进算法的提出，应用领域更广
1996年-2001年
引起学者关注，在应用领域得到拓宽
意大利学者
Dorigo1991年 Dorigo1991年
➢蚂蚁系统中的精英策略
– 每次循环之后给予最优解以额外的信息素量 – 这样的解被称为全局最优解（global-best solution） – 找出这个解的蚂蚁被称为精英蚂蚁(elitist ants)
16 16
带精英策略的蚂蚁系统
➢信息素根据下式进行更新
其中
ij (t 1) ij (t) ij i*j