大连海事大学《现代优化技术》第7讲：传统启发式算法之改进形态.ppt

现代优化技术 第7讲：传统启发式算法之改进形 传统启发式算法之改进形 构筑法的改进形 （贪婪算法的改进形） 改善法的改进形 （局部探索法的改进形） 传统启发式算法之改进形 构筑法（贪婪算法）的局限性 构筑法（贪婪算法）在任何给定的时点都采 取当时的最佳移动，但最终的整体结果却不 一定是最佳的。其问题在于现时点局部是最 好的，却不一定是后面所需要的。如果在探 索的途中有一个评估函数，能提供现在及未 来的一些信息，就可以改善、避免短期的贪 婪行为。 改进的贪婪法 传统启发式算法之改进形 最佳优先（best-first）探索：A*算法 深度优先策略(deep-first): 以一种任意的模 式往尽可能深的空间探索。 广度优先策略(wide-first): 探索完某一层次 中所有节点后才进入下一层次。 例：TSP的探索树 两种传统的探索策略： 传统启发式算法之改进形 两种传统的探索策略：例 B R L R B B L R L B R L B L R M B R M R B B M R M B R M B B R L B L M L B B M L M B L M B M L R R L M L R R M L M R L M R M L B Z 30473047 3407348534853596 3297 3497 3407 3825 4034 3256 3297 3784 40343674 3825 3584 3297 3674 37843497 3256 3596 传统启发式算法之改进形 最佳优先（best-first）探索： 最佳优先探索使用启发性规则，在探索过程中给 每个已经构造的部分解q提供一个性能值来辅助 下一个节点的选择、引导进一步的探索。这一性 能值包括： 1）已作决策的性能值-c(q) 2）有待决策的潜在性能值-h(q) 一个部分解q的性能评价函数为： eval (q)=c(q)+h(q) 传统启发式算法之改进形 最佳优先（best-first）探索： 评估函数的确定 c(q): 已构造部分解的性能值： 易于评估，甚至可以得到精确的度量，如TSP的部分解 性能就是以得到的部分巡回路的长度。 h(q): 现有部分解的潜在性能值： 从现时点出发到达目标所需的剩余代价-难以评估 用到达目标所需剩余代价的最小估算值 h 来代替 如果 h 是有上界的 ，即 h(q)f(y) (x,y): f(x)f(y) 传统启发式算法之改进形 局部探索法的局限性 目目标函数标函数 难以跳离局部最优解难以跳离局部最优解 3 3 4 4 5 5 6 6 7 7 8 8 9 9 1010 传统启发式算法之改进形 局部最优解的脱出 局部探索法的探索 在局部优解处停止 有必要从局部最优解处脱出 改变初期解，再次应用局部探索法 (multiple start local search，iterated local search) 可变近邻局部探索法 (variable neighborhood local search) 随机局部探索法 (接受恶化解) （stochastic local search） 诱导局部探索法 (guided local search) 传统启发式算法之改进形 Local Search的改进形1 Multiple Start Local Search iterated local search 传统启发式算法之改进形 Local Search 的改进形 1： Iterated Iterated local local SearchSearch ( (迭代局部迭代局部 探索法探索法) ) 传统启发式算法之改进形 Local Search的改进形1 Iterated local search Iterated local search ( (迭代局部探索法迭代局部探索法) )的特点的特点 内循环总是返回一个局部最优解；内循环总是返回一个局部最优解； 外循环通过从一个新的位置开始另一次新的探索，来外循环通过从一个新的位置开始另一次新的探索，来 试图跳离前一个局部最优解；试图跳离前一个局部最优解； 总共尝试总共尝试MAXMAX次（终止条件）次（终止条件）。 传统启发式算法之改进形 Local Search的改进形2 可变近邻法可变近邻法 集中化 扩展的近邻扩展的近邻 多样化 传统启发式算法之改进形 Local Search的改进形2 从局部最优解处，渐渐扩大近邻的探索范围，以从现行 局部最优解处脱出。 可变近邻局部探索法 Variable neighborhood local search 即 ： 满足 ： 传统启发式算法之改进形 Local Search的改进形2 Variable neighborhood local search algorithm 传统启发式算法之改进形 Local Search的改进形3 ( (概率接受恶化解概率接受恶化解) ) 改善解 概率接受概率接受 恶化解恶化解 传统启发式算法之改进形 Local Search的改进形3 Stochastic local search Stochastic local search 随机局部探索法随机局部探索法 传统启发式算法之改进形 Local Search的改进形3 Stochastic local search Stochastic local search 随机局部探索法的特点随机局部探索法的特点 差差 传统启发式算法之改进形 关于接受概率函数 Stochastic local search Stochastic local search 随机局部探索法随机局部探索法 传统启发式算法之改进形 关于接受概率p 与温度T的关系 Stochastic local search Stochastic local search 随机局部探索法随机局部探索法 传统启发式算法之改进形 关 于 接 受 概 率 与 新 点 评 价 值 的 关 系 Stochastic local search Stochastic local search 随机局部探索法随机局部探索法 传统启发式算法之改进形 Local Search的改进形3 问题： 上述随机局部探索法的接受概率是针对目标函随机局部探索法的接受概率是针对目标函 数为求最大值的场合，如为求最小值的场合，数为求最大值的场合，如为求最小值的场合， 如何设计其接受概率？并写出相应的算法。如何设计其接受概率？并写出相应的算法。 Stochastic local search Stochastic local search 随机局部探索法随机局部探索法 传统启发式算法之改进形 Local Search的改进形4 诱导局部探索法 Guided Local Search(GLS) 传统启发式算法之改进形 Local Search的改进形4 诱导局部探索法 Guided Local Search(GLS) 传统启发式算法之改进形 Local Search的改进形4 诱导局部探索法 Guided Local Search(GLS) 传统启发式算法之改进形 Local Search的改进形4 诱导局部探索法 Guided Local Search(GLS) Penalty (long term memory) p: U R Modified Cost Function f(x)=ux c(u) + ux p(u) GLSGLS （） （） 1 p(u) := 0 ( u U) 2 while while STOP TRUE do do 3 x :=