前言：很久没有写博文了，两个字——“穷忙”，这一段时间里收到了很多老师、学生和业界人员的问题，有些回答的稍显草率，请谅解，其中的一些问题（比如QCQP中的semidefinite的相关问题及讨论）很想写写，但一想到写这些东西需要认真捋清思路、小心措辞、辅助作图等，又想到自己research进展跟狗屎一样，就实在没有心情写了。其实，青年教师的科研压力不比在读博士生小，老师们应该都能理解，所以请学生们和业界人员原谅我这一段时间问题回答上的草率。
今天选择Local
Search（LS）这个话题，一来是最近看到很多Papers在使用这些方法，二来是看到最近优化软件LocalSolver(官网，中国代理商)火爆的不行。LocalSolver是基于local search方法（而非Branch and
Cut方法和Constraint Programming方法）求解Mathematical
Programming模型的，所以非线性算子（floor,
ceil, log, exp, pow, cos, sin,
tan）就完全不在话下了，当您的model有大量非线性和非凸性的时候，您就别再一边又一边给杜老师发Email了（杜老师，我用Gurobi和CPLEX怎么都不行？），也别苦逼地去尝试IBM
ILOG CP Opitimizer了，因为CP虽然也能处理这些，但毕竟设计的初衷不是为了求Mathematical
Model的，所以这时候大胆尝试一下LocalSolver吧。我以后再也不会说：你的Model非线性和非凸性都很强，有点没治~；我会说：Pls
Try LocalSolver（对学术界免费开放）。
Local
Search详细的基本知识我就不说了，说实在的，我掌握的也不是很系统，不过LocalSolver团队提供了供课堂教学用的资料，让老师教学生系统学习LS技术（我在内蒙古大学还没有资格给研究生上课，所以暂时不会把LS技术系统地带入课堂,这一点也令我有些沮丧)，有需要教学的老师可向LocalSolver开发团队协商索要教学资料。下面我简单地把跟Local
Search紧密相关的一些算法（这里，我无意全面地介绍跟LS相关的各种算法）介绍给大家，让大家对LS技术有个相对直观和略显高级的理解，也能大致洞察清楚优化软件LocalSolver后面的东东，主要包括：Variable
Neighborhood Descent(VND),Iterated Local Search (ILS)，Variable
Neighborhood Search (VNS)，Variable Neighborhood Decompostion Search
(VNDS)，Large Neighborhood Search
(LNS)等。算法详细的细节我不再披露，请大家google里找相应的Papers阅读，我只简单给出算法的主要伪代码（主要的来源是Thomas
Stutzle在2003年一个暑期学校上的讲义即Blum在Applied
Soft Computing上写的一篇综述论文），并着重分析各算法的核心思想以及各算法的区别。
-------------------------------------博主2013年8月31日注：开始--------------------------
Local
Search也是一种顺序化的搜索方法，搜索路径形成一个轨迹，针对当前点（解），从其邻域中试图找到一个更好的解来代替当前解（找不到时当然要停止搜索）。
问题一：基本的Local
Search常常能到达局部最优，若算法不再配备克服局部极优的机制，常常称这种Local Search为Hill
Climbing（爬山法）；若配备了克服局部极优的机制，就形成更为复杂的算法，如利用iteration机制的Iterated
Local Search算法，利用memory(记忆)机制的reactive search
optimization算法，利用memory-less
stochastic modification机制的Simulated Annealing算法。我们这里提到的Local
Search主要指的是Hill Climbing。
问题二：若定义邻居（邻域）的方法是最多不超过k个Solution
Component发生改变（其余n-k个component不变），这种Local Search成为k-OPT。例子：求解TSP的2-OPT即是一种Local
Search。在这一算法中，常常把定义邻居的交换两条弧的操作成为2-OPT
Swap,可用函数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. Variable
Neighborhood Descent(VND)
http://s9/bmiddle/50c15451tdf1e2fa7c658&690Search的算法赏析" TITLE="基于Local
Search的算法赏析" />
每次在一个邻域N_k中找不到一个更好的解时，就仍然从当前解s出发，换一个领域结构（常常是在一个更大的领域中）搜索，看是否能找到更好的解；当找到一个更好的解s’时，从这一新的解出发，重新返回第一个领域结构开始搜索。这里变换邻域结构时的初衷是当前邻域结构找不到更好的解，而变换（常常为扩大）邻域结构能带来找到更优解的希望，但变换邻域结构时，要保持搜索的初始解（当前解）不变。但值得注意的是：对不同领域结构尝试搜索的算法可能不一样。
2. Iterated Local Search
(ILS)
http://s4/bmiddle/50c15451tdf1e35352f33&690Search的算法赏析" TITLE="基于Local
Search的算法赏析" />
Local Search是在一个领域结构（通常较小，如TSP问题的2-OPT，3-OPT邻域，并行机调度问题的insert邻域）中从一个最优解出发试图找到最好的解，local
search的搜索往往是从一个点到另一个点的顺序化搜索，一点点改进（模拟退火在每个温度上的搜索不也是一种local
search么？只是加入了以一定概率接受差解的机制）。因此local
search的出发点（初始解）就很重要，对出发点的搜索，往往是在一个更大的领域结构内（如TSP问题的4-OPT邻域，并行机调度的swap邻域）随机地选取一点，这种在更大领域内随机选一点的操作称为Perturbation。值得注意的是：Simulated
Annealing (SA), Tabu Search (TS)等也是为了增强local
search而设计的Metaheuristics，它们的整个搜索过程都是一条trajectory，而ILS的搜索过程中由于用了Perturbation来跳出局部最优，所以其搜索过程不再是一条trajectory，这也是ILS与SA、TS的主要不同之处。
博主2013年10月2日注：如果这里Perturbation跟s^*没有关系，是纯随机地产生一个解，那么就不是Iterated
Local Search了，就变成了Multi-start Local Search了。
3. Variable
Neighborhood Search (VNS)
http://s4/bmiddle/50c15451tdf1e3da378a3&690Search的算法赏析" TITLE="基于Local
Search的算法赏析" />
不考虑对解的接受规则（因为AcceptenceCriterion本身可以灵活选用），VNS与ILS的区别仅仅在于：在对local
search初始点搜索(即perturbation)时，VNS并不是仅限于一种领域结构，而是按一定顺序（size从大到小还是从小到大？可有多种不同版本）尝试预先设计好的多个领域结构——从一个领域结构N_k中的一点出发，local
search找不到更好解就从第N_(k+1)个邻域结构的一点出发；一旦找到更好解，下次perturbation时就仍然从第一个邻域结构N_1开始尝试(注意：local
search操作仅仅在N_1领域结构中展开)。VNS与VND的差别在于变换领域的初衷：VND变换领域时local search的出发点不变，即不是为了Perturbation,只是为了改变（扩大）邻域结构能找到更好的解；而VNS变换领域结构目的是perturbation，从几何上看，是从当前搜索的局部区域中跳出来让local
search在另一个局部区域中展开。
4. Variable Neighborhood
Decompostion Search (VNDS)
5. Large Neighborhood Search
(LNS)
那有的小同学又问问题了：杜老师，Large Neighborhood Search
(LNS)又是什么？答：请看下面LNS的Procedure，观察一下差异。
http://s15/mw690/50c15451tdf1e4772aa0e&690Search的算法赏析" TITLE="基于Local
Search的算法赏析" />
看出跟ILS的差异了么？（1）ILS中的Local Search往往邻域较小，所以采用一般的Local
Search即可，而LNS的邻域较大，往往需要其它搜索技术，如Constraint
Programming, MIP-based Method, Dynamic
Programming；（2）ILS中从一个搜索空间跳到另一个搜索空间是靠Perturbation完成的（因为在这个空间中要用local
search,所以空间跳转时只需给一个起始点即可，是为Perturbation），而LNS的搜索空间跳转是靠对当前解随机地定义（给出）一个大邻域完成的（如，固定k个解元素不变，另外n-k个可自由），更加直接。
Enjoy LS! ORson, Dad loves you, such a
ten-month lovely boy!
加载中，请稍候......
加载中…
(2013-06-14 21:44:12)