禁忌搜索算法.ppt

禁忌搜索算法
局部搜索
邻域的概念
局部搜索算法
局部搜索示例
禁忌搜索
算法的主要思路
禁忌搜索示例
禁忌搜索的关键参数和操作
变化因素
禁忌表
其他
禁忌搜索的实现与应用
30城市TSP问题(d*= by D B Fogel)
基于禁忌搜索算法的系统辨识
函数优化问题中
在距离空间中,通常的邻域定义是以一点为中心的一个球体;
组合优化问题中
禁忌搜索算法
邻域的概念
例:
TSP问题解的一种表示方法为D={x=(i1,i2,…,in)| i1,i2,…,in是1,2,…,n的排列},定义它的邻域映射为swap,即x中的两个元素进行对换,N(x)2=n(n-1)/2个邻居和x本身。
例如:x=(1,2,3,4),则C42=6,N(x)={(1,2,3,4), (2,1,3,4), (3,2,1,4), (4,2,3,1), (1,3,2,4), (1,4,3,2), (1,2,4,3)}
禁忌搜索算法
领域的概念
例:
TSP问题解的邻域映射可由swap,推广到k-opt。
邻域概念的重要性
邻域的构造依赖于移动操作(move),
邻域的结构在现代优化算法中起重要的作用。
禁忌搜索算法
领域的概念
算法的提出
禁忌搜索(Tabu search)是局部邻域搜索算法的推广,Fred Glover在1986年提出这个概念,进而形成一套完整算法。
算法的特点
禁忌——禁止重复前面的工作。
跳出局部最优点。
/~glover/
禁忌搜索算法
算法的主要思路
5
3
4
6
8
5
6
7
1
Max-cut problem: 将一个图切成2个部分(子图),2个子图之间的边数最多.
禁忌搜索算法
禁忌搜索算法示例
7
4
5
6
3
2
1
1
0
2
0
3
0
4
0
5
0
6
0
7
0
1
1
2
1
3
0
4
0
5
-1
6
-2
7
1
函数值变化:f = 5
禁忌表
Move: one-flip
Step 1: flip 1
禁忌搜索算法
禁忌搜索算法示例
4
5
6
3
2
1
1
3
2
0
3
0
4
0
5
0
6
0
7
0
1
-1
2
-1
3
0
4
0
5
1
6
-2
7
-1
函数值变化:f = 6
禁忌表
Move: one-flip
7
Step 2: flip 5
禁忌搜索算法
禁忌搜索算法示例
4
6
3
2
1
1
2
2
0
3
0
4
0
5
3
6
0
7
0
1
-3
2
-1
3
2
4
-2
5
-1
6
-2
7
-1
函数值变化:f = 7
禁忌表
Move: one-flip
7
5
Step 3: flip 3
禁忌搜索算法
禁忌搜索算法示例
4
6
2
1
1
1
2
0
3
3
4
0
5
2
6
0
7
0
1
-3
2
-3
3
-2
4
0
5
-3
6
-2
7
-3
函数值变化:f = 9
禁忌表
Move: one-flip
7
5
3