⾃适应⼤邻域搜索（AdaptiveLargeNeighborhoodSearch）-详
解
⼀、概念
关于neighborhood serach的总体关系
当⼀个邻域搜索算法搜索的邻域规模随着算例规模的增⼤⽽呈指数增长，或者邻域太⼤⽽不能在实际中明确搜索时，我们把这类邻域搜索算法归类为Very Large-Scale Neighborhood Search(VLSN)。
VLSN⼜可以分为三类：
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.1 Neighborhood Search(NS)
邻域搜索算法（或称为局部搜索算法）是⼀类⾮常常见的改进算法，其在每次迭代时通过搜索当前解的“邻域”到更优的解。 邻域搜索算法设计中的关键是邻域结构的选择，即邻域定义的⽅式。 根据以往的经验，邻域越⼤，局部最优解就越好，这样获得的全局最优解就越好。 但是，与此同时，邻域越⼤，每次迭代搜索邻域所需的时间也越长。出于这个原因，除⾮能够以⾮常有效的⽅式搜索较⼤的邻域，否则启发式搜索也得不到很好的效果。
邻域就是指对当前解进⾏⼀个操作(这个操作可以称之为邻域动作)可以得到的所有解的集合。
邻域动作是⼀个函数，通过这个函数，对当前解s，产⽣其相应的邻居解集合。例如：对于⼀个bool型问题，其当前解为：s = 1001，当将邻域动作定义为翻转其中⼀个bit时，得到的邻居解的集合N(s)={0001,1101,1011,1000}，其中N(s) ∈ S。同理，当将邻域动作定义为互换相邻bit时，得到的邻居解的集合N(s)={0101,1001,1010}。
1.2 什么是VLSN？
对于⼀个邻域搜索算法，当其邻域⼤⼩随着输⼊数据的规模⼤⼩呈指数增长的时候，那么我们就可以称该邻域搜索算法为超⼤规模邻域搜索算法（Very Large Scale Neighborhood Search Algorithm，VLSNA ）
例如，如果将求解线性规划的单纯形算法看成邻域搜索算法的话，那么列⽣成算法就是⼀种超⼤规模的邻域搜索⽅法。 此外，⽤于解决许多⽹络流问题的⽅法也可以归类为超⼤规模的邻域搜索⽅法。 ⽤于求解最⼩费⽤流问题的negative cost cycle canceling algorithm和⽤于求解分配问题的augmenting path algorithm就是两个例⼦
VLSN在WIKI上的定义：
1.3 什么是LNS？
Large Neighborhood Serach，LNS，是VLSN的⼀个实例。⼤多数邻域搜索算法都明确定义它们的邻域。 在LNS中，邻域是
由destroy和repair⽅法隐式定义的。destroy⽅法会破坏当前解的⼀部分，⽽后repair⽅法会对被破坏的解进⾏重建。destroy⽅法通常包含随机性的元素，以便在每次调⽤destroy⽅法时破坏解的不同部分。
那么，解x的邻域N（x）就可以定义为：⾸先通过利⽤destroy⽅法破坏解x，然后利⽤repair⽅法重建解x，从⽽得到的⼀系列解的集合。
1.4 什么是ALNS？
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.1 destroy和repair⽅法
其实，⼀个解x经过destroy和repair⽅法以后，实则是相当于经过了⼀个邻域动作的变换。如下图所⽰：
上图是三个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⽅法能⽣成⾮常多的邻居解，⽽这些邻居解的集合，就是邻域了。
2.2、 LNS的具体流程
下⾯是LNS的伪代码：
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算法不会搜索解的整个邻域，⽽只是对该邻域进⾏采样搜索。也就是说，这么⼤的邻域是不可能⼀⼀遍历搜索的，只能采样，搜索其中的⼀些解⽽已。
2.3 ALNS的具体流程
adaptiveALNS对LNS进⾏了扩展，它允许在⼀次搜索中搜索多个邻域（使⽤多组不同的destroy和repair⽅法）。⾄于搜索哪个邻域呢，ALNS
会根据邻域解的质量好坏，动态进⾏选择调整。伪代码如下：
相对于LNS来说，新增了第4⾏和第12⾏，修改了第2⾏。
Ω^−和Ω^+分别表⽰destroy和repair⽅法的集合。第2⾏中的ρ^−和ρ^+分别表⽰各个destroy和repair⽅法的权重集合。⼀开始时，所有的⽅法都设置相同的权重。
第4⾏根据ρ^−和ρ^+选择destroy和repair⽅法。⾄于选择哪个⽅法的可能性⼤⼩，是由下⾯公式算出的：
即，总的来说，权重越⼤，被选中的可能性越⼤。
除此之外，权重⼤⼩是根据destroy和repair⽅法的在搜索过程中的表现进⾏动态调整的（第12⾏）。具体调整⽅法：在ALNS完成⼀次迭代搜索以后，我们使⽤下⾯的函数为每组destroy和repair⽅法的好坏进⾏⼀个评估：
其中，ω_1 ≥ ω_2 ≥ ω_3 ≥ ω_4 ≥0。为⾃定的参数。
假如，a和b是上次迭代中使⽤的destroy和repair⽅法。那么其权重更新如下所⽰：
其中，λ∈[0,1]，为参数。
在⼀个ALNS算法中，有很多个邻域，每个邻域都可以看做是⼀组destroy和repair⽅法⽣成的。

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