第四讲：启发性算法-改善法

書式設定,書式設定,第 2,第 3,第 4,第 5,*,第四讲：启发性方法,改善法,Heuristics,(improvement method),改善法,(,improvement algorithms)(local search algorithms),or-opt for TSP,k-opt for TSP,cross-opt for VRP,iterated local search,guided local search,改善法示意图1,Local Search,改善法示意图2,黑夜的,登山,者(,这里是,山頂?),局部最优解,近邻（,neighborhood）,近邻：对于某一个实行可行解 ，将 进行一些适当的变形所得到的可行解集合,近,邻,N(x),近邻操作（,neighborhood operation）,近邻操作：从某一可行解 出发，为了在其近,邻 中生成一个可行解而使 适,当变形的操作,局部最优解（,locally optimal solution）：,当中不再存在改善解的 ，则,称 为关于 的局部最优解,全局最优解（,globally optimal solution）,局,部,探索法(,local search method),又称为：登,山法(,hill climbing method),；,近邻探索法（,neighborhood search method）,在,現,行,解,的,近,邻,（,非常相似的,解集合,）,中,，,如有更好的目标函数值存在,，,则用其将现行,解,更新,（,全局,）最,优,解,局,部最优解2,局,部最优,解1,目,标函,数値,近邻,探索,过程,（,全局,）最,优,解,局,部,最,优,解2,局,部最优,解1,近,邻,目,标函数,値,近邻,探索,策略,最初改善策略（,first admissible move strategy）：,对近邻 内随机探索，一旦发现(最初,的)改善解，就将现行解进行更新。,最良改善策略（,best admissible move strategy）：,在对近邻 内所有的可行解进行探索后，,选择其中最好的一个改善解，用其对现行,解进行更新。,探索空间（,search space）,与实行可能域（,feasible solution field）(1),探索空间=实行可能域,目标函数值 探索评价基准,探索空间（,search space）,与实行可能域（,feasible solution field）(2),探索空间,目标函数值(,objective function value)+,惩罚函数值(,penalty function value）,实行可能域,探索空间,实行可能域,探索评价基准,探索空间（,search space）,与实行可能域（,feasible solution field）(3),探索空间 实行可能域,目标函数值 探索评价基准,探索空间,实行可能域,近邻探索算法（,neighborhood search algorithm）,Neighborhood Search(NS),Move(x)=an appropriate element in N(x),NS（,）,1,while,STOP TRUE,do,2,x:=Move(x),Neighborhood N:F 2,F,改善算法（,improvement algorithm）,局部探索法（,local search algorithm）,any x N(x)with f(x)|ac|+|bd|,2,opt (2,）,a,b=next(a),c,d=next(c),k-opt,局部,探索法,k,条,枝,交换后所得到的,巡回,路,，如比原巡回路有改善，则在新巡回路的基础上反复进行上述操作，直到不再得到改善为止，这时所得到的巡回路为,k edge exchange optimal solution,简称,k opt,解,etc.,K,的选取,例,：,2-,opt 3-opt 4-opt .,近,邻的范围,：,狭,窄,宽阔,探索,时间,：,短時間,長時間,解的质量,：,精度低,精度高,K,的选取,，,取决于对问题,解,的精度要求,，,对,計算時間,及速度的要求,如：,Nearest neighbor=(,最优解,15程度）,Nearest neighbor+2-opt=(2.5,程度）,Nearest neighbor+2,3-opt=(0.3,程度）,Cross-opt for VRP,(,两条巡回路之间连续枝的交换,),Cross-opt for VRP(1),Cross-opt for VRP(2),Cross-opt for VRP(3),Cross-opt for VRP(4),Cross-opt for VRP(5),Cross-opt for VRP(6),Cross-opt for VRP(7),Cross-opt for VRP(8),Cross-opt for VRP(9),Cross-opt for VRP(10),