忌搜索算法.ppt

第二章 禁忌搜索算法
局部搜索
邻域的概念
局部搜索算法
局部搜索例如
禁忌搜索
算法的主要思路
，
总可以计算出全局最优解。
局部搜索例如
局部搜索
邻域的概念
局部搜索算法
局部搜索例如
禁忌搜索
算法的主要思路
禁忌搜索例如
禁忌搜索的关键参数和操作
变化因素
禁忌表
其他
禁忌搜索的实现与应用
30城市TSP问题〔d*= by D B Fogel〕
基于禁忌搜索算法的系统辨识
►
禁忌搜索
算法的提出
禁忌搜索〔Tabu search〕是局部邻域搜索算法的推广，Fred Glover在1986年提出这个概念，进而形成一套完整算法。
算法的特点
禁忌——禁止重复前面的工作。
跳出局部最优点。
算法的主要思路
:///~glover/
禁忌搜索
四城市非对称TSP问题

初始解x0=(ABCD)，f(x0)=4，邻域映射为两个城市顺序对换的2－opt，始、终点都是A城市。
禁忌搜索例如
禁忌搜索
四城市非对称TSP问题
第1步
解的形式 禁忌对象及长度 候选解
f(x0)=4
禁忌搜索例如
A
B
C
D
B
C
D
A
B
C
对换
评价值
CD

BC

BD
8
☻
禁忌搜索
四城市非对称TSP问题
第2步
解的形式 禁忌对象及长度 候选解
f(x1)=
禁忌搜索例如
A
B
D
C
B
C
D
A
B
C
3
对换
评价值
CD

BC

BD

☻
T
禁忌搜索
四城市非对称TSP问题
第3步
解的形式 禁忌对象及长度 候选解
f(x2)=
禁忌搜索例如
A
C
D
B
B
C
D
A
B
3
C
2
对换
评价值
CD
8
BC

BD

☻
T
T
禁忌搜索
四城市非对称TSP问题
第4步
解的形式 禁忌对象及长度 候选解
f(x3)=
禁忌长度的选取
禁忌搜索例如
A
C
B
D
B
C
D
A
B
2
3
C
1
对换
评价值
CD

BC

BD

T
T
T
禁忌搜索
四城市非对称TSP问题
第4步〔如果减小禁忌长度〕
解的形式 禁忌对象及长度 候选解
f(x3)=
禁忌搜索例如
A
C
B
D
B
C
D
A
B
1
2
C
0
对换
评价值
CD

BC

BD

☻
T
T
禁忌搜索
四城市非对称TSP问题
第5步
解的形式 禁忌对象及长度 候选解
f(x4)=
禁忌搜索例如
A
D
B
C
B
C
D
A
B
0
1
C
2
对换
评价值
CD

BC
8
BD

☻
T
T
禁忌搜索
四城市非对称TSP问题