PDF《第四章 禁忌搜》

169

169

第四章

第四章 禁忌搜 禁忌搜 索索170

170

第四章

第四章 禁忌搜索( 禁忌搜索( Tabu Tabu Search Search ) ) 一一.

.导言 导言 二二.TS .TS的基本原理及步骤 的基本原理及步骤 三三.TS .TS的算法步骤 的算法步骤 四四.TS .TS可以克服局优的分析 可以克服局优的分析 五五.TS .TS举例 举例 六六.TS .TS的中、长期表的使用 的中、长期表的使用 七七.TS .TS表的应用举例 表的应用举例 八八. .学习 学习TS TS的几点体会 的几点体会

171 171 一一. .导言 导言( (1 1) ) 1. 1. TS TS的提出 的提出

1977 1977年年F.Glover F.Glover提出 提出TS TS , ,90 90年代初得到广 年代初得到广 泛重视 泛重视

172 172 一一. .导言( 导言(2 2) ) 2. 2. TS TS的基本思想 的基本思想―― ――避免在搜索过程中的循环 避免在搜索过程中的循环 ① ① 只进不退的原则 只进不退的原则―― ――用用Tabu Tabu表锁住退路 表锁住退路 ② ② 不以局部最优作为停止准则 不以局部最优作为停止准则 ③ ③ 邻域选优的规则模拟了人类的记忆功能 邻域选优的规则模拟了人类的记忆功能―― ―― 找过的地方都记下来,不再找第二次 找过的地方都记下来,不再找第二次

173 173 一一. .导言( 导言(3 3) ) 3. 3. TS TS的要素构成 的要素构成 ① ① 禁忌表 禁忌表( (Tabu Tabu List) List) ② ② 渴望水平函数 渴望水平函数(Aspiration Level Function) (Aspiration Level Function) ③ ③ 移动规则 移动规则―― ――邻域选优 邻域选优 ④ ④ 选优规则 选优规则―― ――保持历史上的最优解 保持历史上的最优解 ⑤ ⑤ 停止准则 停止准则―― ――与与GA GA相似 相似

174 174 二二. . TS TS的基本原理及步骤 的基本原理及步骤( (1 1) ) 1. 1. 问题的描述及邻域的概念 问题的描述及邻域的概念 TS TS仅用于离散优化,排斥实优化 仅用于离散优化,排斥实优化 ( ) 是离散值空间 X . . min X x t s x C ∈

175 175 二二. . TS TS的基本原理及步骤 的基本原理及步骤( (2 2) ) ( ) { } ( ) u d , x x ud S x s s x ud s X S x = + = = + ∈ 邻域的概念: 的邻域移动为 s , 为单位步长, 为方向,则: 邻域 是邻域移动可达到的解的集合.

176 176 二二. . TS TS的基本原理及步骤 的基本原理及步骤( (3 3) ) 邻域举例: 邻域举例: x x =[0,1,0,0,1,0,0] =[0,1,0,0,1,0,0] u=1, u=1, d d =[0,0,1,0,0,0,0] =[0,0,1,0,0,0,0] 注意:移动的意义是灵活的,目的是便于搜索.如: 注意:移动的意义是灵活的,目的是便于搜索.如: 排序问题中一次换位可称为一次移动,还可以定义为 排序问题中一次换位可称为一次移动,还可以定义为 选一个切点,两部分作交叉运算. ( ) [ ] 0,1,1,0,1,0,0 s x x ud = + = 选一个切点,两部分作交叉运算.

177 177 练练习习??定义邻域移动为位值加 定义邻域移动为位值加1 1或减 或减1, 1, ? ? 对整数编码 对整数编码[

2 2

3 5

3 ] [

2 2

3 5

3 ],以下染色体是否 ,以下染色体是否 在其邻域内: 在其邻域内: [

2 3

3 5

3 ] [

2 3

3 5

3 ], , [

2 3

2 5

3 ] [

2 3

2 5

3 ], , [

2 2

3 5

5 ] [

2 2

3 5

5 ], , [

2 2

3 4

3 ] [

2 2

3 4

3 ], , [

2 2

2 5

3 ] [

2 2

2 5

3 ], , [

2 2

3 4

4 ] [

2 2

3 4

4 ], , 是否是否否是178

178 练练习( 习(2 2) ) ? ? 定义邻域移动为两两换位 定义邻域移动为两两换位, , ? ? 对顺序编码 对顺序编码[

4 2

3 5

1 ] [

4 2

3 5

1 ],以下染色体是否 ,以下染色体是否 在其邻域内: 在其邻域内: [

4 3

2 5

1 ] [

4 3

2 5

1 ], , [

4 3

5 1

2 ] [

4 3

5 1

2 ], , [

4 3

3 5

1 ] [

4 3

3 5

1 ], , [

5 2

3 4

1 ] [

5 2

3 4

1 ], , [1

2 3

5 4 ] [1

2 3

5 4 ], , [

3 4

2 5

1 ] [

3 4

2 5

1 ], , 是否是否否是179

179 二二. . TS TS的基本原理及步骤 的基本原理及步骤( (4 4) ) 2. 2. 禁忌表的概念 禁忌表的概念 禁忌表的作用:防止搜索出现循环 禁忌表的作用:防止搜索出现循环 ① ① 记录前若干步走过的点、方向或目标值,禁 记录前若干步走过的点、方向或目标值,禁 止返回 止返回 ② ② 表是动态更新的 表是动态更新的―― ――把最新的解记入,最老 把最新的解记入,最老 的解从表中释放 的解从表中释放( (解禁 解禁) ). . ③ ③ 表的长度称为 表的长度称为Tabu Tabu- -Size Size, ,一般取 一般取5

5、 、

7 7 、 、

11 11,表长越大分散性越好. ,表长越大分散性越好.

180 180 二二. . TS TS的基本原理及步骤 的基本原理及步骤( (5 5) ) 3. 3. 邻域搜索规则 邻域搜索规则 每一步移动到不在 每一步移动到不在T T表中的邻域中的最优解,即 表中的邻域中的最优解,即若若,,

则令 则令 则本次移动到最优解 则本次移动到最优解 邻域搜索规则的作用:保证 邻域搜索规则的作用:保证TS TS的优良局部搜索 的优良局部搜索 功能 功能 ( ) k s x { } , k s x Opt s x s x S x T k x s x =

181 181 二二. . TS TS的基本原理及步骤 的基本原理及步骤( (6 6) ) 4. 4. 渴望水平函数 渴望水平函数 是一个取决于 是一个取决于 和和的值,若有 的值,若有 则则是不受 是不受T T表限制.即使 表限制.即使 ,仍可取 ,仍可取 渴望水平,一般为历史上曾经达到的最好 渴望水平,一般为历史上曾经达到的最好 目标值. 目标值. ( ) x s A , s x ( ) ( ) ( ) , C s x A s x < ( ) s x ( ) s x T ∈ ( ) x s x = ( ) x s A ,

182 182 三三. . TS TS的算法步骤 的算法步骤( (1 1) ) 1. 1. 步骤: 步骤: ① ① 选一个初始点 选一个初始点 , , ,令 ,令 , , , , 迭代指标 迭代指标 ;

;

② ② 若若停止,否则令 停止,否则令 ,若 ,若 ( (其中 其中NG NG为最大迭代数 为最大迭代数) )停止;

停止;

注: 注: 表示非正常终止,造成的原因: 表示非正常终止,造成的原因: 邻域小 邻域小, ,T T表长.正常设置为 表长.正常设置为(T (T表长度 表长度< ( ) φ = ? T x S

183 183 三三.TS .TS的算法步骤( 的算法步骤(2 2) ) ③ ③ 若若,令 ,令 更新 更新 ( ( 当前最优目标函数值 当前最优目标函数值) ) ;

;

注:步骤 注:步骤③ ③的作用邻域选优 的作用邻域选优 ④ ④ 若若,,

且且,令 ,令,,

((更新渴望水平 更新渴望水平) ) ;

;

注:步骤 注:步骤④ ④的作用破禁检查,修订渴望水平 的作用破禁检查,修订渴望水平 { } , k s x Opt s x s x S x T k x s x = ( ) C x ( ) C x ( ) ( ) ( ) , L C s x A s x < ( ) ( ) ( ) , L A s x C s x = ( ) L s x T ∈ ( ) L x s x = ( ) ( ) ( ) L C s x C x <

184 184 三三.TS .TS的算法步骤( 的算法步骤(3 3) ) ⑤ ⑤ 若若,令 ,令,,

注:步骤 注:步骤⑤ ⑤的作用选优并 的作用选优并记录历史最好点 记录历史最好点 ⑥ ⑥ 更新 更新T T表,转步 表,转步2 2( ( 存入 存入T T表中的第一个位 表中的第一个位 置置))()()? 停止 停止 Y Y N N 若若令令 { } T x S x s x s Opt x S k ? ∈ = , ( ) x S X k = ( ) ( ) ( ) x s A x S C L , < ( ) T x ∈ L S ( ) x S x L = 若若()()?0 >0的数减 的数减1 1;

;

II. II. 对数组上半部分,给新发生的移动所对应 对数组上半部分,给新发生的移动所对应 的数组元加上 的数组元加上Tabu Tabu- -Size;

Size;

III. III. T T表的下半部分,用来记频数,每次 表的下半部分,用来记频数,每次(i,j) (i,j)交交换换(i