第4章——禁忌搜索.ppt

《第4章——禁忌搜索.ppt》由会员分享，可在线阅读，更多相关《第4章——禁忌搜索.ppt（46页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、智能优化方法智能优化方法AI-Based Optimization MethodsBy Professor By Professor DingweiDingwei Wang WangNortheastern UniversityNortheastern UniversityChina 2004China 20041 1第四章第四章禁忌搜索禁忌搜索2 2第四章第四章 禁忌搜索（禁忌搜索（Tabu Search）一一.导言导言二二.TS.TS的基本原理及步骤的基本原理及步骤三三.TS.TS的算法步骤的算法步骤四四.TS.TS可以克服局优的分析可以克服局优的分析五五.TS.TS举例举例六六.TS.T

2、S的中、长期表的使用的中、长期表的使用七七.TS.TS表的应用举例表的应用举例八八.学习学习TSTS的几点体会的几点体会3 31.1.TSTS的提出的提出19771977年年F.GloverF.Glover提出提出TSTS ，9090年代初得到广年代初得到广泛重视泛重视一一.导言（导言（1 1）4 42.2.TSTS的基本思想的基本思想避免在搜索避免在搜索过程中的循程中的循环只只进不退的原不退的原则用用TabuTabu表表锁住退路住退路不以局部最不以局部最优作作为停止准停止准则邻域域选优的的规则模模拟了人了人类的的记忆功能功能找找过的地方都的地方都记下来，不再找第二次下来，不再找第二次一一.导

3、言（导言（2 2）5 53.TS的要素构成的要素构成禁忌表禁忌表(Tabu List)渴望水平函数渴望水平函数(Aspiration Level Function)移动规则移动规则邻域选优邻域选优选优规则选优规则保持历史上的最优解保持历史上的最优解停止准则停止准则与与GA相似相似一一.导言（导言（3 3）6 61.问题的描述及邻域的概念问题的描述及邻域的概念TS仅用于离散优化，排斥实优化仅用于离散优化，排斥实优化二二.TSTS的基本原理及步骤的基本原理及步骤（1 1）7 7 二二.TSTS的基本原理及步骤的基本原理及步骤（2 2）8 8邻域举例：邻域举例：X=0,1,0,0,1,0,0u=1,

4、d=0,0,1,0,0,0,0注意：移动的意义是灵活的，目的是便于搜索。如：注意：移动的意义是灵活的，目的是便于搜索。如：注意：移动的意义是灵活的，目的是便于搜索。如：注意：移动的意义是灵活的，目的是便于搜索。如：排序问题中一次换位可称为一次移动，还可以定义为排序问题中一次换位可称为一次移动，还可以定义为排序问题中一次换位可称为一次移动，还可以定义为排序问题中一次换位可称为一次移动，还可以定义为选一个切点，两部分作交叉运算。选一个切点，两部分作交叉运算。选一个切点，两部分作交叉运算。选一个切点，两部分作交叉运算。二二.TSTS的基本原理及步骤的基本原理及步骤（3 3）9 92.2.禁忌表的概念

5、禁忌表的概念禁忌表的作用：防止搜索出现循环禁忌表的作用：防止搜索出现循环记录前若干步走过的点、方向或目标值，禁记录前若干步走过的点、方向或目标值，禁止返回止返回表是动态更新的表是动态更新的把最新的解记入，最老把最新的解记入，最老的解从表中释放的解从表中释放(解禁解禁)。表的长度称为表的长度称为TabuTabu-Size-Size，一般取，一般取5 5、7 7、1111，表长越大分散性越好。，表长越大分散性越好。二二.TSTS的基本原理及步骤的基本原理及步骤（4 4）10103.邻域搜索规则邻域搜索规则每一步移动到不在每一步移动到不在T表中的邻域中的最优解，即表中的邻域中的最优解，即若若 ，则令

6、，则令则本次移动到最优解则本次移动到最优解邻域搜索规则的作用：保证邻域搜索规则的作用：保证TS的优良局部搜索的优良局部搜索功能功能二二.TSTS的基本原理及步骤的基本原理及步骤（5 5）11114.渴望水平函数渴望水平函数是一个取决于是一个取决于 和和 的值，若有的值，若有则则 是不受是不受T表限制。即使表限制。即使 ，仍可取，仍可取 渴望水平，一般为历史上曾经达到的最好渴望水平，一般为历史上曾经达到的最好目标值。目标值。二二.TSTS的基本原理及步骤的基本原理及步骤（6 6）12121.1.步骤：步骤：选一个初始点选一个初始点 ，令，令 ，迭代指标迭代指标 ；若若停止，否则令停止，否则令，若

7、，若(其中其中NGNG为最大迭代数为最大迭代数)停止；停止；注：注：表示非正常终止，造成的原因：表示非正常终止，造成的原因：邻域小，邻域小，T T表长。正常设置为表长。正常设置为(T(T表长度表长度 0的数减的数减1；II.对数数组上半部分，上半部分，给新新发生的移生的移动所所对应的数的数组元加上元加上Tabu-Size;III.T表的下半部分，用来记频数，每次表的下半部分，用来记频数，每次(i,j)交换交换(ij)，对应的，对应的(j,i)+1)来记忆频数。来记忆频数。六六.TS.TS的中、长期表的使用的中、长期表的使用（4 4）3030频数表的优点：同一数组作为频数表的优点：同一数组作为T

8、表和频数表共同表和频数表共同使用，方便操作又节省了时间。使用，方便操作又节省了时间。六六.TS.TS的中、长期表的使用的中、长期表的使用（5 5）3131频数表：频数表：Tabu-Size=7六六.TS.TS的中、长期表的使用的中、长期表的使用（6 6）T T表表表表1 11 1，2 22 21 1，5 53 332323.长期表的使用长期表的使用多阶段多阶段TS算法算法长期表的作用长期表的作用长期表用来记录每个阶段的初始解，在下一长期表用来记录每个阶段的初始解，在下一阶段产生初始解时，使之尽可能与已有的初始阶段产生初始解时，使之尽可能与已有的初始解有较大的距离。解有较大的距离。六六.TS.T

9、S的中、长期表的使用的中、长期表的使用（7 7）3333图示图示六六.TS.TS的中、长期表的使用的中、长期表的使用（8 8）3434函数表达式函数表达式函数表达式函数表达式长期表的长期表的长期表的长期表的TSTSTSTS有很好的性能。有很好的性能。有很好的性能。有很好的性能。六六.TS.TS的中、长期表的使用的中、长期表的使用（9 9）35351.问题的来源问题的来源1994年年IcmellIcmell发表的论文，发表的论文，C&OR V21,No.8C&OR V21,No.8Computer and Operations ResearchComputer and Operations Re

10、search问题：问题：带有折扣资金流的约束网络计划问题带有折扣资金流的约束网络计划问题(资源受限资源受限)2.例题例题见下页见下页七.TS表的应用举例（1 1）3636n n个工作组成的项目个工作组成的项目个工作组成的项目个工作组成的项目,求极小化折扣资金流的计划求极小化折扣资金流的计划求极小化折扣资金流的计划求极小化折扣资金流的计划七.TS表的应用举例（2 2）3737H=(1,3),(1,4),(2,5),(2,6),(3,7),(5,7),(4,8),(6,8)解：解：变量定义：变量定义：七.TS表的应用举例（3 3）S SE E1 12 26 68 87 73 34 45 53838

11、问题模型：问题模型：问题模型：问题模型：式式式式 式式式式 式式式式 式式式式 式式式式脱期罚项脱期罚项脱期罚项脱期罚项n n是最后完成的工作是最后完成的工作是最后完成的工作是最后完成的工作脱期惩罚因子脱期惩罚因子脱期惩罚因子脱期惩罚因子3939数学模型的解释：数学模型的解释：式式折扣资金折扣资金；式式每个工作只能完成每个工作只能完成1次次;式式资源约束；资源约束；式式工作工作i没做完不允许做工作没做完不允许做工作j仔细思考，以上数学表达式的下标设计是非常仔细思考，以上数学表达式的下标设计是非常精妙的尤其是精妙的尤其是式资源约束。式资源约束。七.TS表的应用举例（5 5）4040将以上模型简化

12、将以上模型简化七.TS表的应用举例（6 6）4141该式表示该式表示该式表示该式表示i i在在在在j j之前之前之前之前这一项表示条件取和这一项表示条件取和这一项表示条件取和这一项表示条件取和注：对于条件取和、注：对于条件取和、注：对于条件取和、注：对于条件取和、，常规的优化方法不，常规的优化方法不，常规的优化方法不，常规的优化方法不能计算，但可用能计算，但可用能计算，但可用能计算，但可用TSTS求解求解求解求解 。4242编码方式：自然数编码编码方式：自然数编码状态：状态：邻域定义：邻域定义：邻域大小：邻域大小：2n七.TS表的应用举例（8 8）4343邻域搜索规则：邻域搜索规则：中有可行解

13、时，取可行解中目标值最小中有可行解时，取可行解中目标值最小的邻域解；的邻域解；中无可行解时，取约束违反量最小的邻中无可行解时，取约束违反量最小的邻域解域解七.TS表的应用举例（9 9）44441.TS的记忆功能的记忆功能短、中、长期表要灵活使短、中、长期表要灵活使用用2.TS相对于相对于GA,SA是更快的算法，局域搜索是更快的算法，局域搜索能力强，但全局搜索能力较弱；能力强，但全局搜索能力较弱；3.改善改善TS的全局搜索能力，提高的全局搜索能力，提高TS的分散性的分散性的方法的方法用长期表用长期表八.学习TS的几点体会（1 1）4545加大加大TabuTabu Size Size加大对频数的惩罚，即增大加大对频数的惩罚，即增大4.TS仍是一种启发式，不能保证最优性仍是一种启发式，不能保证最优性5.TS的理论工作较少的理论工作较少八.学习TS的几点体会（2 2）4646