06计算智能导论_进化计算-5-蚁群
智能计算导论
第第二章章进化计算
第五节蚁群算法及其应用
智能科学与技术系西安电子科技大学
1
第五节蚁群算法及其应用
提纲
•简介
•基本蚂蚁算法
•改进算法
•蚁群算法的应用
2
背景(1)
3
背景(2)
2001年至今
1996年-2001年
引起学者关注，在应用领域得到拓宽
1991年意大利学者
Dorigo
受自然界
启发自然界中真实蚁群集体行为
蚁群算法，是一种仿生算法。
蚁群算法原理
•蚂蚁在觅食过程中可以找出巢穴到食物源的最短路径，为什么？
（1）信息素(pheromone)
（2）正反馈现象：某一路径上走过的蚂蚁越多，则后来者选择该路径的概率就越大。
5
简简化的蚂蚁寻食过程的蚂食过(1)
蚂蚁从A点出发，速度相同，食物在D点，可能随机选择路线ABD或ACD。假设初始时每条分配路线一只蚂蚁，每个时间单位行走一步，本图为经过9个时间单位时的情形：走ABD的蚂蚁到达终点，而走ACD的蚂蚁刚好走到C点，为一半路程。6
简化的蚂蚁寻食过程(2)
经过18个时间单位时的情形：走ABD的蚂蚁到达终点后得到食物又返回了起点A，而走ACD的蚂蚁刚好走到D点。
7
自然蚁群与人工蚁群
相似之处在于：都是优先选择信息素浓度大的路径。两者的区别：
（1）在于人工蚁群有一定的记忆能力，能够记忆已经访问过的节点。
（2）人工蚁群选择路径时不是盲目的。而是按一定规律有意识地寻找最短路径。例如，在TSP 问题中，可以预先知道当前城市到下一个目的地的距离。
8
第五节蚁群算法及其应用
提纲
•简介
•基本蚂蚁算法
•改进算法
•蚁群算法的应用
9
蚂蚁算法
路径选择方法：
蚂蚁向下一个目标的运动是通过一个随机原则来实现的，也就是运用当前所在节点存储的信息，计算出下一步可达节点的概率，并按此概率实现一步移动，步点的概率此概率实步逐此往复，越来越接近最优解。
蚂蚁在寻找过程中或者找到个解后会评估该蚂蚁在寻找过程中，或者找到一个解后，会
解或解的一部分的优化程度，并把评价信息保存在相关连接的信息素中。
10
蚂蚁算法
信息素的更新方式有2种:
•一是挥发(evaporation)，也就是所有路径上的信息素以一定的比率进行减少，模拟自然蚁群的信息素随时间挥发的过程挥模拟自然蚁群的信息素随时间挥发的过程挥发过程主要用于避免算法过快地向局部最优区域集中，有助于搜索区域的扩展；
•二是增强(reinforcement)，给评价值“好”(有蚂蚁走过) 的边增加信息素。增强过程是蚁群优化算法中可选的部分，这种方式可以实现由单个蚂蚁无法实现的集中行动。也就是说，增强过程体现在观察蚁群（m 只蚂蚁）中每只蚂蚁所找到的路径并选择其中最优路径上的弧进行信息素的增强路径，并选择其中最优路径上的弧进行信息素的增强。
11
基本蚂蚁算法(2)
Ant System ,AS)
蚂蚁k(k=1,2，…,m)根据各个城市间连接路径上的
个访问城市设P k
ij (t ) 表示t时刻蚂蚂蚁算法(信息素浓度决定其下信息素浓度决定其下一个访问城市，设
蚁k从城市i转移到城市j的概率，其计算公式为：
13
TSP 问题
z问题描述：
一商人去n个城市销货，所有城市走一遍再回到起点使所走路程最短（TSPt 回到起点，使所走路程最短（TSP, traveling li salesman problem,1960年首先提出)。zTSP在许多工程领域具有广泛的在许域有广应用价值价值:
例如电路板布线、VLSI芯片设计、机器人控制、交通路由等。
zTSP的求解是NP NP-hard问题hard问题:
随着城市数目的增多,问题空间将呈指数级增长。增长
16
TSP 问题的数学描述
zTSP 问题表示为问题表示为一个个N 个城市的有向图G=（N ，A ），
N ={1,2,...,n} A ={(i , j) | i , j ∈N }
z城市之间距离(d ij ) n ×n
z目标函数为min n
f (w ) =∑d i
l =1l i l +1
w =(i 1, i 2, " , i n , ) 为城市1,2，…n 的一个排列，且i n +1=i 1
17
蚂蚁算法求解TSP(1)
z首先将m只蚂蚁随机放置在n个城市；
只蚂蚁在图的相邻节点间移动，从而协作异从而协作异z假设m 只蚂蚁在图的相邻节点间移动
步地得到问题的解；
z每只蚂蚁的每只蚂蚁的一步转移概率由图中的每条边上的两类步转移概率由图中的每条边上的两类参数决定：
信息素值，也称信息素痕迹。信息素值也称信息素痕迹
可见度，即先验值。
然后, 根据公式(1)(2)计算；
18
蚂蚁算法求解TSP(2)⑴初始化随机放置蚂蚁，为每只蚂蚁建立禁忌表tabuk ，将初始节点置入禁忌表中;
⑵迭代过程
k=1
while while k=
for i = 1 to m do (对m只蚂蚁循环)for j = 1 to n do (对n个城市循环)根据式(1)，选择下一个城市j;
将j置入禁忌表,蚂蚁转移到j;
end end forfor
end for
计算每只蚂蚁的路径长度;
根据式(2)更新所有蚂蚁路径上的信息量;k = k + 1;
end end whilewhile
⑶输出结果,结束算法.
19
蚁群的规模和停止规则
蚁群大小
一般情况下蚁群中蚂蚁的个数不超过TSP图中节点的个般情况下蚁群中蚂蚁的个数不超过TSP图中节点的个数。
终止条件
(1) 设定一个外循环的最大迭代次数；
((2) 当前最优解连续K次相同而停止；) 当前最优解连续次相同而停；
其中K是一个给定的整数，表示算法已经收敛，不再需要继续。
20
基本蚂蚁算法的缺点
蚂蚁算法的缺点：
（1）收敛速度慢：算法的时间复杂度为O (Kn 2m ) ，K表示迭代次数, n城市数, m参与搜索的蚂蚁数量;
（2）易于陷入局部最优解:易出现停滞现象；改进：
（1）蚁群系统（Ant Colony System,ACS）算法, 由M.Dorigo 提出。M.Dorigo 提出。
（2）最大-最小蚂蚁（Max-Min AS)算法,由T.Stutzle 提出。
21
第五节蚁群算法及其应用
提纲
•简介
•基本蚂蚁算法
•改进算法(ACS & MMAS)
•蚁群算法的应用
22
蚁群系统(ACS)算法
蚁群系统做了三个方面的改进：
z状态转移规则:为更好更合理地利用新路径和利用关于问题的先验知识提供了方法；
z全局更新规则:只应用于最优的蚂蚁路径上；z局部更新规则:局部更新规则避免收敛到同一路经。避免收敛到同路经
23
最大-最小蚂蚁系统（MMAS）z蚁群算法优点：将蚂蚁的搜索行为集中到最优解的附近可以提高解的蚁群算法优点将蚂蚁的搜索行为集中到最优解的附近可以提高解的质量和收敛速度，从而改进算法的性能。
z缺点：缺点但这种搜索方式会使早熟收敛行为更容易发生。但这种搜索方式会使早熟收敛行为更容易发生
zMMAS：能将这种搜索方式和一种能够有效避免早熟收敛的机制结合在一起，从而使算法获得最优的性能
信息素的更新方式
信息素的浓度限制
27
第五节蚁群算法及其应用
提纲
•简介
•基本蚂蚁算法
•改进算法(ACS & MMAS) •蚁群算法的应用
30
网络拓扑结构
31
网络拥塞
网络拥塞主要表现在:
带宽设计太窄;
由于突发性事件造成信息急剧膨胀;
路由不平衡, 局部拥塞;
32Á
已知：网络有20 个结点, 结点之间连线代表结点之间有已知：网络有20个结点结点之间连线代表结点之间有通路, 连线上的一组数字分别表示结点之间的距离和最大流量(或带宽) ；
(1)假定要从源结点1 出发, 目的结点是20 ,
(2)从源结点9 出发, 目的结点是15 , 进行数据通信,如何进行动态最优路由选择呢?
33
设网络的加权连通图：G(V,E) ，顶点总数n ，顶点集顶点集:V ={vV {1, v2, ..., vn }，
边的集合：E ={e
网络的连接矩阵：1, e2, ..., e
(取n-1}，
A =(a ij ) nxn 0或1)
距离矩阵：B =(b ij ) nxn
流量容量限制矩阵：C =(c ij ) nxn
M 为蚂蚁个数，则目标函数Z 为
其中，其中Ex 是阶段拥塞时网络可行边的集合，它是包含于是阶段拥塞时网络可行边的集合它是包含于E 的不断缩小的集合序列，的不断缩小的集合序列通过Ex 的不断变化，可以找到最短路径。
34
求解过程
Step1p : 利用构造的自适应蚂蚁算法寻找源结点到目的结点的最短路径
Step2: 用最短路径的每一网段的容量减去最短路径的最小网段容量;小网段容量
Step3: 根据容量变化和连接矩阵的变化重新寻找源结点到目的结点的最短路径;
Step4: 一旦再也找不到一条源结点到目的结点可行路由(或限制在预设的最短路径数量以内),则源结点或目的结点成为孤立点, 跳出循环,结束;
Step5: 将找到的最短路径序列作为源结点目的结点的最优路由表设置。优路由表设置
35
实验结果
α=1, β=2, ρ=0.8, Q =1000, 对于点1->20的最短路径，计算时取，
初次得到最短路径①1-> 3 ->6 ->11 ->16 ->20,1>3>6>11>16>20长度为13，流量(最小网段容量)为4;τmin =6037
其它研究与应用举例
题目出版时间作者期刊来源基于蚂蚁算法的时序电
路测试生成研究2002‐04‐01李智电子科技大学硕士论
文
基于自适应蚂蚁算法的
房地产投资组合优化决2006‐02‐28李慧敏等基建优化
策
基于蚂蚁算法的公交驾
驶员调度问题研究2009‐05‐01杨尚华中科技大学硕士论
文
基于蚂蚁算法的传感器
网络路由算法研究2009‐02‐10张爱科通信技术求解有限产能作业间调
度的改进蚂蚁算法2011‐02‐23陈琦等计算机工程与应用基于蚂蚁算法的电梯群
控系统的设计与实现2013‐11‐01马大龙吉林大学基于自适应阈值蚁群算
法的路径规划算法2014‐02‐15赖智铭等计算机系统应用
38
蚁群算法小结
Á优点:
分布式计算: 蚁群算法是一种基于种群的进蚁群算法是种基于种群的进化算法, 具有本质并行性, 易于并行实现；易与其他方法结合:蚁群算法很容易与多种启发式算法结合, 以改善算法的功能; Á缺点：
初期信息素匿乏, 求解速度较慢；求解速度较慢
39