第三章禁忌搜索-.ppt

第三章禁忌搜索-
第三章 禁忌搜索
一. 前言
二. 禁忌搜索
三. 算法举例
四. 短、中、长期表的使用

2
问题描述

目标函数
约束条件
定义域
3
局域搜索
邻域的概的解从表中释放（解禁）

21
构成要素
选择策略
选择策略的作用：保证TS具有跳出局优的能力
当前解x每一步总是移动到邻域N(x)中未被禁忌的最优解，即若
则令 ，本次移动到邻域N(x)中未被禁忌的最优解

22
构成要素
渴望水平
渴望水平A(s,x)是一个取决于s和x的值，若有
成立，则s(x)不受T表限制。也就是说即使存在
x仍然可以移动到s(x)。
A(s,x)一般选取为历史上所能达到的最优函数值。

禁忌策略和渴望水平构成了TS的两大核心移动规则
23
构成要素
停止准则
设定最大迭代次数
得到满意解
设定某个对象的最大禁忌频率

24
算法流程
Step 1
选一个初始点 x( )，令 ， ，渴望水平 ，迭代指标 k=0；
Step 2
若 ，则停止；否则令k=k+1；若k>NG(其中NG为最大迭代次数)，则停止；

注： 表示非正常终止，造成的原因：邻域小，T表长。正常设置为T表长度<邻域大小。Step 2的作用是设置循环体出口。
25
算法流程
Step 3
若 且 ，令 ，转Step 5；
Step 4
若 ，令 ；

注：Step 3的作用破禁检查
注：Step 4的作用邻域选优
26
算法流程
Step 5
若 ，令 ， ，
；
Step 6
更新T表，转Step 2 ；

注：Step 5的作用更新历史最好解及渴望水平
注：x存入T表中的第一个位置
27
TS克服局优分析
从邻域搜索的方法看
移向N(x)\T中最好的解，而不与当前解比较，
是 N(x)\T中的最好点，但
可能劣于

28
TS克服局优分析
从选优规则看
始终保持历史最优解，不以当前解为最优
从停止规则上看
不以最优判据为停止规则，而是指定最大迭代步数为停止条件，这样不能保证最优性。

29
问题提出
由7层不同的绝缘材料构成的一种绝缘体，应如何排
列顺序，可获得最好的绝缘性能?

30
算法设计
编码方式：顺序编码
初始解的产生：随机产生，如2-5-7-3-4-6-1
适值函数：极大化目标值
邻域移动方式：2-opt，即两两交换
其他参数：禁忌对象为邻域移动方式，T表长度设为3，NG设为5

31
初始表
初始编码：2-5-7-3-4-6-1
结论：交换4和5

移动
5，4
6
7，4
4
3，6
2
2，3
0
4，1
-1
……
……
T表
1
2
3
32
迭代1编码：2-4-7-3-5-6-1

结论：交换1和3

移动
3，1
2
2，3
1
3，4
-1
7，1
-2
6，1
-4
……
……
T表
1
4，5
2
3
33
迭代2编码：2-4-7-1-5-6-3
结论：因交换1和3已在禁忌表中，故只能交换2和4

移动
1，3
-2
2，4
-4
7，6
-6
4，5
-7
5，3
-9
……
……
T表
1
1，3
2
4，5
3
若选择这项 C(x) =16，渴望水平
不能发生作用
34