蚁群优化算法PPT

ACO首次被系统的提出
自然界中真实蚁群集体行为
4
蚁群算法原理
如何找到最短路径 ？
• 信息素：信息素多的地方显然经过这里的蚂蚁多， 因而会有更多的蚂蚁聚集过来。
• 正反馈现象：某一路径上走过的蚂蚁越多，则后来 者选择该路径的概率就越大。
类比：
大肠杆菌在人体肠道内觅食的过程
5
蚁群算法原理
自然蚂蚁的智能特点
Meet the requirement of the solution
Y
output
31
实现过程
32
实现过程
33
实现过程
·
当 比较小时，搜索的全局性好，但收敛速度变慢; 当 比较大时，收敛速度比较快，但是容易陷入局部最优。
13
蚁群算法参数选择
因子 和 的选取
启发式因子 的大小则反映了在蚁群路径搜索中的随机性因素作 用的强度;
启发式因子 的大小反映了在蚁群路径搜索中确定性因素作用的 强度。
1.Ant-cycle
Q / Lk，第k只蚂蚁从城市i访问城市j k ii 0, 其他
k ii
Q / dij，第k只蚂蚁从城市i访问城市j 2.Ant-quantity 0, 其他
Q，第k只蚂蚁从城市i访问城市j 3.Ant-density 0, 其他
8
求解组合优化问题的蚁群算法
9
基本蚁群算法
蚂蚁k(k=1,2，…,m)根据各个城市间连接路径上的信 息素浓度决定其下一个访问城市，设 Pijk t 表示t时刻蚂蚁 k从城市i转移到城市j的概率，其计算公式为：
is (t )is (t ) , s allowk Pijk (t ) is (t )is (t ) xallowk 0, s allowk
较强的鲁棒性
·
需要较长的搜索时间 容易出现停滞现
分布式计算 易于与其他方法结合
15
带精英策略的蚂蚁系统
带精英策略的蚂蚁系统（Ant System with elitist strategy,
ASelite）是最早的改进蚂蚁系统。
遗传算法中的精英策略
– 传统的遗传算法可能会导致最适应个体的遗传信息丢失 – 精英策略的思想是保留住一代中的最适应个体
Lnn 是由最近的邻域启发产生的一个路径长度 市的数量，
局部更新规则可以有效地避免蚂蚁收敛到同一路径
21
Max-Min Ant System（ MMAS）
信息素轨迹更新原则
在MMAS中，只有一只蚂蚁用于在每次循环后更新信息 轨迹。经修改的轨迹更新原则如下：
ij (t 1) ij (t )
轨迹量
平滑机制有助于对搜索空间进行更有效的探索
24
Max-Min Ant System（ MMAS）
25
蚁群算法的应用
26
蚁群算法的应用
TSP问题
问题描述：旅行商按一定的顺序访问n个城市，使得每 个城市都被访问且仅能被访问一次而使花费代价最小， 从图论的观点来看，就是找出一个最短的封闭回路。
总信息量Q的选取
总信息量Q越大，可以加强蚁群搜索时的正反馈性能，有助于算 法的快速收敛。
蚂蚁的初始分布
所有蚂蚁初始时刻放在同一个城市; 蚂蚁分布在不同的城市中。
14
蚁群算法时间复杂度及优缺点
M.Dorigo曾经对经典的TSP问题求解复杂度进 行过深入的研究，所得到的经验结果表明，算法 的时间复杂度为O(NC·n2·m)，NC表示迭代次数， n表示城市数，m则表示参与搜索的蚂蚁数量。当 参与搜索的蚂蚁数量m大致与规模大小n相等时， 算法的时间复杂度变为O(NC·n3)
信息更新公式为：
ij (t 1) (1 ) ij (t ) ij n ,0 1 k ij ii k 1
10
基本蚁群算法
针对蚂蚁释放信息素问题，M.Dorigo等人曾给出3中 不同的模型，分别为蚁周系统、蚁量系统和蚁密系统， 其计算公式如下：
其中，S根据下列公式得：到
ij (t ) ij (t ) , j allowed k k is (t ) is (t ) P ij (t ) sallowed k otherwise 0,
19
蚁群系统
蚁群系统全局更新原则
只有全局最优的蚂蚁才被允许释放信息素。
[ (i, j )] [ (i, j )] , if j tabuk P k (i, j ) [ (i, s )] [ (i, s)] stabuk otherwise 0 ,
(1)
(i, j ) 1/ d (i, j ) 是 (i, j) 表示边（i，j）上的信息素浓度； 启发信息，d是城市i和j之间的距离；α 和β 反映了信息 tabuk 表示蚂蚁k已经访问过 素与启发信息的相对重要性； 的城市列表。
Each ant choose the next city
Move to j and modify the tabu
i++
i>=city.N
N
Y
Calculate the distance each ant walks the loop
Update pheromone between cities
N
目的：使蚂蚁的搜索主要集中在当前循环为止所找出 的最好路径领域内。 全局更新在所有蚂蚁都完成它们的路径之后执行，用 下式对所建立的路径进行更新：
(r, s) (1 ) (r, s) (r, s)
1 L , (r , s ) gb 0, 如果(r,s) 全局最优路径 否则
20
蚁群系统
蚁群系统局部更新原则
类似于蚁密和蚁量模型中的更新规则
蚂蚁应用下列局部更新规则对它们所经过的边进行信 息素更新
(r , s) (1 ) (r, s) (r, s) 其中， 0 1
0 实验发现，
1 可以产生好的结果，其中n是城 n L nn
k ij k 1 m
其中 ij
Q , 如果蚂蚁k在本次循环中经过路径(i,j) k ij Lk 0, 否则
Q * , 如果边(i,j)是所找出的最优解的一部分 * ij L 0, 否则
17
带精英策略的蚂蚁系统
表示精英蚂蚁引起的路径(i, j)上的信息素量的增加
信息素轨迹的平滑化
基本思想：通过增加选择有着低强度信息素轨迹量解 元素的概率以提高探索新解的能力
* ij (t ) ij (t ) ( max (t ) ij (t ))
* 其中,0 1, ij (t )和 ij (t )分别为平滑化之前和之后的信息素
m in ij ( t ) m a x

m a x ij
(t )

t

ti
i 1
1 f ( s opt )
min 的选取要基于两点假设：1.最优解在搜索停滞发 生之前不久被找出。2.对解构造的主要影响是由信息素 轨迹的上限与下限之间的相对差异决定
23
Max-Min Ant System（ MMAS）
TSP在许多工程领域具有广泛的应用价值，例如电路板 布线、机器人控制、交通路由等。 TSP的求解是NP-hard问题。随着城市数目的增多,问题 空间将呈指数级增长
27

蚁群系统在TSP问题中的应用
28
蚁群算法求解TSP问题
下面以TSP为例说明基本蚁群算法模型。
首先将m只蚂蚁随机放置在n个城市，位于城市i的第k 只蚂蚁选择下一个城市j的概率为:
去
人工蜂群算法 细菌觅食算法 萤火虫算法 粒子群算法 人工鱼群算法 鸟群算法
2
蚁群算法的提出
Macro Dorigo
Gambardella
3
蚁群算法的发展
2001年至今
各种改进算法的提出，应用领域更广
1996年-2001年
引起学者关注，在应用领域得到拓宽
意大利学者 Dorigo1991年 Dorigo1991年 启发
蚁群优化算法
Ant Colony Optimization
算法介绍
• 群智能算法
群智能是一种由简单智能的个体通过某种形式的聚集协同而表现出智能行 为。它在没有集中控制，不提供全局模型的前提下寻找复杂的分布式问题求解 方案提供了基础。群智能算法通过模仿生物界的进化机理和群体协作行为而提 出的仿生类随机搜索算法。
(3)
其中，Q为常数；Lk 表示第k只蚂蚁在本次迭代中走过 的路径长度。
30
Initialization
Distribute the ants, Modify the tabu
Calculate the probability of moving between cities
Number of traverse city i=1


bestij
bestij
1 f ( s best )
表示迭代最优解或全局最优解的值。
在蚁群算法中主要使用全局最优解，而在MMAS中则主 要使用迭代最优解。
22
Max-Min Ant System（ MMAS）
信息素轨迹的限制
min MMAS对信息素轨迹的最小值和最大值分别施加了 和 max 的限制，从而使得对所有信息素轨迹 ，有
6
蚁群算法原理
人工蚂蚁的模型
7
蚁群算法原理
自然蚁群与人工蚁群