-禁忌搜索课件

1、智能优化方法AI-Based Optimization MethodsBy Professor Dingwei WangNortheastern UniversityChina 2004第1页，共46页。1第四章禁忌搜索第2页，共46页。2第四章 禁忌搜索（ Tabu Search ）一.导言二.TS的基本原理及步骤三.TS的算法步骤四.TS可以克服局优的分析五.TS举例六.TS的中、长期表的使用七.TS表的应用举例八.学习TS的几点体会第3页，共46页。3TS的提出1977年F.Glover提出TS ，90年代初得到广泛重视一.导言（1）第4页，共46页。4TS的基本思想避免在搜索过程中的循

2、环只进不退的原则用Tabu表锁住退路不以局部最优作为停止准则邻域选优的规则模拟了人类的记忆功能找过的地方都记下来，不再找第二次一.导言（2）第5页，共46页。5TS的要素构成禁忌表(Tabu List)渴望水平函数(Aspiration Level Function)移动规则邻域选优选优规则保持历史上的最优解停止准则与GA相似一.导言（3）第6页，共46页。6问题的描述及邻域的概念TS仅用于离散优化，排斥实优化二. TS的基本原理及步骤（1）第7页，共46页。7二. TS的基本原理及步骤（2）第8页，共46页。8邻域举例：X=0,1,0,0,1,0,0u=1,d=0,0,1,0,0,0,0注意

3、：移动的意义是灵活的，目的是便于搜索。如：排序问题中一次换位可称为一次移动，还可以定义为选一个切点，两部分作交叉运算。二. TS的基本原理及步骤（3）第9页，共46页。9禁忌表的概念禁忌表的作用：防止搜索出现循环记录前若干步走过的点、方向或目标值，禁止返回表是动态更新的把最新的解记入，最老的解从表中释放(解禁)。表的长度称为Tabu-Size，一般取5、 7 、11，表长越大分散性越好。二. TS的基本原理及步骤（4）第10页，共46页。10邻域搜索规则每一步移动到不在T表中的邻域中的最优解，即若 ，则令则本次移动到最优解邻域搜索规则的作用：保证TS的优良局部搜索功能二. TS的基本原理及步骤

4、（5）第11页，共46页。11渴望水平函数是一个取决于 和 的值，若有则 是不受T表限制。即使 ，仍可取 渴望水平，一般为历史上曾经达到的最好目标值。二. TS的基本原理及步骤（6）第12页，共46页。12步骤：选一个初始点 ， ，令 ， ，迭代指标 ；若停止，否则令，若(其中NG为最大迭代数)停止；注：表示非正常终止，造成的原因：邻域小，T表长。正常设置为(T表长度0的数减1；对数组上半部分，给新发生的移动所对应的数组元加上Tabu-Size;T表的下半部分，用来记频数，每次(i,j)交换(ij)，对应的(j,i)+1)来记忆频数。六.TS的中、长期表的使用（4）第30页，共46页。30频数

5、表的优点：同一数组作为T表和频数表共同使用，方便操作又节省了时间。六.TS的中、长期表的使用（5）第31页，共46页。31频数表：Tabu-Size=7六.TS的中、长期表的使用（6）T表11，221，53第32页，共46页。32长期表的使用多阶段TS算法长期表的作用长期表用来记录每个阶段的初始解，在下一阶段产生初始解时，使之尽可能与已有的初始解有较大的距离。六.TS的中、长期表的使用（7）第33页，共46页。33图示六.TS的中、长期表的使用（8）第34页，共46页。34函数表达式长期表的TS有很好的性能。六.TS的中、长期表的使用（9）第35页，共46页。35问题的来源1994年Icmel

6、l发表的论文，C&OR V21,No.8Computer and Operations Research问题：带有折扣资金流的约束网络计划问题(资源受限)例题见下页七.TS表的应用举例（1）第36页，共46页。36n个工作组成的项目,求极小化折扣资金流的计划七.TS表的应用举例（2）第37页，共46页。37H=(1,3),(1,4),(2,5),(2,6),(3,7),(5,7),(4,8),(6,8)解：变量定义：七.TS表的应用举例（3）SE12687345第38页，共46页。38问题模型： 式 式 式 式 式脱期罚项n是最后完成的工作脱期惩罚因子第39页，共46页。39数学模型的解释：式

7、折扣资金；式每个工作只能完成1次;式资源约束；式工作i没做完不允许做工作j仔细思考，以上数学表达式的下标设计是非常精妙的尤其是式资源约束。七.TS表的应用举例（5）第40页，共46页。40将以上模型简化七.TS表的应用举例（6）第41页，共46页。41该式表示i在j之前这一项表示条件取和注：对于条件取和、 ，常规的优化方法不能计算，但可用TS求解 。第42页，共46页。42编码方式：自然数编码状态：邻域定义：邻域大小：2n七.TS表的应用举例（8）第43页，共46页。43邻域搜索规则： 中有可行解时，取可行解中目标值最小的邻域解； 中无可行解时，取约束违反量最小的邻域解七.TS表的应用举例（9）第44页，共46页。44TS的记忆功能短、中、长期表要灵活使用TS相对于GA,SA是更快的算法，局域搜索能力强，但全局搜索能力较弱；改善TS的全局搜索能力，提高