02禁忌搜索.ppt

2 禁忌搜索 局部搜索禁忌搜索技术问题应用案例 禁忌搜索 TabooSearch TS局部搜索LocalSearch LSTS是LS的推广在搜索过程中 通过禁忌表禁止搜索前几次已经搜索过的内容 从而有望跳出 局部陷阱 获得最优解 Glover F 1986 FuturePathsforIntegerProgrammingandLinkstoArtificialIntelligence ComputerandOperationsResearch vol 13 no 5 pp 533 549 2 1局部搜索 组合优化问题标准形式 minf x s t g x 0 x D 2 1局部搜索 从某个初始解x0开始 寻找其邻域中更优的解 如找到比x0更好的解x1 继续寻找x1的邻域中更优的解 直到找不到更优的解为止初始解 随机产生或凭经验产生局部搜索范围 整个邻域或邻域的一部分 或随机选取 邻域中 的一个点示例 4城市TSP问题P53 LS的优缺点 又称为爬山法或下山法优点 简单 快速缺点 优化能力低严重依赖搜索起点和邻域结构易陷入局部陷阱 无法保证获得全局最优解 禁忌搜索 使用对以往搜索的记忆 禁止新的搜索重复以前的搜索示例P54 TabuSearchFramework Stop 应用启发式规则 为追求多样化 diversification 或强化 intensification 更改选取规则diversificationor Generateinitialsolutionandinitializememorystructures Constructmodifiedneighborhood Selectbestneighbor Executespecializedprocedures 禁忌规则限制候选列表藐视规则豁免精英解 局部搜索 UpdatememoryStructures Tabumemory Updatebestsolution Moreiterations 使用短期或长期策略 Yes No 短期和长期禁忌策略 短期记忆策略目的 避免搜索过程的返回和循环基于解移动的特征和最近的移动长期策略Frequency basedmemory 考查移动出现的频率 确定对其的禁忌策略Strategicoscillation 有意识的调整搜索方向以接近搜索边界Pathrelinking 针对已形成的搜索路径 规划出更短的路径并沿此路径继续 TabuSearch参数 局部搜索设计邻域结构设计藐视准则被禁忌对象禁忌对象的加入方式禁忌长度终止条件 需要解决的问题 禁忌表的设计滚动式矩阵式禁忌对象解目标值的变化解向量分量的变化禁忌长度定长或变长 凭经验或测试确定 和邻域构造密切相关 终止准则确定步数终止 超过K次迭代频率控制 某个解或目标值的出现频率超过K目标控制 在记忆最优解的前提下 超过k步未找到更优的解下界偏离程度 目标值充分接近给定下界 应用案例2 Minimumspanningtreeproblemwithconstraints Objective Connectsallnodeswithminimumcosts 20 30 15 40 10 5 25 20 30 15 40 10 5 25 Costs Anoptimalsolutionwithoutconsideringconstraints Constraints1 LinkADcanbeincludedonlyiflinkDEalsoisincluded penalty 100 Constraints2 Atmostoneofthethreelinks AD CD andAB canbeincluded Penaltyof100ifselectedtwoofthethree 200ifallthreeareselected Example Newcost 75 iteration2 localoptimum 20 30 15 40 10 5 25 Delete Add Iteration1Cost 50 200 constraintpenalties Constraints1 LinkADcanbeincludedonlyiflinkDEalsoisincluded penalty 100 Constraints2 Atmostoneofthethreelinks AD CD andAB canbeincluded Penaltyof100ifselectedtwoofthethree 200ifallthreeareselected Example Atabumovewillbeconsideredonlyifitwouldresultinabettersolutionthanthebesttrialsolutionfoundpreviously AspirationCondition Iteration3newcost 85Escapelocaloptimum 20 30 15 40 10 5 25 Tabu Delete Add Tabulist DEIteration2Cost 75 Constraints1 LinkADcanbeincludedonlyiflinkDEalsoisincluded penalty 100 Constraints2 Atmostoneofthethreelinks AD CD andAB canbeincluded Penaltyof100ifselectedtwoofthethree 200ifallthreeareselected Add 25 Example Atabumovewillbeconsideredonlyifitwouldresultinabettersolutionthanthebesttrialsolutionfoundpreviously AspirationCondition Iteration4newcost 70Overridetabustatus 20 30 15 40 10 5 Tabu Tabu Delete Tabulist DE BEIteration3Cost 85 Constraints1 LinkADcanbeincludedonlyiflinkDEalsoisincluded penalty 100 Constraints2 Atmostoneofthethreelinks AD CD andAB canbeincluded Penaltyof100ifselectedtwoofthethree 200ifallthreeareselected Example OptimalSolutionCost 70Additionaliterationsonlyfindinferiorsolutions 20 30 15 40 10 5 25 应用案例3车间作业调度 n个工件在m台机器上加工 每个工件在一台机器上加工最多1次或0次 一台机器一次只能加工一个工件 且加工过程不允许打断 如何安排各工件在各机器上的加工顺序使得总加工时间最短 工序矩阵 各工件的工序对应机器 工件1 123工件2 321工件3 231 工时矩阵 各工件的工序所需加工时间 工件1 231工件2 462工件3 372 调度方案示例 各机器上工件的排序 机器1 123机器2 123机器3 223 应用案例3车间作业调度 解的表达方式 多种直接表达基于工件的编码邻域 找到关键路径中的关键块 掉换块内两工序的位置禁忌对象 已进行过的掉换 应用案例3车间作业调度 ProsandCons Pros 允许接受劣解以跳出局部最优离散问题或连续问题皆可应用对大规模或高难度的问题 调度问题 二次指派問題 车辆路由问题等 禁忌搜索经常能获得与其他算法相比同样好或更好的解 1 1 Glover F Kelly J P andL