第四章 禁忌搜索.ppt

1 1智能优化方法 AI-Based Optimization Methods AI-Based Optimization Methods By Professor Dingwei Wang By Professor Dingwei Wang Northeastern University Northeastern University China 2004 China 2004 2 2第四章第四章禁忌搜禁忌搜索索 3 3第四章第四章禁忌搜索( 禁忌搜索( Tabu Search Tabu Search ) ) 一一. . .TS .TS .TS .TS .TS 的中、长期表的使用的中、 .TS 表的应用举例表的应用举例八八. .学****学****TS TS的几点体会的几点体会 4 4 1. TS的提出的提出 1977 1977 提出提出 TS TS, ,90 90年代初得到广年代初得到广泛重视泛重视一一. .导言( 导言( 1 1) )5 5 2. TS的基本思想的基本思想————避免在搜索过程中的循环避免在搜索过程中的循环①①只进不退的原则只进不退的原则————用用Tabu Tabu 表锁住退路表锁住退路②②不以局部最优作为停止准则不以局部最优作为停止准则③③邻域选优的规则模拟了人类的记忆功能邻域选优的规则模拟了人类的记忆功能————找过的地方都记下来,不再找第二次找过的地方都记下来,不再找第二次一一. .导言( 导言( 2 2) )6 6 3. 3. TS TS 的要素构成的要素构成①①禁忌表禁忌表(Tabu List) (Tabu List) ②②渴望水平函数渴望水平函数(Aspiration Level Function) (Aspiration Level Function) ③③移动规则移动规则————邻域选优邻域选优④④选优规则选优规则————保持历史上的最优解保持历史上的最优解⑤⑤停止准则停止准则————与与 GA GA 相似相似一一. .导言( 导言( 3 3) )7 7 1. TS TS 仅用于离散优化,排斥实优化仅用于离散优化,排斥实优化二二. . TS TS的基本原理及步骤的基本原理及步骤( (1 1) ) ??是离散值空间 X .. min Xxts xC?8 8 二二. . TS TS的基本原理及步骤的基本原理及步骤( (2 2) ) ?????? u d , x x ud S x s s x ud s X S x ? ?? ???邻域的概念: 的邻域移动为 s , 为单位步长, 为方向,则: 邻域 是邻域移动可达到的解的集合。 9 9 邻域举例: 邻域举例: 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] 注意:移动的意义是灵活的,目的是便于搜索。如: 注意:移动的意义是灵活的,目的是便于搜索。如: 排序问题中一次换位可称为一次移动,还可以定义为排序问题中一次换位可称为一次移动,还可以定义为选一个切点,两部分作交叉运算。选一个切点,两部分作交叉运算。二二. . TS TS的基本原理及步骤的基本原理及步骤( (3 3) ) ???? 0,1,1, 0,1, 0, 0 s x x ud ? ?? 10 10练练********定义邻域移动为位值加定义邻域移动为位值加 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 ] , , 是否是否否是