⾃适应⼤邻域搜索算法（AdaptiveLargeNeighborhoodSearch
——ALNS）
⽬录
这⼜是⼀种基于邻域的搜索算法，邻域及其邻域的相关知识可以看这篇——。之所以单独拿出来，是因为邻域搜索Neighborhood
Search(NS)（本质也是⼀种启发式算法）也是⼀个奇妙的分⽀。
它在邻域搜索的基础上增加了的对算⼦作⽤效果的衡量，使算法能够⾃适应选择好的算⼦对解进⾏破坏与修复，从⽽加速更好的解⽅案的产⽣。
在邻域搜索算法中，如果邻域搜索范围较⼩，那么即使使⽤额外的元启发式技术，如模拟退⽕或禁忌搜索，也很难摆脱陷⼊局部最优的情况；在⼤型邻域搜索技术中(如变邻域搜索算法)，通过在当前解的多个邻域中寻更满意的解，能够⼤⼤提⾼算法在解空间的搜索范围，但是它在使⽤算⼦时盲⽬地将每种算⼦形成的邻域结构都搜索⼀遍，缺少了⼀些启发式信息的指导且时间成本较⾼。
⾃适应⼤邻域搜索算法弥补了这种不⾜，⾸先ALNS算法允许在⼀次搜索中搜索多个邻域，它会根据算⼦
的历史表现与使⽤次数选择下⼀次迭代使⽤的算⼦，通过算⼦间的相互竞争来⽣成当前解的邻域结构，⽽在这种结构中有很⼤概率能够到更好的解。
1.邻域搜索及其⼤家族
1.1 邻域搜索涉及概念
邻域搜索算法（或称为局部搜索算法）是⼀类⾮常常见的改进算法，在每次迭代时通过搜索当前解的“邻域”到更优的解。 邻域搜索算法设计中的关键是邻域结构的选择，即邻域定义的⽅式。 根据以往的经验，邻域越⼤，局部最优解就越好，这样获得的全局最优解就越好。 但是，与此同时，邻域越⼤，每次迭代搜索邻域所需的时间也越长。出于这个原因，除⾮能够以⾮常有效的⽅式搜索较⼤的邻域，否则启发式搜索也得不到很好的效果。所以仍然是时间和解的质量的平衡。
所谓邻域，简单的说即是给定点附近其它点的集合。在距离空间中，邻域⼀般被定义为以给定点为圆⼼的⼀个圆；⽽在组合优化问题中，邻域⼀般定义为由给定转化规则对给定的问题域上每结点进⾏转化所得到的问题域上结点的集合 。通俗⼀点：邻域就是指对当前解进⾏⼀个操作(这个操作可以称之为邻域动作，也可以称为 )可以得到的所有解的集合。那么不同邻域的本质区别就在于邻域动作的不同了。
1.2 邻域搜索的分类
邻域搜索：neighborhood serach，它有好多种衍⽣和变种出来的算法。⽐如⼤邻域Large Neighborhood Serach，LNS；超⼤规模邻域搜索算法Very Large Scale Neighborhood Search，VLSNA ；或者⾃适应邻域搜索Adaptive Large Neighborhood Search
，ALNS。名字很相近，实则⼤有不同。
1.3 超⼤邻域搜索⽅法VLSN
当⼀个邻域搜索算法搜索的邻域规模随着算例规模的增⼤⽽呈指数增长，或者邻域太⼤⽽不能在实际中明确搜索时，我们把这类邻域搜索算法归类为Very Large-Scale Neighborhood Search(VLSN)。
⼀些超⼤规模的邻域搜索⽅法已经运⽤于运筹学中了，并且取得了不错的效果。 例如，如果将求解线性规划的单纯形算法看成邻域搜索算法的话，那么列⽣成算法就是⼀种超⼤规模的邻域搜索⽅法。 此外，⽤于解决许多⽹络流问题的⽅法也可以归类为超⼤规模的邻域搜索⽅法。 ⽤于求解最⼩费⽤流问题的negative cost cycle canceling algorithm和⽤于求解分配问题的augmenting path algorithm就是两个例⼦。[1]
超⼤规模邻域搜索算法VLSN⼜可以分为三类：[1]
Variable-depth methods
Network-flows based improvement algorithms
Efficiently solvable special cases
⽽Large Neighborhood Search(LNS) 则不属于以上三种类型，但它确实是属于VLSN这种类型的，因为它搜索的是⼀个⾮常⼤的邻域。
最后呢，是Adaptive Large Neighborhood Search(ALNS)，它是根据Large Neighborhood Search(LNS) 算法扩展和延伸⽽来（嗯，相当于爸爸和⼉⼦的关系……）。
1.4 ⼤邻域搜索⽅法——邻域通过destroy和repair⽅法隐式定义
Large Neighborhood Serach，LNS，是VLSN的⼀个实例。⼤多数邻域搜索算法都明确定义它们的邻域。 在LNS中，邻域是由destroy 和repair⽅法隐式定义的。destroy⽅法会破坏当前解的⼀部分，⽽后repair⽅法会对被破坏的解进⾏重建。destroy⽅法通常包含随机性的元素，以便在每次调⽤destroy⽅法时破坏解的不同部分。
当前解x经过destroy和repair⽅法以后⽣成的是⼀个邻域（邻居解的集合）。
那么，解x的邻域N（x）就可以定义为：⾸先通过利⽤destroy⽅法破坏解x，然后利⽤repair⽅法重建解x，从⽽得到的⼀系列解的集合（邻域）。
1.4.1 ⾃适应⼤邻域搜索ALNS——为每个destroy和repair⽅法分配⼀个权重
ALNS是从LNS发展扩展⽽来的，在了解了LNS以后，我们现在来看看ALNS。ALNS在LSN的基础上，允许在同⼀个搜索中使⽤多个destroy和repair⽅法来获得当前解的邻域。
ALNS会为每个destroy和repair⽅法分配⼀个权重，通过该权重从⽽控制每个destroy和repair⽅法在搜索期间使⽤的频率。 在搜索的过程中，ALNS会对各个destroy和repair⽅法的权重进⾏动态调整，以便获得更好的邻域和解。
简单点解释，ALNS和LNS不同的是，ALNS通过使⽤多种destroy和repair⽅法，然后再根据这些destroy和repair⽅法⽣成的解的质量，选择那些表现好的destroy和repair⽅法，再次⽣成邻域进⾏搜索。
2.destroy和repair⽅法——邻域构建的关键
关于destroy和repair⽅法，在LNS和ALNS中是要组合在⼀起使⽤的。其实，⼀个解x经过destroy和repair⽅法以后，实则是相当于经过了⼀个邻域动作的变换。如下图所⽰：[1]
上图是三个CVRP问题的解，上左表⽰的是当前解，上右则是经过了destroy⽅法以后的解（移除了6个customers），下⾯表⽰由上右的解经过repair⽅法以后最终形成的解（重新插⼊了⼀些customers）。
上⾯展⽰的只是⽣成邻域中⼀个解的过程⽽已，实际整个邻域还有很多其他可能的解。⽐如在⼀个CVRP问题中，将destroy⽅法定义为：移除当前解x中15%的customers。假如当前的解x中有100名customers，那么就有C（100,15）= 100!/(15!×85!) =2.5×10的17次⽅ 种移除的⽅式。并且，根据每⼀种移除⽅式，⼜可以有很多种修复的⽅法。这样下来，⼀对destroy和repair⽅法能⽣成⾮常多的邻居解，⽽这些邻居解的集合，就是邻域了。
3.ALNS的具体流程
3.1 LNS的伪代码
ALNS是由LNS扩展⽽来的，在了解ALNS之前，先来了解⼀下LNS的具体流程。下⾯是LNS的伪代码：[1]
LNS算法中包含三个变量。变量x^b记录⽬前为⽌获得的最优解，x则表⽰当前解，⽽x^t是临时解（便于回退到之前解的状态）。
函数d(.)是destroy⽅法，⽽r(.)是repair⽅法。详细点就是，d(x)表⽰破坏解x的部分，⽽r(x)则表⽰对破坏的解进⾏重新修复。
在第2⾏中，初始化了全局最优解。在第4⾏中，算法⾸先⽤destroy⽅法，然后再⽤repair⽅法来获得临时解x^t 。在第5⾏中，评估临时解x^t 的好坏，并以此确定该临时解x^t 是否应该成为当前新的解x（第6⾏）。
评估的⽅式因具体程序⽽异，可以有很多种。最简单的评估⽅式就只接受那些变得更优的解。注：评估准则可以参考模拟退⽕的算法原理，设置⼀个接受的可能性，效果也许会更佳。
第8⾏检查新解x是否优于全局最优解x^(b)。此处c(x)表⽰解x的⽬标函数值。如果新获得的解x更优，那么第9⾏将会更新全局最优解
x^(b)。在第11⾏中，检查终⽌条件。在第12⾏中，返回到的全局最优解x^(b)。
从伪代码可以注意到，LNS算法不会搜索解的整个邻域，⽽只是对该邻域进⾏采样搜索。也就是说，这么⼤的邻域是不可能⼀⼀遍历搜索的，只能采样，搜索其中的⼀些解⽽已。
3.2 ALNS的具体流程adaptive
在理解了LNS的基础上，理解ALNS也⾮常easy了。前⾯说过，ALNS对LNS进⾏了扩展，它允许在⼀次搜索中搜索多个邻域（使⽤多组不同的destroy和repair⽅法）。⾄于搜索哪个邻域呢，ALNS会根据邻域解的质量好坏，动态进⾏选择调整。好啦，来看伪代码：[1]
上⾯就是ALNS伪代码。相对于LNS来说，新增了第4⾏和第12⾏，修改了第2⾏。
和分别表⽰destroy和repair⽅法的集合。第2⾏中的  和  分别表⽰各个destroy和repair⽅法的权重集合。⼀开始时，所有的⽅法都设置相同的权重。
第4⾏根据和  选择destroy和repair⽅法。⾄于选择哪个⽅法的可能性⼤⼩，是由下⾯公式算出的：[1]

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。