当前位置: 首页 > >

禁忌搜索算法

发布时间:

禁忌搜索算法
(Tabu Search) 吴浩博

1 局部搜索 2 禁忌搜索
1 算法的主要思路 2 禁忌搜索示例

3 禁忌搜索的关键参数和操作
3.1 变化因素 3.2 禁忌表 3.3 其他

4 禁忌搜索的实现与应用
4.1 图结点染色

1 局部搜索
局部搜索示例
?

n个城市的对称旅行商问题

简单易行,但无法保证全局最优性;
局部搜索主要依赖起点的选取和邻域的结构; 为了得到好的解,可以比较不同的邻域结构和不同 的初始点; 如果初始点的选择足够多,

总可以计算出全局最优解。

2 禁忌搜索
2.1 算法的背景
?

禁忌搜索算法(Tabu Search)是由美国 科罗拉多州大学的Fred Glover教授在 1986年左右提出来的,是一个用来跳出 局部最优的搜寻方法。在解决最优问题 上,一般区分为两种方式:一种是传统 的方法,另一种方法则是一些启发式搜 索算法。

2 禁忌搜索
2.1 算法的背景 使用传统的方法,我们必须对每一个问题都去设 计一套算法,相当不方便,缺乏广泛性,优点在 于我们可以证明算法的正确性,我们可以保证找 到的答案是最优的;而对于启发式算法,针对不 同的问题,我们可以套用同一个架构来寻找答案, 在这个过程中,我们只需要设计评价函数以及如 何找到下一个可能解的函数等,所以启发式算法 的广泛性比较高,但相对在准确度上就不一定能 够达到最优,但是在实际问题中启发式算法那有 着更广泛的应用。

2 禁忌搜索
2.1 算法的背景
?

禁忌搜索是一种亚启发式随机搜索算法,它从一个初始可 行解出发,选择一系列的特定搜索方向(移动)作为试探,选 择实现让特定的目标函数值变化最多的移动。为了避免陷 入局部最优解,TS搜索中采用了一种灵活的“记忆”技术 ,对已经进行的优化过程进行记录和选择,指导下一步的 搜索方向。 TS是人工智能的一种体现,是局部领域搜索的 一种扩展。禁忌搜索是在领域搜索的基础上,通过设置禁 忌表来禁忌一些已经历的操作,并利用藐视准则来奖励一 些优良状态,其中涉及邻域 、禁忌表、禁忌长度、候选解 、藐视准则等影响禁忌搜索算法性能的关键因素。迄今为 止,TS算法在组合优化等计算机领域取得了很大的成功, *年来又在函数全局优化方面得到较多的研究,并大有发 展的趋势。

2 禁忌搜索
2.2 禁忌搜索示例
?

四城市非对称TSP问题

初始解x0=(ABCD),f(x0)=4,邻域映射为两个城市 顺序对换的2-opt,始、终点都是A城市。

2 禁忌搜索
2.2 禁忌搜索示例
?

四城市非对称TSP问题

第1步
解的形式 A B C D f(x0)=4 禁忌对象及长度 B A B C C D 候选解
对换 评价值

CD BC BD

4.5 ? 7.5 8

2 禁忌搜索
2.2 禁忌搜索示例
?

四城市非对称TSP问题

第2步
解的形式 A B D C f(x1)=4.5 禁忌对象及长度 B A B C 3 C D 候选解
对换 评价值

CD BC BD

4.5 T 3.5 ? 4.5

2 禁忌搜索
2.2 禁忌搜索示例
?

四城市非对称TSP问题

第3步
解的形式 A C D B f(x2)=3.5 禁忌对象及长度 B A B 3 C 2 C D 候选解
对换 评价值

CD BC BD

8 T 4.5 T 7.5 ?

2 禁忌搜索
2.2 禁忌搜索示例
?

四城市非对称TSP问题

第4步
解的形式 A C B D f(x3)=7.5 禁忌对象及长度 B A B 2 C 3 1 C D 候选解
对换 评价值

CD BC BD

4.5 T 4.5 T 3.5 T

禁忌长度的选取

2 禁忌搜索
2.2 禁忌搜索示例
?

四城市非对称TSP问题

第4步(如果减小禁忌长度)
解的形式 A C B D f(x3)=7.5 禁忌对象及长度 B A B 1 C 2 0 C D 候选解
对换 评价值 4.5 ?

CD BC BD

4.5 T 3.5 T

2 禁忌搜索
2 禁忌搜索示例
?

四城市非对称TSP问题

第5步
解的形式 A D B C f(x4)=4.5 禁忌对象及长度 B A B 0 C 1 2 C D 候选解
对换 评价值

CD BC BD

7.5 T 8 ? 4.5 T

TS算法 框架

? ?

?

?

?

?

(1)是否有其他形式的候选集? (2)禁忌的长度如何确定?如果在算法中记忆下搜索到 的当前最优解,极端的两种情况是:一是将所有的对换 个数作为禁忌长度,此时等价于将候选集中的所有的对 换遍历;另外则取为1,这等价于局部搜索算法。 (3)是否有评价值的其他替代形式?有时计算目标值的 工作量较大,或无法接受计算目标值所花费的时间,于 是需要其他的方法。 (4)被禁的对换能否再一次解禁?有这样的直观现象, 当搜索到一个局部最优解后,它邻域中的其他状态都被 禁,我们是否解禁一些状态以便跳出局部最优?解禁的 功能就是为了获得更大的搜索范围,以免陷入局部最优 。 (5)如何利用更多的信息?在禁忌搜索算法中,还可记 录其他一些信息。如一个被禁对象(交换)被禁的次数 ,评价值变化的大小等。 (6)终止原则,即一个算法停止的条件,怎样给出?

3 禁忌搜索的关键参数和操作
3.1 变化因素
?

禁忌表的主要指标(两项指标)

禁忌对象:禁忌表中被禁的那些变化元素
禁忌长度:禁忌的步数
?

状态变化(三种变化) 解的简单变化 解向量分量的变化

目标值变化

3 禁忌搜索的关键参数和操作
3.1 变化因素
?

解的简单变化

假设x, y ? D,邻域映射为 N,其中D为优化问题的定义域, 则简单解变化 x ? y ? N ( x) 是从一个解变化到另一 个解。

这种变化最为简单,如从(ABCDE)变到(ABCED)

3 禁忌搜索的关键参数和操作
3.1 变化因素
?

向量分量的变化

设原有的解向量为(x1, …, xi-1, xi, xi+1, …, xn),向量 分量的最基本变化为
(x1, …, xi-1, xi, xi+1,…, xn)→(x1, …, xi-1, yi, xi+1,…, xn) 即只有第i个分量发生变化。 也包含多个分量变化的情形。

3 禁忌搜索的关键参数和操作
3.1 变化因素
?

目标值的变化

目标值的变化隐含着解集合的变化。

3 禁忌搜索的关键参数和操作
3.2 禁忌表
?

禁忌对象的选取

情况1:禁忌对象为简单的解变化

禁忌长度为4,从2-opt邻域中选出最佳的5个解组 成候选集Can_N(xnow),初始解xnow=x0=(ABCDE), f(x0)=45,H={(ABCDE;45)}。

3 禁忌搜索的关键参数和操作
3.2 禁忌表
?

禁忌对象的选取

情况1:禁忌对象为简单的解变化
第1步—— xnow=(ABCDE),f(xnow)=45,H={(ABCDE;45)} Can_N(xnow)={(ACBDE;43),(ABCDE;45), (ADCBE;45),(ABEDC;59),(ABCED;44)}。

xnext=(ACBDE)

3 禁忌搜索的关键参数和操作
3.2 禁忌表
?

禁忌对象的选取

情况1:禁忌对象为简单的解变化
第2步—— xnow=(ACBDE),f(xnow)=43,H={(ABCDE;45), (ACBDE;43)} Can_N(xnow)={(ACBDE;43),(ACBED;43), (ADBCE;44),(ABCDE;45),(ACEDB;58)}。 xnext=(ACBED)

3 禁忌搜索的关键参数和操作
3.2 禁忌表
?

禁忌对象的选取

情况1:禁忌对象为简单的解变化
第3步—— xnow=(ACBED),f(xnow)=43,H={(ABCDE;45), (ACBDE;43) ,(ACBED;43)} Can_N(xnow)={(ACBED;43),(ACBDE;43), (ABCED;44),(AEBCD;45),(ADBEC;58)}。 xnext=(ABCED)

3 禁忌搜索的关键参数和操作
3.2 禁忌表
?

禁忌对象的选取

情况1:禁忌对象为简单的解变化
第4步—— xnow=(ABCED),f(xnow)=44,H={(ABCDE;45), (ACBDE;43) ,(ACBED;43) ,(ABCED;44)} Can_N(xnow)={(ACBED;43),(AECBD;44), (ABCDE;45),(ABCED;44),(ABDEC;58)}。 xnext=(AECBD)

此时H已达到4个解,新选入的解代替最早被禁的解

3 禁忌搜索的关键参数和操作
3.2 禁忌表
?

禁忌对象的选取

情况1:禁忌对象为简单的解变化
第5步—— xnow=(AECBD),f(xnow)=44,H={(ACBDE;43) , (ACBED;43) ,(ABCED;44) ,(AECBD;44)} Can_N(xnow)={(AEDBC;43),(ABCED;44), (AECBD;44),(AECDB;44),(AEBCD;45)}。 xnext=(AEDBC)

3 禁忌搜索的关键参数和操作
3.2 禁忌表
?

禁忌对象的选取

情况2:禁忌对象为分量变化

禁忌长度为3,从2-opt邻域中选出最佳的5个解组 成候选集Can_N(xnow),初始解xnow=x0=(ABCDE), f(x0)=45。

3 禁忌搜索的关键参数和操作
3.2 禁忌表
?

禁忌对象的选取

情况2:禁忌对象为分量变化
第1步—— xnow=(ABCDE),f(xnow)=45,H=Φ Can_N(xnow)={(ACBDE;43),(ADCBE;45), (AECDB;60),(ABEDC;59),(ABCED;44)}。

xnext=(ACBDE)
由于H为空集,从候选集中选最好的一个,它是B与C 的对换构成

3 禁忌搜索的关键参数和操作
3.2 禁忌表
?

禁忌对象的选取

情况2:禁忌对象为分量变化
第2步—— xnow=(ACBDE),f(xnow)=43,H={(B,C)} Can_N(xnow)={(ACBED;43),(ADBCE;44), (ABCDE;45),(ACEDB;58),(AEBDC;59)}。

xnext=(ACBED)

3 禁忌搜索的关键参数和操作
3.2 禁忌表
?

禁忌对象的选取

情况2:禁忌对象为分量变化
第3步—— xnow=(ACBED),f(xnow)=43,H={(B,C),(D,E)} Can_N(xnow)={(ACBDE;43),(ABCED;44), (AEBCD;45),(ADBEC;58),(ACEBD;58)}。

xnext=(AEBCD)
可以看出,情况2 比情况1禁忌的范围要更大一些

3 禁忌搜索的关键参数和操作
3.2 禁忌表
?

禁忌对象的选取

情况3:禁忌对象为目标值变化

禁忌长度为3,从2-opt邻域中选出最佳的5个解组 成候选集Can_N(xnow),初始解xnow=x0=(ABCDE), f(x0)=45。

3 禁忌搜索的关键参数和操作
3.2 禁忌表
?

禁忌对象的选取

情况3:禁忌对象为目标值变化
第1步—— xnow=(ABCDE),f(xnow)=45,H={45} Can_N(xnow)={(ABCDE;45),(ACBDE;43), (ADCBE;45),(ABEDC;59),(ABCED;44)}。

xnext=(ACBDE)

3 禁忌搜索的关键参数和操作
3.2 禁忌表
?

禁忌对象的选取

情况3:禁忌对象为目标值变化
第2步—— xnow=(ACBDE),f(xnow)=43,H={45,43} Can_N(xnow)={(ACBDE;43),(ACBED;43), (ADBCE;44),(ABCDE;45),(ACEDB;58)}。

xnext=(ADBCE)
这种方法禁忌的范围更大

3 禁忌搜索的关键参数和操作
3.2 禁忌表
?

禁忌对象的选取

解的简单变化比解的分量变化和目标值变化的受禁 范围要小,可能造成计算时间的增加,但也给予了 较大的搜索范围;
解分量的变化和目标值变化的禁忌范围大,减少了 计算时间,可能导致陷在局部最优点。

3 禁忌搜索的关键参数和操作
3.2 禁忌表

t ?[tmin , tmax ]

3 禁忌搜索的关键参数和操作
3.2 禁忌表
?

禁忌长度的选取

禁忌长度过短,一旦陷入局部最优点,出现循环无 法跳出;
禁忌长度过长,造成计算时间较大,也可能造成计 算无法继续下去。

3 禁忌搜索的关键参数和操作
3.2 禁忌表
?

特赦(藐视)原则

(1)基于评价值的规则,若出现一个解的目标值 好于前面任何一个最佳候选解,可特赦;
(2)基于最小错误的规则,若所有对象都被禁忌, 特赦一个评价值最小的解;

3 禁忌搜索的关键参数和操作
3.3 其他
?

候选集合的确定 (1)从邻域中选择若干目标值最佳的邻居入选; (2)随机选取。

3 禁忌搜索的关键参数和操作
3.3 其他
?

评价函数

(1)直接评价函数,通过目标函数的运算得到评 价函数;
(2)间接评价函数,构造其他评价函数替代目标 函数,应反映目标函数的特性,减少计算复杂性。

3 禁忌搜索的关键参数和操作
3.3 其他
?

记忆频率信息

根据记忆的频率信息(禁忌次数等)来控*刹 数(禁忌长度等)。
例如: 如果一个元素或序列重复出现或目标值变化很小, 可增加禁忌长度以避开循环;

如果一个最佳目标值出现频率很高,则可以终止计 算认为已达到最优值。

3 禁忌搜索的关键参数和操作
3.3 其他
?

终止规则

(1)确定步数终止,优点是易于操作和控制时间, 但无法保证解的效果,应记录当前最优解;
(2)频率控制原则,当某一个解、目标值或元素 序列的频率超过一个给定值时,终止计算; (3)目标控制原则,如果在一个给定步数内,当 前最优值没有变化,同规则2,可终止计算。

3 禁忌搜索的关键参数和操作
3.3 其他

禁忌算法的特征由禁忌对象和长度、 候选集和评价函数、停止规则和一些 计算信息组成 ? 综合上面的讨论,给出了他们的选取 禁忌对象,禁忌长度,特赦规则, 候选集合,评价函数,终止规则
?

禁忌搜索算法: ? step1 选定一个初始解xnow及给以禁忌表H等 于空集; ? step2 若满足停止规则,停止计算;否则,在 xnow的邻域N(H,xnow)中选出满足禁忌要 求的候选集Can_N(xnow);在Can_N(xnow)中 选一个评价值最佳的解xnext,xnow:=xnest ;更新历史记录H,重复step2. 禁忌算法的step2中,xnow的邻域N(H,xnow )中满足禁忌要求的元素包含两类:一类是那些 没有被禁忌的元素,另一类是可以被解除禁忌的 元素。

4 禁忌搜索的应用和实现
4.1 图结点染色

举一个参考文献4中的例子: 给定一个无向图G,其顶点集V={1,2, ···,n},E是边集,求最少用几种颜色k,使 不同颜色的点间没有边相连。
?

求最小的k,使(V1,···Vk)是V的一个划分 。

总结
与传统的优化算法相比,TS算法的主要特点是: 1.从移动规则看,每次只与最优点比较,而不与经过点比较 ,故可以爬出局部最优。 2.选优规则始终保持曾经达到的最优点,所以即使离开了全 局最优点也不会失去全局最优性。 3.终止规则不以达到局部最优为终止规则,而以最大迭代次 数、出现频率限制或者目标值偏离成都为终止规则 ? 禁忌搜索是对人类思维过程本身的一种模拟,它通过对一些 局部最优解的禁忌(也可以说是记忆)达到接纳一部分较差 解,从而跳出局部搜索的目的。因而在计算搜索领域有着广 泛应用。
?

参考文献
?

维基百科
http://en.wikipedia.org/wiki/Tabu_search

? ? ?

?

现代优化计算方法 清华大学出版社 陈丽 禁忌搜索算法的研究及其在TSP的应用 2010 Hertz A, de Werra D.The Tabu Search metaheuristics:how we use it . Annals of Mathematics and Atrifical Intelligence,1990,1:111~121 百度百科 http://baike.baidu.com/view/354708.htm http://baike.baidu.com/view/1117099.htm

谢谢!




友情链接: