27
应用二：QoS多播路由问题
什么是多播路由？ 构造一棵费用最小的多播树， 构造一棵费用最小的多播树，且满足 以下限制条件： 以下限制条件： 延时） (1) d(T(s, D))≤D （延时） (2) dj(T(s, D))≤DJ （抖动） 抖动） D))≤PL 丢包率） ≤P (3) pl(T(s, D))≤PL （丢包率） 带宽） (4) b(T(s, D))≥B. （带宽）
蚁群算法及其应用
1
启发式算法_分类
现代优化算法： 现代优化算法： 80年代初兴起 禁忌搜索（tabu search） 模拟退火（simulated annealing） 神经网络（neural networks） 遗传算法（genetic algorithms） 蚂蚁算法（Ant Algorithm，群体智能， Swarm Intelligence）
10
TSP问题的数学描述
TSP问题表示为一个 个城市的有向图G=（N，A），其中 问题表示为一个N个城市的有向图 （ ， ），其中 问题表示为一个 个城市的有向图 ），
N = {1,2,..., n} A = {(i , j) | i, j ∈ N }
城市之间距离
(d
目标函数为
ij
)
n× n
n
f (w) =
(对 只蚂蚁循环) for i = 1 to m do (对m只蚂蚁循环) (对 个城市循环) for j = 1 to n - 1 do (对n个城市循环)
根据式(1)，采用轮盘赌方法在窗口外选择下一个城市j; 根据式(1)，采用轮盘赌方法在窗口外选择下一个城市j; (1) 置入禁忌表,蚂蚁转移到j; 将j置入禁忌表,蚂蚁转移到j; end for end for 计算每只蚂蚁的路径长度; 计算每只蚂蚁的路径长度; 根据式(2)更新所有蚂蚁路径上的信息量; (2)更新所有蚂蚁路径上的信息量 根据式(2)更新所有蚂蚁路径上的信息量; k = k + 1; end while 输出结果,结束算法. ⑶输出结果,结束算法.
7
简化的蚂蚁寻食过程
经过18个时间单位时的情形： ABD的蚂蚁到达 经过18个时间单位时的情形：走ABD的蚂蚁到达 18个时间单位时的情形 终点后得到食物又返回了起点A，而走ACD的蚂蚁 终点后得到食物又返回了起点A 而走ACD的蚂蚁 ACD 刚好走到D 刚好走到D点。
8
自然蚁群与人工蚁群
相似之处在于：都是优先选择信息素浓度大的路径。 相似之处在于：都是优先选择信息素浓度大的路径。 在于 两者的区别： 两者的区别： （1）在于人工蚁群有一定的记忆能力，能够记忆 ）在于人工蚁群有一定的记忆能力， 已经访问过的节点。 已经访问过的节点。 （2）人工蚁群选择路径时不是盲目的。而是按一 ）人工蚁群选择路径时不是盲目的。 定规律有意识地寻找最短路径。例如， 问题中， 定规律有意识地寻找最短路径。例如，在TSP问题中，可 问题中 以预先知道当前城市到下一个目的地的距离。 以预先知道当前城市到下一个目的地的距离。
∏ (1 − pl ( n ))
(3)
29
多播树的QoS参数计算
d(T(s, D)) = max{d ( p( s, d i )) | d i ∈ D}
dj(T(s, D)) = max{dj ( p ( s, d i )) | d i ∈ D}
pl(T(s, D)) = max{ pl ( p ( s, d i )) | d i ∈ D}
(4)
(5)
(6)
b(T(s, D)) = min{b(e) | e ∈ T ( s, D )}
c(T(s, D)) =
e ∈ T (s, D)
(7 )
c(n) (8 )∑c(e)Fra bibliotek+
n ∈ T (s, D)
∑
30
算法
方法1 方法1：用蚁群算法找到去每一个目的节 点的QoS最优路径，再融合。 QoS最优路径 点的QoS最优路径，再融合。 方法2 找到一条QoS最优路径， QoS最优路径 方法2：找到一条QoS最优路径，其它目 的节点再依次加入多播树中。 的节点再依次加入多播树中。
31
(1,1,10-5,4) 9) 00, ,3,1 18 ( (1,1,10-6,11)
1
(9, 0,8 0,2 )
其中： 为常数； 其中：Q为常数；lk表示第k只蚂蚁在本次迭代中 走过的路径， 为路径长度。 走过的路径，Lk为路径长度。
14
求解TSP算法步骤 求解TSP算法步骤 TSP
随机放置蚂蚁，为每只蚂蚁建立禁忌表tabu ⑴初始化 随机放置蚂蚁，为每只蚂蚁建立禁忌表tabuk，将初始节 点置入禁忌表中; 点置入禁忌表中; ⑵迭代过程 k=1 (执行迭代 执行迭代) while k=<ItCount do (执行迭代)
22
对Kroa100，算子3优化前后的路径如图所示。 （23012），算子3优化后（21282）
23
收敛特性对比
27000 26000 25000 Length 24000 23000 22000 21000 6 8 14 16 17 25 34 Iteration 50 51 417 1000 LOACA ACA
18
对Kroa100，算子1优化前后的路径如图所示。 优化前（28596），算子1优化后（26439）
19
改进一：局部优化（算子 改进一：局部优化（算子2 ）
20
对Kroa100，算子2优化前后的路径如图所示。 算子1（26439），算子2优化后（23012）
21
改进一：局部优化（算子 改进一：局部优化（算子3 ）
28
路径的QoS参数计算
d(p(s, d i )) =
e∈p(s,d i )
∑ d(e) + ∑ d(n)
n∈p(s,d i )
(1)
dj(p(s,di )) =
e∈p(s,di )
∑dj(e)+ ∑dj(n)
n∈p(s,di )
(2)
pl(p(s, d i )) = 1 −
n∈p(s,d i )
24
改进二：蚁群优化算法
1)ACS采用了更为大胆的行为选择规则，在 城市r的蚂蚁k转移到城市s的规则为:
25
2.1.4蚁群优化算法
第三，仅对全局最优解边上的信息素进行加强，更新如下: 第三，仅对全局最优解边上的信息素进行加强，更新如下:
26
其它改进
1）精英策略 2）基于排序的蚂蚁系统 3） MAX-MIN蚂蚁系统
13
蚂蚁算法求解TSP
τ ij (t + n) = ρ ⋅τ ij (t ) + ∆τ ij
∆τ ij = ∑ ∆τ
k =1 m k ij
(2)
其中：ρ为小于1的常数，表示信息的持久性。 其中： 为小于1的常数，表示信息的持久性。
Q k ∆τ ij = Lk 0 ij ∈ l k otherwise (3)
2
遗传算法
遗传算法(Genetic Algorithm, GA)是1962 年密切根大学Holland教授首次提出的一 种全局优化算法，它借用了生物遗传学 的观点，通过自然选择、遗传、变异等 作用机制，实现各个体的适应性的提高， 并迅速推广到优化、搜索、机器学习等 方面。
3
遗传算法的过程
编码和初始群体生成
9
应用一：TSP问题
旅行商问题（ 旅行商问题（TSP,traveling salesman problem）1960年首先提出 年首先提出。 problem）1960年首先提出。 问题描述： 问题描述： 一商人去n个城市销货， 一商人去n个城市销货，所有城市走一遍再 回到起点，使所走路程最短。 回到起点，使所走路程最短。 TSP在许多工程领域具有广泛的 在许多工程领域具有广泛的应用价值 TSP在许多工程领域具有广泛的应用价值 例如电路板布线、VLSI芯片设计 芯片设计、 例如电路板布线、VLSI芯片设计、机器人控 交通路由等。 制、交通路由等。 TSP的求解是NP-hard问题 的求解是NP 问题。 TSP的求解是NP-hard问题。随着城市数目的增 问题空间将呈指数级增长。 多,问题空间将呈指数级增长。
15
蚁群的规模和停止规则
一、蚁群大小 一般情况下蚁群中蚂蚁的个数不超过TSP TSP图中节点的个 一般情况下蚁群中蚂蚁的个数不超过TSP图中节点的个 数。 二、终止条件 给定一个外循环的最大数目； 1 给定一个外循环的最大数目； 当前最优解连续K次相同而停止，其中K 2 当前最优解连续K次相同而停止，其中K是一个给定 的整数，表示算法已经收敛，不再需要继续。 的整数，表示算法已经收敛，不再需要继续。
6
简化的蚂蚁寻食过程
蚂蚁从A点出发，速度相同，食物在D 蚂蚁从A点出发，速度相同，食物在D点，可能随机 选择路线ABD ACD。 ABD或 选择路线ABD或ACD。假设初始时每条分配路线一只 蚂蚁，每个时间单位行走一步，本图为经过9 蚂蚁，每个时间单位行走一步，本图为经过9个时 间单位时的情形：走ABD的蚂蚁到达终点，而走ACD 间单位时的情形： ABD的蚂蚁到达终点，而走ACD 的蚂蚁到达终点 的蚂蚁刚好走到C 为一半路程。 的蚂蚁刚好走到C点，为一半路程。
TSP具有邻域特征，设置候选窗口， TSP具有邻域特征，设置候选窗口，窗口大小应 具有邻域特征 取一个合理值。 取一个合理值。 蚂蚁总是优先选择候选窗口中的城市。 蚂蚁总是优先选择候选窗口中的城市。搜索结 束后，根据候选窗口对路径进行优化， 束后，根据候选窗口对路径进行优化，如果将候 选窗口内的节点交换到当前节点附近后距离更短， 选窗口内的节点交换到当前节点附近后距离更短， 则进行变异。 则进行变异。
16
蚂蚁算法的缺点
蚂蚁算法的缺点： 蚂蚁算法的缺点： 1）收敛速度慢 2）易于陷入局部最优 改进： 改进： 采用局部优化，设计了三种优化算子。 1）采用局部优化，设计了三种优化算子。 采用蚁群优化算法。 2）采用蚁群优化算法。 3）其它优化算法