第4章——禁忌搜索.ppt

1 智能优化方法AI BasedOptimizationMethods ByProfessorDingweiWangNortheasternUniversityChina2004 2 第四章禁忌搜索 3 第四章禁忌搜索 TabuSearch 一 导言二 TS的基本原理及步骤三 TS的算法步骤四 TS可以克服局优的分析五 TS举例六 TS的中 长期表的使用七 TS表的应用举例八 学习TS的几点体会 4 TS的提出1977年F Glover提出TS 90年代初得到广泛重视 一 导言 1 5 TS的基本思想 避免在搜索过程中的循环只进不退的原则 用Tabu表锁住退路不以局部最优作为停止准则邻域选优的规则模拟了人类的记忆功能 找过的地方都记下来 不再找第二次 一 导言 2 6 TS的要素构成禁忌表 TabuList 渴望水平函数 AspirationLevelFunction 移动规则 邻域选优选优规则 保持历史上的最优解停止准则 与GA相似 一 导言 3 7 问题的描述及邻域的概念TS仅用于离散优化 排斥实优化 二 TS的基本原理及步骤 1 8 二 TS的基本原理及步骤 2 9 邻域举例 X 0 1 0 0 1 0 0 u 1 d 0 0 1 0 0 0 0 注意 移动的意义是灵活的 目的是便于搜索 如 排序问题中一次换位可称为一次移动 还可以定义为选一个切点 两部分作交叉运算 二 TS的基本原理及步骤 3 10 禁忌表的概念禁忌表的作用 防止搜索出现循环记录前若干步走过的点 方向或目标值 禁止返回表是动态更新的 把最新的解记入 最老的解从表中释放 解禁 表的长度称为Tabu Size 一般取5 7 11 表长越大分散性越好 二 TS的基本原理及步骤 4 11 邻域搜索规则每一步移动到不在T表中的邻域中的最优解 即若 则令则本次移动到最优解邻域搜索规则的作用 保证TS的优良局部搜索功能 二 TS的基本原理及步骤 5 12 渴望水平函数是一个取决于和的值 若有则是不受T表限制 即使 仍可取渴望水平 一般为历史上曾经达到的最好目标值 二 TS的基本原理及步骤 6 13 步骤 选一个初始点 令 迭代指标 若停止 否则令 若 其中NG为最大迭代数 停止 注 表示非正常终止 造成的原因 邻域小 T表长 正常设置为 T表长度 邻域大小 步骤 的作用是设置循环体出口 三 TS的算法步骤 1 14 若 令更新 当前最优目标函数值 注 步骤 的作用邻域选优若 且 令 更新渴望水平 注 步骤 的作用破禁检查 修订渴望水平 三 TS的算法步骤 2 15 若 令 注 步骤 的作用选优并记录历史最好点更新T表 转步2 存入T表中的第一个位置 三 TS的算法步骤 3 16 17 从邻域搜索的方法看移向中最好的解 但不与当前解比较是中的最优点 但可能劣于 四 TS可以克服局优的分析 1 18 选优规则看始终保持历史上的最优解 不以当前解为最优从停止规则上看不以最优判据为停止规则 而是指定最大迭代步数为停止条件 这样不能保证最优性 四 TS可以克服局优的分析 2 19 问题的提出由7层不同的绝缘材料构成的一种绝缘体 应如何排列顺序 可获得最好的绝缘性能 五 TS举例 1 20 编码方式 顺序编码初始编码 2 5 7 3 4 6 1目标值 极大化目标值 邻域定义 两两交换是一个邻域移动邻域大小 TabuSize 3NG 5 五 TS举例 2 21 初始表初始编码 2 5 7 3 4 6 1结论 交换4和5 五 TS举例 3 22 迭代1编码 2 4 7 3 5 6 1 16结论 交换1和3 五 TS举例 4 23 迭代2编码 2 4 7 1 5 6 3 18结论 因交换1和3已在禁忌表中 故只能交换2和4 五 TS举例 5 若选择这项 16 渴望水平不能发生作用 24 迭代3编码 4 2 7 1 5 6 3 14 18结论 因渴望水平发挥作用 交换在破禁表中的4 5 五 TS举例 6 因 20大于渴望水平 18此时渴望水平发生作用 破禁 交换4和5 25 迭代4编码 5 2 7 1 4 6 3 20结论 交换7和1 五 TS举例 7 26 迭代5编码 5 2 1 7 4 6 3 20结论 迭代已到5次 得到最优解5 2 7 1 4 6 3和5 2 1 7 4 6 3 20 五 TS举例 8 27 引入中长期表的目的改善TS的广域搜索能力 TS的局域搜索能力很好 邻域选优快 但广域搜索能力较差 搜索能力是TS的关键 采用中长期表可改善TS的广域搜索能力 六 TS的中 长期表的使用 1 28 中期表 频数表频数表的作用频数表是用来记忆不同方向的移动次数 从而加以惩罚 比如两两交换 记录每对交换的发生次数 以提高搜索方向的多样性 六 TS的中 长期表的使用 2 29 在邻域选优公式中 令注 惩罚因子的取值一般应远小于目标值 1 目标值或1 目标值 越大分散性越好 广域搜索能力强 但会损坏邻域搜索 六 TS的中 长期表的使用 3 30 频数表的记录方法建立n n的数组 对上半部分每做一步搜索将所有 0的数减1 对数组上半部分 给新发生的移动所对应的数组元加上Tabu Size T表的下半部分 用来记频数 每次 i j 交换 i j 对应的 j i 1 来记忆频数 六 TS的中 长期表的使用 4 31 频数表的优点 同一数组作为T表和频数表共同使用 方便操作又节省了时间 六 TS的中 长期表的使用 5 32 频数表 Tabu Size 7 六 TS的中 长期表的使用 6 33 长期表的使用 多阶段TS算法长期表的作用长期表用来记录每个阶段的初始解 在下一阶段产生初始解时 使之尽可能与已有的初始解有较大的距离 六 TS的中 长期表的使用 7 34 图示 六 TS的中 长期表的使用 8 35 函数表达式长期表的TS有很好的性能 六 TS的中 长期表的使用 9 36 问题的来源1994年Icmell发表的论文 C ORV21 No 8ComputerandOperationsResearch问题 带有折扣资金流的约束网络计划问题 资源受限 例题见下页 七 TS表的应用举例 1 37 n个工作组成的项目 求极小化折扣资金流的计划 七 TS表的应用举例 2 38 H 1 3 1 4 2 5 2 6 3 7 5 7 4 8 6 8 解 变量定义 七 TS表的应用举例 3 39 问题模型 式 式 式 式 式 脱期罚项 n是最后完成的工作 脱期惩罚因子 40 数学模型的解释 式折扣资金 式每个工作只能完成1次 式资源约束 式工作i没做完不允许做工作j仔细思考 以上数学表达式的下标设计是非常精妙的尤其是 式资源约束 七 TS表的应用举例 5 41 将以上模型简化 七 TS表的应用举例 6 42 该式表示i在j之前 这一项表示条件取和 注 对于条件取和 常规的优化方法不能计算 但可用TS求解 43 编码方式 自然数编码状态 邻域定义 邻域大小 2n 七 TS表的应用举例 8 44 邻域搜索规则 中有可行解时 取可行解中目标值最小的邻域解 中无可行解时 取约束违反量最小的邻域解 七 TS表的应用举例 9 45 TS的记忆功