文档介绍：1
第四章禁忌搜索( Tabu Search )
、长期表的使用
3的邻域
搜索陷入循环
1的邻域
1
2的邻域
2
4的邻域
4
3
在邻域中找到最好的解
3
,90年代初得到广泛重视。
是GA之后提出的另一启发式优化方法。
模仿人类的记忆功能,使用禁忌表封锁刚搜索过的区域,以避免迂回搜索。
同时赦免禁忌区域中的一些优良状态,以保证搜索的多样性。
(1)
4
TS的基本思想——避免在搜索过程中的循环
只进不退的原则——用Tabu表锁住退路,将近期历史搜索过程存放在禁忌表中,防止算法重新进入。
不以局部最优作为停止准则,算法接受劣解,只要不在禁忌表的较好解都可作为下一次迭代的初始解。
邻域选优的规则模拟了人类的记忆功能——找过的地方都记下来,不再找第二次。随着迭代的进行,禁忌表不断更新,一定迭代次数后,早期进入禁忌表解被解禁退出。
(2)
5
禁忌表作用示例(1)
七种不同绝缘材料构成一种绝缘体,如何排列七种材料使得绝缘效果最好?
绝缘效果以绝缘数值表示,数值越大,效果越好。
某次迭代后,材料的排列顺序为2-4-7-3-5-6-1,交换各种材料对绝缘效果的改善情况见下表:
交换的材料
绝缘效果改善
1,3
2(正值表示绝缘效果变好)
2,3
1
3,4
-1(负值表示绝缘效果变坏)
1,7
-2
1,6
-4
…
…
6
禁忌表作用示例(2)
可见,交换材料1和3可增加绝缘数值2,并且改善效果最好,交换后2-4-7-1-5-6-,将交换(1,3)加入禁忌表。
此时两两交换材料对绝缘效果的影响见下表。
交换的材料
绝缘效果
1,3
-2
2,4
-4
6,7
-6
4,5
-7
3,5
-9
…
…
7
禁忌表作用示例(3)
上表看出,交换(1,3)对绝缘数值的降低最小,但是交换后又回到以前的状态,为避免回到上一次交换前的状态,采用禁忌表。
所以,选择交换(2,4),是其它选择中使绝缘数值降低最小的一对。
此禁忌表中存放的不是解,而是解的移动。
为实现全局搜索,往往设置渴望水平,若一个移动达到渴望水平,能跳离局部最优,该移动可以不受禁忌表的限制,称为破禁。
8
TS的要素构成
(1) 编码方法
(2) 适值函数的构造
(3) 初始解的获得
(4) 移动与邻域移动
(5) 禁忌表(Tabu List)
(6) 选择策略
(7) 渴望水平函数(Aspiration Level Function)
(8) 停止准则——与GA相似
(3)
9
(1) 编码方法
灵活的选择编码方法,如背包的0-1编码。
同一问题有多种编码方法,如分组问题:不相同的n件物品分为m组,n=9,m=3.
编码1:
1-3-4-0-2-6-7-5-0-8-9 (1-4-3-0-6-2-5-7-0-9-8)
0起到隔开作用1-3-4分为一组,2-6-7-5一组,8-9一组。
编码2:
1-2-1-1-2-2-2-3-3 (2-1-2-2-1-1-1-3-3)
表示1-3-4分为一组,2-6-7-5一组,8-9一组
10
(2) 适值函数的构造
适值函数是用来对搜索状态进行评价的。
对目标函数的任何变形都可作为目标函数,只要该变形保持严格单调。