禁忌搜索算法

• Tabu list { }，长度为2。 记录从当前解生 成新的解的过程中，产生的新的相邻关系 • M=2 • N=4
Start
Tabu list 初始化(清空) 设M,N的值
求得初始解 BS=初始解 n=0;NI=0
是
是 最好的新解比 BS好？ 接受新的解用新的 It’s in tabu？ 解替换当前解 否 是 接受新的解；用新 的解替换当前解 更新tabulist
禁忌表长度
太短：计算速度快，但容易陷入死循环 太长：计算速度慢 在搜索过程中，禁忌表长度设为固定 在搜索过程中，禁忌表长度可动态变化
禁忌表长度：5—10
藐视准则（Aspiration criterion）
如果找到了一个新的解比当前记录的最好 解还要好，那么即使从当前得到这个新的 解被tabu list禁止，仍然接受这个新的解， 并更新tabu list. 即tabu list对这个解没有禁 止作用
Intensification
求得一系列候选解，并按优劣排序
用插值的方法求得候选解 随机数＝2
Sequence 143256 431256 432156 432516 432561
The length of the route 29 33 35 36 38
Start
Tabu list 初始化(清空) 设M,N的值
Sequence 413256 143256 134256 132546 132564
The length of the route 30 35 38 40 45
Start
Tabu list 初始化(清空) 设M,N的值
求得初始解 BS=初始解 n=0;NI=0
是
是 最好的新解比 BS好？ 接受新的解用新的 It’s in tabu？ 解替换当前解 否 是 接受新的解；用新 的解替换当前解 更新tabulist
在邻域中找到最好的解
加入禁忌表，避免陷入循环
禁忌表长度为3：{①, ②, ③} 规则：不得接受与禁忌表中相同的解 禁忌表的变化： 第一步搜索时{ } 第二步搜索时{① } 第三步搜索时{①, ②, } 第四步搜索时{①, ②, ③}
避免循环的原理：当前解为④时，其领域中 最好的解为①，原本下一步应为①，但其与 禁忌表中的元素相同，所以选择次好的解⑤， 从而避免死循环
TSP算例
City to city
1 1 2 3
2 12
3 4 11
4 7 20 6
5 9 13 17
6 10 8 13
4
5 6
6
9
15
Start
Tabu list 初始化(清空) 设M,N的值
求得初始解 BS=初始解 n=0;NI=0
是
是 最好的新解比 BS好？ 接受新的解用新的 It’s in tabu？ 解替换当前解 否 是 接受新的解；用新 的解替换当前解 更新tabulist
否
是否为最后一 个候选解？
用新的解替换 当前解;
NI=0
否 找出下一个 次好的新解
求得一系列候选解， 并按优劣排序
NI=NI+1
n=n+1 NI=M? 是 Diversification NI=0 是 n<N 否 End 否
Intensification
判断是否为tabu, 决定接受与否
接受最好的候选解，并替换当前解
Intensification
判断是否为tabu, 决定接受与否
BS
Sequence The length of the route
132456 28 Tabu list {41， }，NI=1,n=1
考虑下一个最好的候选解
当前解 候选解
Sequence The length of the route 30 413256 33 431256 新生成相邻关系(3,1), is not Tabu! accept it
否
是否为最后一 个候选解？
用新的解替换 当前解;
NI=0
否 找出下一个 次好的新解
求得一系列候选解， 并按优劣排序
NI=NI+1
n=n+1 NI=M? 是 Diversification NI=0 是 n<N 否 End 否
Intensification
求得初始解 BS=初始解
初始解
Sequence The length of the route 132456 28
NI=0
否 找出下一个 次好的新解
Tabu Search
• 特点 – Neighborhood search + memory • Neighborhood search • Memory –Record the search history –Forbid cycling search
搜索陷入循环
1的邻域
2 2的邻域
1
3 4的邻域 4
Sequence The length of the route 当前解 413256 30
BS
Sequence The length of the route
132456 28
Tabu list {41， }，NI=1,n=1
Start
Tabu list 初始化(清空) 设M,N的值
求得初始解 BS=初始解 n=0;NI=0
要设计一个禁忌搜索算法，需要确 定以下环节
1)初始解和适配值函数（目标函数）； 2)邻域结构(如何生成相邻解)和禁忌对象(禁 忌表中的元素)； 3)候选解选择； 4)禁忌表及其长度； 5)藐视准则 6)集中搜索和分散搜索策略 7)终止准则。 ’
变量定义：
n ＝ 搜索次数 N ＝ 搜索N 次，程序结束
NI=NI+1
n=n+1 NI=M? 是 Diversification NI=0 是 n<N 否 End 否
Intensification
判断是否为tabu, 决定接受与否
BS
Sequence The length of the route
132456 28 Tabu list {41， }，NI=1,n=1
NI ＝连续没有找到更好解的次数
M ＝连续M次没有找到更好解， 执行分散搜索策略 BS ＝ 找到的最好的解
Start
Tabu list 初始化(清空) 设M,N的值
求得初始解 BS=初始解 n=0;NI=0
是
是 最好的候选 解比BS好？ 接受新的解用新的 It’s in tabu？ 解替换当前解 否 是
否
是否为最后一 个候选解？
用新的解替换 当前解;
NI=0
否 找出下一个 次好的新解
求得一系列候选解， 并按优劣排序
NI=NI+1
n=n+1 NI=M? 是 Diversification NI=0 是 n<N 否 End 否
Intensification
Tabu list 初始化(清空)设M,N的值
否
是否为最后一 个候选解？
接受新的解；用新 的解替换当前解
更新tabulist
用新的解替换 BS;
NI=0
否 找出下一个 次好的新解
求得一系列候选解， 并按优劣排序
NI=NI+1
n=n+1 否 NI=M? 是 Diversification NI=0 是 n<N 否 End
Intensification
否
是否为最后一 个候选解？
用新的解替换 当前解;
NI=0
否 找出下一个 次好的新解
求得一系列候选解， 并按优劣排序
NI=NI+1
n=n+1 NI=M? 是 Diversification NI=0 是 n<N 否 End 否
Intensification
求得一系列候选解，并按优劣排序
用插值的方法求得候选解：生成随机数r=[1,6],选取 第r个位置上的元素，插入到其余位置前面 随机数＝4
是
是 最好的新解比 BS好？ 接受新的解用新的 It’s in tabu？ 解替换当前解 否 是 接受新的解；用新 的解替换当前解 更新tabulist
否
是否为最后一 个候选解？
用新的解替换 当前解;
NI=0
否 找出下一个 次好的新解
求得一系列候选解， 并按优劣排序
NI=NI+1
n=n+1 NI=M? 是 Diversification NI=0 是 n<N 否 End 否
Start
Tabu list 初始化(清空) 设M,N的值
求得初始解 BS=初始解 n=0;NI=0
是
是 最好的新解比 BS好？ 接受新的解用新的 It’s in tabu？ 解替换当前解 否 是 接受新的解；用新 的解替换当前解 更新tabulist
否
是否为最后一 个候选解？
用新的解替换 当前解;
是
是 最好的新解比 BS好？ 接受新的解用新的 It’s in tabu？ 解替换当前解 否 是 接受新的解；用新 的解替换当前解 更新tabulist
否
是否为最后一 个候选解？
用新的解替换 当前解;
NI=0
否 找出下一个 次好的新解
求得一系列候选解， 并按优劣排序
NI=NI+1
n=n+1 NI=M? 是 Diversification NI=0 是 n<N 否 End 否
BS
Sequence The length of the route
132456
28
Start
Tabu list 初始化(清空) 设M,N的值
求得初始解 BS=初始解 n=0;NI=0
是
是 最好的新解比 BS好？ 接受新的解用新的 It’s in tabu？ 解替换当前解 否 是 接受新的解；用新 的解替换当前解 更新tabulist
假设记录生成相邻解的方法，Tabu list = {②, ③, ④},下一步采用②方法生成了迄今 为止最好的解，仍然接受这个，更新Tabu list={②, ③, ②},
分散搜索（Diversification）和 集中搜索（Intensification）策略
• 分散搜索：是为了对整个解的空间 进行更广泛的覆盖，而不是仅仅局 限在某个局部的区域。
1的邻域 1
2 2的邻域 3
5 4的邻域
4
禁忌表的更新
更新原则：先进先出 {①, ②, ③} {②, ③, ④}
{Biblioteka Baidu , ④, ⑤} ….
禁忌表中元素
禁忌表中元素的可以是完整的解，可以是完 整解的一部分，也可以是采取的一个生成相 邻解的动作等等
完整解：{12345,13245,31245} 生成相邻解的操作（如交换的动作）： {32, 31} 从12345开始，取3出来，插入1245 每个位置前面
求得初始解 BS=初始解 n=0;NI=0
是
是 最好的新解比 BS好？ 接受新的解用新的 It’s in tabu？ 解替换当前解 否 是 接受新的解；用新 的解替换当前解 更新tabulist
否
是否为最后一 个候选解？
用新的解替换 当前解;
NI=0
否 找出下一个 次好的新解
求得一系列候选解， 并按优劣排序
考虑最好的候选解
当前解 候选解
Sequence The length of the route 30 413256 29 143256 新生成相邻关系(14), is Tabu! Reject it
Start
Tabu list 初始化(清空) 设M,N的值
求得初始解 BS=初始解 n=0;NI=0
禁忌搜索 Tabu Search
禁忌搜索概述
• 禁忌搜索(Tabu Search或Taboo Search， 简称TS)的思想最早由Glover(1986)提出， 它是对局部邻域搜索的一种扩展，是一种 全局逐步寻优算法，是对人类智力过程的 一种模拟。
禁忌搜索概述
• TS算法通过引入一个灵活的存储结构和相应的禁 忌准则来避免迂回搜索，并通过藐视准则来赦免 一些被禁忌的优良状态，进而保证多样化的有效 探索以最终实现全局优化。 • 相对于模拟退火和遗传算法，TS是又一种搜索特 点不同的算法。迄今为止，TS算法在组合优化、 生产调度、机器学习、电路设计和神经网络等领 域取得了很大的成功，近年来又在函数全局优化 方面得到较多的研究，并大有发展的趋势。
无邻域的搜索
有邻域的搜索
有邻域的搜索 & 分散搜索策略
分散搜索（Diversification）和 集中搜索（Intensification）策略
• 集中搜索：如果当前搜索区域内发 现了比较好的解，如果进一步对当 前区域进行更集中的搜索，那么可 能会发现更多更好的解。
• 分散搜索策略（Diversification strategy）在当前 搜索区域内进行了一定次数的搜索了之后（如 25次），若不能发现更好的解，那么就执行分 散搜索策略。把tabu list清空，然后从一个新 的初始解开始搜索。 • 集中搜索：如果最好解的记录被更新，那么就 执行集中搜索策略，即清空tabu list. 这样可以 在当前区域进行更自由的搜索。