02禁忌搜索.ppt

? Taboo Search , TS ?局部搜索 Local Search , LS ? TS 是 LS 的推广?在搜索过程中,通过禁忌表禁止搜索前几次已经搜索过的内容,从而有望跳出“局部陷阱”获得最优解 Glover, F. (1986) “ Future Paths for Integer Programming and Links to Artificial Intelligence, ” Computer and Operations Research , vol. 13, no. 5, pp. 533-549. 局部搜索?组合优化问题标准形式: min f(x ) . g(x) ≥0, x∈D 局部搜索?从某个初始解 x 0开始,寻找其邻域中更优的解;如找到比 x 0更好的解 x 1,继续寻找 x 1的邻域中更优的解……直到找不到更优的解为止?初始解:随机产生或凭经验产生?局部搜索范围:整个邻域或邻域的一部分, 或随机选取(邻域中)的一个点?示例: 4城市 TSP 问题 P53 LS 的优缺点又称为爬山法或下山法?优点:简单、快速?缺点:优化能力低–严重依赖搜索起点和邻域结构–易陷入局部陷阱,无法保证获得全局最优解禁忌搜索?使用对以往搜索的记忆,禁止新的搜索重复以前的搜索?示例 P54 Tabu Search Framework Stop 应用启发式规则为追求多样化( diversification )或强化( intensification ) 更改选取规则 diversification or Generate initial solution and initialize memory structures Construct modified neighborhood Select best neighbor Execute specialized procedures 禁忌规则限制候选列表藐视规则豁免精英解局部搜索… Update memory Structures ( Tabu memory ) Update best solution More iterations? 使用短期或长期策略 Yes No短期和长期禁忌策略?短期记忆策略–目的:避免搜索过程的返回和循环–基于解移动的特征和最近的移动?长期策略– Frequency-based memory :考查移动出现的频率,确定对其的禁忌策略– Strategic oscillation :有意识的调整搜索方向以接近搜索边界– Path relinking :针对已形成的搜索路径,规划出更短的路径并沿此路径继续 Tabu Search 参数?局部搜索设计?邻域结构设计?藐视准则?被禁忌对象?禁忌对象的加入方式?禁忌长度?终止条件需要解决的问题?禁忌表的设计–滚动式–矩阵式?禁忌对象–解–目标值的变化–解向量分量的变化?禁忌长度–定长或变长。–凭经验或测试确定和邻域构造密切相关