蚁群算法

τij (t + n) = ρ1 τij (t ) +△τij (t , t + n)
△ τ ij ( t , t + n ) =
∑ △τ
k =1
m
k ij
(t , t + n )
25
2.3 蚁周系统模型 上式中的 ρ 与 ρ 不同,因为该方程 不再是每 1
走一步都对轨迹更新,而是在一只蚂蚁建立了 一个完整的路径(n步)后再更新轨迹量. 在一系列的标准测试问题上运行的实验表明, 蚁周算法优于其他两种算法. 蚂蚁系统在解决小规模的TSP问题时还可以, 但是随着问题规模的扩大蚂蚁系统很难再可接 受的循环次数内找出最优解来.
2
1.1 蚂蚁的觅食行为
原因:蚂蚁在运动过程中,能够在它所经过的 路径上留下一种称之为外激素或者信息素 (pheromone)的物质进行信息传递,而且蚂蚁 在运动过程中能够感知这种物质,并以此指导 自己的运动方向,因此由大量蚂蚁组成的蚁群 集体行为便表现出一种信息正反馈现象:某一 路径上走过的蚂蚁越多,则后来者选择该路径 的概率就越大.
30
α
3.1.2 蚁群全局更新规则
在蚁群系统中,只有全局最优蚂蚁才允许释放信息素. 以及伪随机规则的使用,目的是使蚂蚁的搜索主要集中 在当前循环为止所找出的最好路径的邻域内,全局更新 在所有蚂蚁都完成它们的路径后执行,更新公式如下:
τ(r , s ) ← (1 α) τ(r , s ) + α △τ(r , s )
10
1.2 蚂蚁的觅食策略
2,不等长双桥实验: 图2 (a)为蚂蚁经过不等长双桥开始觅食; 图2 (b)显示绝大多数蚂蚁选择较短的桥; 图2 (c)显示最终有80%一100%的蚂蚁选 择较短的桥.
11
1.2 蚂蚁的觅食策略
图 2 不等长双桥实验
12
1.2 蚂蚁的觅食策略
在非对称双桥实验中,由于初始波动的扩大,蚂蚁常 常会选择最短的路径;先回蚁巢的蚂蚁在最短分支上走 了两次(从蚁穴到食物源,再回到蚁穴).所以这些蚂蚁 回来后不久,在短分支上有更多的信息素,从而诱使 巢中同伴选择短分支. 实验表明,通过初始波动的扩大,最终选择短分支的 几率随着两个分支的长度比的增加而增长.由此可见 ,在非对称双桥实验中,初始波动对胜出分支桥(即较 多蚂蚁选择的桥)的影响减小,而占主导作用的是随机 信息素的引导行为.
27
3.1 蚁群系统
(2)全局更新规则之用于最优的蚂蚁路径 上.每次循环后只对最优蚂蚁所走过的 路径进行信息素的增强,其他路径会由 于挥发机制逐渐减少,这就增大了最优 和最差路径在信息素上的差异,使搜索 行为能够很快地集中到最优路径附近, 提高了算法的搜索效率.
28
3.1 蚁群系统
(3)在建立问题解决方案后对所有 路径进行一次全局更新. 蚁群系统中,蚂蚁在构造路径的同时 进行更新,类似于蚁密系统和蚁量模型中 的规则,而在每次循环后再对路径进行一 次全局更新.
17
2.1 蚂蚁系统模型的建立
时间t=0 初始化A(t) 评价A(t)
释放信息素 蚂蚁移动 信息素挥发
终止条件是否满足
否
t=t+1
是 结束
18
2.1 蚂蚁系统模型的建立
在初始时刻,各条路径上的信息素量相等,设 τ ij ( 0 ) = c . 蚂蚁k(k=1,2…,m)在运动中根据各条路径上的信息 素量决定转移方向. Pij k ( t ) 位于城市i的蚂蚁k选择移动到城市j的概率 为:
3
简化的蚂蚁寻食过程
蚂蚁从A点出发,速度相同,食物在D点,可能随机选择路线ABD或ACD .假设初始时每条分配路线一只蚂蚁,每个时间单位行走一步,本图为 经过9个时间单位时的情形:走ABD的蚂蚁到达终点,而走ACD的蚂蚁刚 好走到C点,为一半路程.
4
简化的蚂蚁寻食过程
本图为从开始算起,经过18个时间单位时的情形:走ABD的蚂蚁到 达终点后得到食物又返回了起点A,而走ACD的蚂蚁刚好走到D点.
5
简化的蚂蚁寻食过程
假设蚂蚁每经过一处所留下的信息素为一个单位,则经过36 个时间单位后所有开始一起出发的蚂蚁都经过不同路径从D点取 得了食物,此时ABD的路线往返了2趟,每一处的信息素为4个单 位,而 ACD的路线往返了一趟,每一处的信息素为2个单位,其 比值为2:1. 若按以上规则继续,蚁群在ABD路线上再增派一只蚂蚁(共3 只),而ACD路线上仍然为一只蚂蚁.再经过36个时间单位后, 两条线路上的信息素单位积累为24和6,比值为4:1. 若继续进行,则按信息素的指导,最终所有的蚂蚁会放弃ACD 路线,而都选择ABD路线.这也就是前面所提到的正反馈效应.
( Lab ) △τ(r,s) = 0
1
如果(r,s)属于全局最优路径 否则
a为信息素挥发参数, Lab 为道目前为止找出的全局最优路径.
31
3.1.3蚁群局部更新规则
蚂蚁的局部更新规则对它们所经过的边进行激 素更新 设置 τ0 = (nLnn )1 可以产生好的结果,Lnn 是由最 近的领域启发产生的一个路径长度.实验表明 ,局部更新规则可以有效的避免蚂蚁收殓到同 一路径.
7
1.2 蚂蚁的觅食策略
图 1 等长双桥实验
8
1.2 蚂蚁的觅食策略
S.Goss等人还给出了上述实验的概率模型.首 先,假设桥上残留的信息素量和过去一段时间 经过该桥的蚂蚁数成正比(也就是说不考虑信息 A 素挥发的情况);其次某一时刻蚂蚁按照桥上信 息素量的多少来选择某支桥,即蚂蚁选择某支 桥的概率与经过该桥的蚂蚁数成正比.当所有 的m只蚂蚁都经过两支桥以后,设 Am 和 Bm 分别 为经过A桥和B桥的蚂蚁数( Am + Bm =m),则第 m+1只蚂蚁选择A(B)桥的概率为:
13
1.3 人工蚁群的基本思想
基于以上蚁群寻找食物时的最优路径选择问题,可以 构造人工蚁群,来解决最优化问题人工蚁群中把具有简单 功能的工作单元看作蚂蚁.二者的相似之处在于都是优先 选择信息素浓度大的路径.较短路径的信息素浓度高,所 以能够最终被所有蚂蚁选择,也就是最终的优化结果. 两者的区别在于人工蚁群有一定的记忆能力,能够记 忆已经访问过的节点.同时,人工蚁群再选择下一条路径 的时候是按一定算法规律有意识地寻找最短路径,而不是 盲目的.例如在TSP问题中,可以预先知道当前城市到下 一个目的地的距离.
m
9
1.2 蚂蚁的觅食策略
(k + Ai ) PA = = 1 PB n n (k + Ai ) + (k + Bi )
n
公式表明:往A走的蚂蚁越多,选择分支A的概率就越高 "n"决定选择公式的非线性程度.(n越大,信息素多 一点的分支选择概率越高) "k"表示对未标记的分支的吸引程度.(k越大,越多 的信息素使选择非随机化)
蚁群算法及其应用
1.
2.
3.
蚂蚁觅食行为 与觅食策略 蚂蚁系统—— 蚁群系统的原 型 改进的蚁群优 化算法
4.
蚁群优化算法研究 蚁群算法的应用— —对QoS组播路由 问题求解
5.
1
1.1 蚂蚁的觅食行为
现象: 在蚁群寻找食物时,它们总 能找到一条从食物到巢穴之间的最优路 径,并且能随着环境的变化而变化的搜 索新的最优路径.
22
k =1
2.2蚁量系统和蚁密系统的模型
蚁量系统和蚁密系统模型的差别紧差于在 △τij k (t , t + 1) 的表达式不同.在蚁密系统模型中,一只蚂蚁在经过 路径(i,j)上释放的信息量为 每单位长度Q,在蚁量 模型中,一只蚂蚁在经过路径(i,j)上释放的信息素 量为每单位长度Q/dij.从而:
6
1.2 蚂蚁的觅食策略
1,等长二元桥实验
蚁穴通过双支桥与食物相连,而桥的两个 分支长度相等,而且两个分支上最初没有信息 素.然后,将蚂蚁置于可以自由地在蚁穴和食 物源之间移动的状态,观察选择两个分支的蚂 蚁的比例.结果如图(b)显示,经过最初的一个 短暂的震荡阶段,蚂蚁向着一条相同的路径前 进.
14
2.1 蚂蚁系统模型的建立
商旅问题的引入(TSP问题)
引入原因: 1,它是最短路径问题,蚁群算法很容易适应这 类问题. 2,很容易理. 3,TSP是典型的组合问题,长用来验证一些算法 的有效性,便于与其他算法的比较.
15
2.1 蚂蚁系统模型的建立
蚂蚁主体具有的特征:
(1) 在从城市i到j的过程中或者一次循环结束 ,在边(i,j)释放信息素. (2) 有概率的访问下一个城市,这个概率是两 城市间和连接两城市的路径上存有轨迹量的函 数. (3) 不允许蚂蚁访问已经访问过的城市.
21
2.1 蚂蚁系统模型的建立
τij (t + 1) = ρ τij (t ) +△τij (t , t + 1)
△τij (t , t + 1) = ∑ △τ ij (t , t + 1)
k m
k
经过n个时刻,蚂蚁完成一次循环,各路径上的信息素 根据根据如下公式调整:
△τ ij (t , t + 1) 表示第k只蚂蚁在时刻(t,t+1)留在路径 (i,j)上的信息素. △τij (t , t + 1) 表示本次循环中路径(i,j)的信息素增量
26
3.1 蚁群系统
蚁群系统用于改善蚂蚁系统的性能,更好的解 决蚂蚁系统仅限于小规模问题的解决. 蚁群系统在蚂蚁系统上主要做了三个方面的改 进:
(1)状态转移规则为更好更合理地利用新路径好利用关 于问题的先验知识. 蚂蚁系统:使用随机比例规则,有倾向性地对路径进 行探索. 蚁群系统:伪随机比例规则.
29
3.1.1 蚁群系统状态转移规则
一只位于节点r的蚂蚁通过应用方程式给出的规 则选择下一个将要移动到的城市s.