领域

官方一点：所谓邻域，简单的说即是给定点附近其它点的集合。在距离空间中，邻域一般被定义为以给定点为圆心的一个圆；而在组合优化问题中，邻域一般定义为由给定转化规则对给定的问题域上每结点进行转化所得到的问题域上结点的集合 （太难懂了 呜呜呜.....）。

通俗一点：邻域就是指对当前解进行一个操作(这个操作可以称之为邻域动作)可以得到的所有解的集合。那么不同邻域的本质区别就在于邻域动作的不同了。

邻域动作是一个函数，通过这个函数，对当前解s，产生其相应的邻居解集合。例如：对于一个bool型问题，其当前解为：s = 1001，当将邻域动作定义为翻转其中一个bit时，得到的邻居解的集合N(s)={0001,1101,1011,1000}，其中N(s) ∈ S。同理，当将邻域动作定义为互换相邻bit时，得到的邻居解的集合N(s)={0101,1001,1010}。

Variable Neighborhood Descent (VND)

VND其实就是一个算法框架，它的过程描述如下：

1) 给定初始解S； 定义m个邻域，记为N_k(k = 1, 2, 3......m)；i = 1。

2) 使用邻域结构N_i（即 N_i(S)）进行搜索，如果在N_i(S)里找到一个比S更优的解S′，则令S=S′, i=1 。

3)如果搜遍邻域结构N_i仍找不到比S更优的解，则令i++。

4)如果i≤m ,转步骤2。

5) 输出最优解S。

1)当在本邻域搜索找不出一个比当前解更优的解的时候，我们就跳到下一个邻域继续进行搜索。如图中虚黑线所示。

2)当在本邻域搜索找到了一个比当前解更优的解的时候，我们就跳回第一个邻域重新开始搜索。如图中红线所示。

之前我们把局部搜索比作爬山的过程，那么每变换一次邻域，也可以理解为切换了搜索的地形（landscape）。效果如下 ：

每一次跳跃，得到都是一个新的世界……

伪代码

shaking procedure

其实呀，这玩意儿。说白了就是一个扰动算子，类似于邻域动作的这么一个东西。通过这个算子，可以产生不同的邻居解。虽然名词很多看起来很高大上，扰动、抖动、邻域动作这几个本质上还是没有什么区别的。都是通过一定的规则，将一个解变换到另一个解而已。这里读者还是抓其本质，不要被表象所迷惑了就好。

VNS过程

在综合了前面这么多的知识以后，VNS的过程其实非常简单, 直接看伪代码，一目了然：

做点说明吧。伪代码中N_k和N_l代表的邻域集合，分别是给Shaking和VND使用的，这两点希望大家要格外注意，区分开来哈。这两个邻域集合可以是一样的，也可以不一样。

本打算将伪代码用文字来翻译一下，但是这个过程太痛苦了，小编抓狂了一阵后就放弃了。拜托大家还是看伪代码吧。有什么疑问请在留言区提出来，小编会老老实实的回复的。

什么是VNS?

对上面的局部搜索有一定的印象后，理解变邻域搜索也不难了。其实说白了，变邻域搜索算法（VNS）就是一种改进型的局部搜索算法。它利用不同的动作构成的邻域结构进行交替搜索，在集中性和疏散性之间达到很好的平衡。其思想可以概括为“变则通”。

变邻域搜索算法依赖于以下事实：

1) 一个邻域结构的局部最优解不一定是另一个邻域结构的局部最优解。

2)全局最优解是所有可能邻域的局部最优解。

变邻域搜索算法主要由以下两个部分组成：

1) VARIABLE NEIGHBORHOOD DESCENT (VND)

2) SHAKING PROCEDURE

https://cloud.tencent.com/developer/article/1146083