大连海事大学现代优化技术大连海事大学现代优化技术第第7讲：传统启发式算法之改讲：传统启发式算法之改进形态进形态传统启发式算法之改进形传统启发式算法之改进形构筑法的改进形构筑法的改进形 （贪婪算法的改进形）（贪婪算法的改进形）改善法的改进形改善法的改进形 （局部探索法的改进形）（局部探索法的改进形）传统启发式算法之改进形传统启发式算法之改进形改善法（局部探索法）的改进形改善法（局部探索法）的改进形改善法的探索路径改善法的探索路径改善法的局限性改善法的局限性改善法的改进形改善法的改进形传统启发式算法之改进形传统启发式算法之改进形局局部最优部最优解解近近邻与局部最优解邻与局部最优解（概念（概念図図）近近邻邻 N(x)N(x)可可可可行行行行解解解解传统启发式算法之改进形传统启发式算法之改进形邻域解邻域解一一台机器的交货期最小迟延排序问题台机器的交货期最小迟延排序问题工件的工件的集合集合 1,2,3,41,2,3,4工件工件 i 1 2 3 4加工时间加工时间 pi 1 2 3 4交货期交货期 di 5 9 6 4可可行行解解的的集合集合 从从1,2,3,41,2,3,4中中構構成成4!4!种可能的排序种可能的排序传统启发式算法之改进形传统启发式算法之改进形目目标函数：标函数：一一台机器的交货期最小迟延排序问题台机器的交货期最小迟延排序问题目目标函数：交货期迟延的标函数：交货期迟延的合合計計（最小化）（最小化）可可行行解（解（順順列）列）12341234 所对应的目标函数所对应的目标函数J1J1J2J2J3J3J4J4J1J1J1J1交货期交货期交货期交货期J2J2J2J2交货期交货期交货期交货期J3J3J3J3交货期交货期交货期交货期J4J4J4J4交货期交货期交货期交货期目标函数值目标函数值目标函数值目标函数值= = = =6 6 6 6=6传统启发式算法之改进形传统启发式算法之改进形邻域解邻域解一一台机器的交货期最小迟延排序问题台机器的交货期最小迟延排序问题近近邻邻两个相邻工件两个相邻工件交交換換后得到的排序后得到的排序可可行行解解1 2 3 4 1 2 3 4 的近邻的近邻1 2 1 2 4 34 31 1 3 23 2 4 42 12 1 3 4 3 4传统启发式算法之改进形传统启发式算法之改进形邻域解图：邻域解图：一一台机器的交货期最小迟延排序问题台机器的交货期最小迟延排序问题 123434124343 点点与与解解一一对应一一对应667754357710878668554610目目标函数值标函数值2134213413241324传统启发式算法之改进形传统启发式算法之改进形局部探索法的局部探索法的探索探索路径路径邻域解图的邻域解图的邻域解图的邻域解图的枝枝枝枝(x,y):f(x)f(y)(x,y):f(x)f(y)传统启发式算法之改进形传统启发式算法之改进形局部探索法的局限性局部探索法的局限性目目目目标函数标函数标函数标函数难以跳离局部最优解难以跳离局部最优解难以跳离局部最优解难以跳离局部最优解3 34 45 56 67 78 89 91010传统启发式算法之改进形传统启发式算法之改进形 局部最优解的局部最优解的脱出脱出局局部部探索法探索法的探索的探索 在在局局部优部优解解处处停止停止 有必要从有必要从局局部最优解处部最优解处脱出脱出改变改变初期解，初期解，再次应用局部探索法再次应用局部探索法(multiplestartlocalsearch，iteratedlocalsearch)可变近邻局部探索法可变近邻局部探索法(variableneighborhoodlocalsearch)随机局部探索法随机局部探索法(接受恶化解接受恶化解)（stochasticlocalsearch）诱导局部探索法诱导局部探索法(guidedlocalsearch)传统启发式算法之改进形传统启发式算法之改进形LocalSearch的改进形的改进形1MultipleStartLocalSearchiteratedlocalsearch传统启发式算法之改进形传统启发式算法之改进形LocalSearch的改进形的改进形1：IteratedIteratedlocallocalSearchSearch( (迭代局部迭代局部迭代局部迭代局部探索法探索法探索法探索法) )传统启发式算法之改进形传统启发式算法之改进形LocalSearch的改进形的改进形1 1IteratedlocalsearchIteratedlocalsearch( ( ( (迭代局部探索法迭代局部探索法迭代局部探索法迭代局部探索法) ) ) )的特点的特点的特点的特点 内循环总是返回一个局部最优解；内循环总是返回一个局部最优解；内循环总是返回一个局部最优解；内循环总是返回一个局部最优解； 外循环通过从一个新的位置开始另一次新的探索，来外循环通过从一个新的位置开始另一次新的探索，来外循环通过从一个新的位置开始另一次新的探索，来外循环通过从一个新的位置开始另一次新的探索，来试图跳离前一个局部最优解；试图跳离前一个局部最优解；试图跳离前一个局部最优解；试图跳离前一个局部最优解； 总共尝试总共尝试总共尝试总共尝试MAXMAXMAXMAX次（终止条件）次（终止条件）次（终止条件）次（终止条件）。传统启发式算法之改进形传统启发式算法之改进形Local SearchLocal Search的改进形的改进形2 2可变近邻法可变近邻法集中化集中化扩展的近邻扩展的近邻扩展的近邻扩展的近邻多多样样化化传统启发式算法之改进形传统启发式算法之改进形LocalSearch的改进形的改进形2从局部最优解处，渐渐扩大近邻的探索范围，以从现行从局部最优解处，渐渐扩大近邻的探索范围，以从现行局部最优解处脱出。局部最优解处脱出。可变近邻局部探索法可变近邻局部探索法Variable neighborhood local search即：即：满足：满足：传统启发式算法之改进形传统启发式算法之改进形LocalSearch的改进形的改进形2Variable neighborhood local search algorithmVariable neighborhood local search algorithm传统启发式算法之改进形传统启发式算法之改进形LocalSearch的改进形的改进形3( ( ( (概率接受恶化解概率接受恶化解概率接受恶化解概率接受恶化解) ) ) )改善解改善解概率接受概率接受概率接受概率接受恶化解恶化解恶化解恶化解传统启发式算法之改进形传统启发式算法之改进形LocalSearch的改进形的改进形3StochasticlocalsearchStochasticlocalsearch随机局部探索法随机局部探索法随机局部探索法随机局部探索法传统启发式算法之改进形传统启发式算法之改进形LocalSearch的改进形的改进形3StochasticlocalsearchStochasticlocalsearch随机局部探索法的特点随机局部探索法的特点随机局部探索法的特点随机局部探索法的特点差差差差传统启发式算法之改进形传统启发式算法之改进形关于接受概率函数关于接受概率函数StochasticlocalsearchStochasticlocalsearch随机局部探索法随机局部探索法随机局部探索法随机局部探索法传统启发式算法之改进形传统启发式算法之改进形关于接受概率关于接受概率p p 与温度与温度T T的关系的关系StochasticlocalsearchStochasticlocalsearch随机局部探索法随机局部探索法随机局部探索法随机局部探索法传统启发式算法之改进形传统启发式算法之改进形关关于于接接受受概概率率与与新新点点评评价价值值的的关关系系StochasticlocalsearchStochasticlocalsearch随机局部探索法随机局部探索法随机局部探索法随机局部探索法传统启发式算法之改进形传统启发式算法之改进形LocalSearch的改进形的改进形3问题：问题： 上述上述随机局部探索法的接受概率是针对目标函随机局部探索法的接受概率是针对目标函随机局部探索法的接受概率是针对目标函随机局部探索法的接受概率是针对目标函数为求最大值的场合，如为求最小值的场合，数为求最大值的场合，如为求最小值的场合，数为求最大值的场合，如为求最小值的场合，数为求最大值的场合，如为求最小值的场合，如何设计其接受概率？并写出相应的算法。如何设计其接受概率？并写出相应的算法。如何设计其接受概率？并写出相应的算法。如何设计其接受概率？并写出相应的算法。StochasticlocalsearchStochasticlocalsearch随机局部探索法随机局部探索法随机局部探索法随机局部探索法传统启发式算法之改进形传统启发式算法之改进形LocalSearch的改进形的改进形4诱导局部探索法诱导局部探索法 GuidedLocalSearch(GLS)传统启发式算法之改进形传统启发式算法之改进形LocalSearch的改进形的改进形4诱导局部探索法诱导局部探索法 GuidedLocalSearch(GLS)传统启发式算法之改进形传统启发式算法之改进形LocalSearch的改进形的改进形4诱导局部探索法诱导局部探索法 GuidedLocalSearch(GLS)传统启发式算法之改进形传统启发式算法之改进形LocalSearch的改进形的改进形4诱导局部探索法诱导局部探索法 GuidedLocalSearch(GLS)Penalty (long term memory) p: Penalty (long term memory) p: U RU RModifiedCostFunctionf(x)=u xc(u)+u xp(u)GLS（）1 p(u) := 0 ( u U) 2 while while STOP TRUE do do3 x := LS (x, g)4 u* := arg max ux c(u)/(p(u)+1)5 p(u*) :=p(u*)+1 传统启发式算法之改进形传统启发式算法之改进形诱导局部探索法诱导局部探索法 GuidedLocalSearch(GLS传统启发式算法之改进形传统启发式算法之改进形TSP的诱导局部探索法的诱导局部探索法GuidedLocalSearchforTSP继续探索继续探索Q & A结束语结束语谢谢大家聆听！谢谢大家聆听！38