基于LocalSearch的算法赏析

前言：很久没有写博文了，两个字——“穷忙”，这一段时间里收到了很多老师、学生和业界人员的问题，有些回答的稍显草率，请谅解，其中的一些问题（比如QCQP中的semidefinite的相关问题及讨论）很想写写，但一想到写这些东西需要认真捋清思路、小心措辞、辅助作图等，又想到自己research进展跟狗屎一样，就实在没有心情写了。其实，青年教师的科研压力不比在读博士生小，老师们应该都能理解，所以请学生们和业界人员原谅我这一段时间问题回答上的草率。今天选择LocalSearch（LS）这个话题，一来是最近看到很多Papers在使用这些方法，二来是看到最近优化软件LocalSolver(官网，中国代理商)火爆的不行。LocalSolver是基于localsearch方法（而非BranchandCut方法和ConstraintProgramming方法）求解MathematicalProgramming模型的，所以非线性算子（floor,ceil,log,exp,pow,cos,sin,tan）就完全不在话下了，当您的model有大量非线性和非凸性的时候，您就别再一边又一边给杜老师发Email了（杜老师，我用Gurobi和CPLEX怎么都不行？），也别苦逼地去尝试IBMILOGCPOpitimizer了，因为CP虽然也能处理这些，但毕竟设计的初衷不是为了求MathematicalModel的，所以这时候大胆尝试一下LocalSolver吧。我以后再也不会说：你的Model非线性和非凸性都很强，有点没治~；我会说：PlsTryLocalSolver（对学术界免费开放）。LocalSearch详细的基本知识我就不说了，说实在的，我掌握的也不是很系统，不过LocalSolver团队提供了供课堂教学用的资料，让老师教学生系统学习LS技术（我在内蒙古大学还没有资格给研究生上课，所以暂时不会把LS技术系统地带入课堂,这一点也令我有些沮丧)，有需要教学的老师可向LocalSolver开发团队协商索要教学资料。下面我简单地把跟LocalSearch紧密相关的一些算法（这里，我无意全面地介绍跟LS相关的各种算法）介绍给大家，让大家对LS技术有个相对直观和略显高级的理解，也能大致洞察清楚优化软件LocalSolver后面的东东，主要包括：VariableNeighborhoodDescent(VND),IteratedLocalSearch(ILS)，VariableNeighborhoodSearch(VNS)，VariableNeighborhoodDecompostionSearch(VNDS)，LargeNeighborhoodSearch(LNS)等。算法详细的细节我不再披露，请大家google里找相应的Papers阅读，我只简单给出算法的主要伪代码（主要的来源是ThomasStutzle在2003年一个暑期学校上的讲义即Blum在AppliedSoftComputing上写的一篇综述论文），并着重分析各算法的核心思想以及各算法的区别。-------------------------------------博主2013年8月31日注：开始--------------------------LocalSearch也是一种顺序化的搜索方法，搜索路径形成一个轨迹，针对当前点（解），从其邻域中试图找到一个更好的解来代替当前解（找不到时当然要停止搜索）。问题一：基本的LocalSearch常常能到达局部最优，若算法不再配备克服局部极优的机制，常常称这种LocalSearch为HillClimbing（爬山法）；若配备了克服局部极优的机制，就形成更为复杂的算法，如利用iteration机制的IteratedLocalSearch算法，利用memory(记忆)机制的reactivesearchoptimization算法，利用memory-lessstochasticmodification机制的SimulatedAnnealing算法。我们这里提到的LocalSearch主要指的是HillClimbing。问题二：若定义邻居（邻域）的方法是最多不超过k个SolutionComponent发生改变（其余n-k个component不变），这种LocalSearch成为k-OPT。例子：求解TSP的2-OPT即是一种LocalSearch。在这一算法中，常常把定义邻居的交换两条弧的操作成为2-OPTSwap,可用函数2OptSwap(route,i,k)。如对于解A-B-C-D-E-F-G-H-A，指定i=3,k=6，即针对弧C-D和G-H进行交换，交换为C-G和D-H,即(A-B-C)和（H-A）片段不变（也即H-A-B-C不变），片段（D-E-F-G）元素也不变，只是两个片段原来靠弧C-D和G-H连接，现在靠弧C-G和D-H连接（两个片段连接的首尾交换了一下），考虑到这里是有方向的，故将片段（D-E-F-G）在元素连接方式不变的情况下方向变一下，即为（G-F-E-D），这就构造除了新的邻居A-B-C-G-F-E-D-H-A。所以每次给定一个i、k的具体值，2OptSwap(route,i,k)就会给出一个具体的邻居。这就有了下面的问题三。问题三：对于当前解S，有很多邻居（对于上面的2-OPT，每个不同的i,k组合都将是一个邻居），也即它的邻域中有很多解，如何搜索它的邻域？也即，如何在邻域中找到更好的解？一种简单粗暴的思路是“系统化的搜索”，利用两次for循环来枚举不同的i,k组合，当在某个i_some,k_some找到更好解时，替代当前解S，否则继续枚举i,k,见下面的代码；另一种策略常常用到，即“随机化的搜索”方法，每次随机地选取S的一个邻居（即i,k），找到更好的解时替代当前解，否则继续随机选取S的一个邻居，当在给定随机尝试次数内找不到更好解时，算法停止。-------------------------------------博主2013年8月31日注：结束--------------------------1.VariableNeighborhoodDescent(VND)每次在一个邻域N_k中找不到一个更好的解时，就仍然从当前解s出发，换一个领域结构（常常是在一个更大的领域中）搜索，看是否能找到更好的解；当找到一个更好的解s’时，从这一新的解出发，重新返回第一个领域结构开始搜索。这里变换邻域结构时的初衷是当前邻域结构找不到更好的解，而变换（常常为扩大）邻域结构能带来找到更优解的希望，但变换邻域结构时，要保持搜索的初始解（当前解）不变。但值得注意的是：对不同领域结构尝试搜索的算法可能不一样。2.IteratedLocalSearch(ILS)LocalSearch是在一个领域结构（通常较小，如TSP问题的2-OPT，3-OPT邻域，并行机调度问题的insert邻域）中从一个最优解出发试图找到最好的解，localsearch的搜索往往是从一个点到另一个点的顺序化搜索，一点点改进（模拟退火在每个温度上的搜索不也是一种localsearch么？只是加入了以一定概率接受差解的机制）。因此localsearch的出发点（初始解）就很重要，对出发点的搜索，往往是在一个更大的领域结构内（如TSP问题的4-OPT邻域，并行机调度的swap邻域）随机地选取一点，这种在更大领域内随机选一点的操作称为Perturbation。值得注意的是：SimulatedAnnealing(SA),TabuSearch(TS)等也是为了增强localsearch而设计的Metaheuristics，它们的整个搜索过程都是一条trajectory，而ILS的搜索过程中由于用了Perturbation来跳出局部最优，所以其搜索过程不再是一条trajectory，这也是ILS与SA、TS的主要不同之处。博主2013年10月2日注：如果这里Perturbation跟s^*没有关系，是纯随机地产生一个解，那么就不是IteratedLocalSearch了，就变成了Multi-startLocalSearch了。3.VariableNeighborhoodSearch(VNS)不考虑对解的接受规则（因为AcceptenceCriterion本身可以灵活选用），VNS与ILS的区别仅仅在于：在对localsearch初始点搜索(即perturbation)时，VNS并不是仅限于一种领域结构，而是按一定顺序（size从大到小还是从小到大？可有多种不同版本）尝试预先设计好的多个领域结构——从一个领域结构N_k中的一点出发，localsearch找不到更好解就从第N_(k+1)个邻域结构的一点出发；一旦找到更好解，下次perturbation时就仍然从第一个邻域结构N_1开始尝试(注意：localsearch操作仅仅在N_1领域结构中展开)。VNS与VND的差别在于变换领域的初衷：VND变换领域时localsearch的出发点不变，即不是为了Perturbation,只是为了改变（扩大）邻域结构能找到更好的解；而VNS变换领域结构目的是perturbation，从几何上看，是从当前搜索的局部区域中跳出来让localsearch在另一个局部区域中展开。4.VariableNeighborhoodDecompostionSearch(VNDS)VNS的一个常用变种是VNDS（变邻域分解搜索），VNDS与VNS的唯一不同在于：localsearch是针对一个缩小后的问题（子问题）进行搜索的。每次perturbation得到一个初始解后，不是马上进行localsearch，而通过“保留这个初始解的k个解元素不变，另外n-k个解元素是可变的”定义一个子问题，让localsearch搜索这n-k个自由的解元素（从上图看出，实际是一个缩小的问题）。5.LargeNeighborhoodSearch(LNS)那有的小同学又问问题了：杜老师，LargeNeighborhoodSearch(LNS)又是什么？答：请看下面LNS的Procedure，观察一下差异。看出跟ILS的差异了么？（1）ILS中的LocalSearch往往邻域较小，所以采用一般的LocalSearch即可，而LNS的邻域较大，往往需要其它搜索技术，如ConstraintProgramming,MIP-basedMethod,DynamicProgramming；（2）ILS中从一个搜索空间跳到另一个搜索空间是靠Perturbation完成的（因为在这个空间中要用localsearch,所以空间跳转时只需给一个起始点即可，是为Perturbation），而LNS的搜索空间跳转是靠对当前解随机地定义（给出）一个大邻域完成的（如，固定k个解元素不变，另外n-k个可自由），更加直接。