一、旅行商问题(Traveling Salesman Problem)介绍
旅行商问题描述如下：假设有若干个城市，且任何两个城市之间的距离是确定的，现有一个旅行商人要拜访这些城市，要求旅行商从某城市出发，必须经过每个城市，且每个城市只能拜访一次，最后要回到出发的城市，问如何确定一条路线使路径长度最短。
详细介绍见blog：LocalSearch之爬山算法
二、VND（Variable Neighborhood Descent）算法介绍
2.1什么是VND（Variable Neighborhood Descent）？
变量邻域下降法(Variable Neighborhood Descent, VND)是由Mladenovic和Hansen(1997)首次提出的一种局部搜索算法，在求解空间中交替搜索并考虑邻域结构。VND可以看作一个算法框架，最大的特点是有多个邻域，且以确定的（deterministic）方式来改变邻域。VND算法的邻域数一般不小于2，如果VND算法的邻域只有一个，那么就与普通的爬山算法类似。
2.2 VND一般过程
算法伪代码如下[1]：
其中，Nk(k=1,2,3...kmax)表示预先选定的邻域结构(neighborhood structures)。Nk(x)表示x的第k个邻域中的一系列解。f(x)表示解x的价值（value）。
伪代码的具体流程如下：
(1)给定初始解x;定义k个邻域，记为Nk(k=1,2,3...kmax)
(2)k的初始值设为1
(3)重复以下步骤，直到k=kmax
(4)在Nk(x)中找到最优解x'
(5)对比当前解的价值f(x)与新解的价值f(x')。如果新解x'相比于当前解x有改进，那么当前解更新为新解x'、k返回初始值1
(6)否则，k=k+1
如下图所示可以更简单理解：
不同于爬山单个邻域：VND有多个邻域，在第k个邻域做单次爬山：当在本邻域找不到更好的解时，前进到下一个邻域单次爬山，如上图中的虚线所示；如果在本邻域中找到了比当前解更好的解，就跳回第一个邻域重新搜索，如上图中的红线所示。过程会一直持续下去，直到探索到第k个邻域结构，在现有的解决方案中没有改进，或者直到某个停止准则得到满足。
三、VNS（Variable Neighborhood Search）算法介绍
3.1什么是VNS（Variable Neighborhood Search）？
变邻域搜索算法（Variable neighborhood search）是一种基于邻域系统变化思想（systematic change of neighborhood）的局部搜索算法，能够很好的平衡集中性和疏散性。
VNS算法基于以下三个事实[1]：
（1）一个邻域结构中的局部最优解未必是其它邻域的局部最优解
（2）全局最优解一定是所有邻域的局部最优解
（3）在一些问题中，不同邻域结构的局部最优解相对接近。这意味着局部最优解往往会提供有关全局最优解的一些信息。
VNS主要由两个部分组成：
（1）下降阶段（descent phase）
（2）扰动阶段（perturbation phase）
算法在下降（descent）阶段寻找局部最优解，在扰动（perturbation）阶段跳出局部最优。所以VNS算法在局部搜索时，倾向于选择集中性较强的邻域算子；而在扰动阶段，倾向于选择探索性强的算子。
3.2什么是扰动（perturbation/shake）？
扰动可以看做一个类似于邻域动作的算子，通过这个算子可以产生不同的邻近解，VNS算法中的扰动阶段能够帮助算法跳出局部最优解。
一些常见的邻域算子，例如swap、insert、2opt等也可作为一种扰动算子，具体内容可参考前两期系列博文，下面举例介绍一种探索性较好的扰动算子DoubleBridge，它是一种特殊的4-opt，图解如下：
将一条回路分割成四段，按照以下步骤修改连接方式就能产生DoubleBridge结果：
（1）初始状态：ABCD（c2 ->d1 ->d2 ->c3 ->c4 ->d3 ->d4 ->c1）
（2）交换BC边（c2 ->d1 ->d3 ->c4 ->c3 ->d2 ->d4 ->c1）
（3）交换bD边（c2 ->d1 ->d3 ->c4 ->c1 ->d4 ->d2 ->c3）
（4）交换cd边（c2 ->d1 ->d4 ->c1 ->c4 ->d3 ->d2 ->c3）
实现DoubleBridge扰动算子的Matlab代码如下:
结合下图可以看出，假设pos0是初始位置，算法寻找了3个分割点pos1、pos2和pos3，将一个解分割成4条边ABCD，在经过DoubleBridge重新连接之后，变为了ADCB。
3.3 VNS怎么实现？
下面将分别介绍两种VNS的实现方法：BVNS(Basic Variable Neighborhood Search)和GVNS(General Variable Neighborhood Search)，两者的区别主要在于：BVNS在descent阶段采用的是普通的爬山算法，而GVNS在descent阶段采用的是VND。
3.3.1 GVNS（General VNS）
GVNS的伪代码如下[1]：
伪代码的具体流程如下：
(1)选定初始解x作为当前解；定义l个用于VND的邻域结构，记为Nl(k=1,2,3...lmax)；定义k个用于抖动操作的邻域结构，记为Nk(k=1,2,3...kmax)；选择算法的终止条件，即CPU处理时限tm。
(2)重复以下步骤，直到t>tmax
(3)k的初始值设为1
(4)重复以下步骤，直到k=kmax
(5)通过扰动，在当前解的第k个邻域结构中随机生成解x'
(6)对x'进行VND局部搜索，得到解x''
(7)对比当前解x的价值f(x)与解x''的价值f(x'')。如果x''相比于当前解x有改进，那么当前解更新为新解x''、k返回初始值1
(8)否则，k=k+1
算法的终止条件并不唯一，比如上文选用的是：允许的最大CPU处理时间tmax；此外，也可以选择两次改进之间的最大迭代次数等其它条件。
3.3.2 BVNS（Basic VNS）
BVNS也是VNS算法中的一种，就是将GVNS中局部搜索的算法用普通爬山算法代替。
BVNS的伪代码如下[1]：
四、用VNS算法解决TSP问题
4.1 TSP问题
（1）解的表示方式：对城市进行编号，编号序列表示城市的访问顺序，不同的编号序列表示不同的解。
（2）初始解的生成方式：随机生成编号序列
4.2 VNS算法相关信息
扰动方式：swap、insert，LS邻域算子（即VND的邻域算子）：2opt、swap、insert，邻近解的选择策略是bestImprove或firstImprove（下文以bestImprove为例）。
4.3 以GVNS算法为例，解决思路如下：
（1）设置参数：最大迭代次数maxIter，扰动算子共kmax种，LS邻域算子共lmax种。
（2）初始化：Bestsol用于记录最优解，Bestsol.Cost的初始值为无限大；迭代次数初始值为1，k=1，l=1；随机生成初始解sol作为当前解，并计算该解的路径长度Cost。
（3）通过第k种扰动算子，对sol进行扰动，得到解shakeSol。
（4）当l≤lmax时，进行以下的步骤：
（a）通过第l种邻域算子、bestImprove的邻域选择策略，找到shakeSol邻域中的最优解newsol
（b）比较shakeSol和newsol的Cost，若newsol优于shakeSol，那么把shakeSol更新为newsol、令l=1；否则，shakeSol保持不变，l=l+1。
（5）比较shakeSol与Bestsol的Cost，判断是否更新Bestsol
（6）比较newsol（实际上与shakeSol的值相同）和当前解sol的Cost，若newsol优于当前解sol，那么把sol更新为newsol、令k=1；否则，sol保持不变，k=k+1。返回到（3）。
4.4 Matlab代码实现及结果分析
Matlab代码见文末链接。
本文借助Matlab，对TSP问题中经典的Berlin52算例做了分析。为保证结果可复现，以rng函数确定随机种子，以下为实验结果：
4.4.1算法原理分析
实验结果部分如图所示，由此可分析出算法的具体实现过程：
算法先生成一个初始解26981，通过Swap算子扰动后得到新目标值27242，并从新目标值27242开始进行VND搜索，找到邻域内的最优解7746；然后使用Swap算子对当前目标值7746扰动后得到新目标值9529，并从新目标值9529开始进行VND搜索，找到邻域内的最优解还是7746，相对于原目标值没有改进，说明Swap算子无法帮助我们跳出当前局部最优困境；
所以放弃Swap算子开始使用第二个Insert算子进行扰动操作，把当前目标值7746扰动后得到新目标值8495，并从新目标值8495开始进行VND搜索，找到邻域内的最优解还是7746，说明Swap算子同样无法帮助跳出当前局部最优困境；
同理，放弃Insert算子开始使用第三个Doublebridge算子进行扰动操作，把当前目标值7746扰动后得到新目标值8021，并从新目标值8021开始进行VND搜索，找到邻域内的最优解为7542，很明显优于原目标值7746，说明Doublebridge算子已经带领我们来到一片新大陆，然后我们会重新从第一个扰动算子开始探索这片新大陆的同时，寻找另一片新大陆。
如果对第三个Doublebridge算子扰动后的目标值进行VND搜索得到的解仍然没有改进，此时程序就会结束运行，这种情况说明当前解即是允许迭代次数下的最优解。
4.4.2扰动算子比较
在随机种子为rng(1)的实验中：使用doublebridge扰动算子，第1次迭代就能得到较好的解7542，若不使用doublebridge扰动算子，需要迭代17次才能得到7542这个解。
同样的，在随机种子为rng(2)的实验中：使用doublebridge扰动算子，第10次迭代就能得到解7542，若不使用doublebridge扰动算子，需要迭代61次才能得到7542这个解。
从实验结果能看出在算法设计的过程中选择合适且高效的扰动算子会得到更优的解，帮助算法跳出局部最优解。
五、ILS（Iterated Local Search）算法介绍
5.1 什么是ILS？
迭代邻域搜索算法（Iterated Local Search, ILS）属于探索性局部搜索方法（Explorative Local Search Methods）的一种。它在局部搜索得到的局部最优解上，加入了扰动（perturbation），然后再重新进行局部搜索。其思想是：物以类聚，好的解之间会有一些共性，所以在局部最优解上做扰动，比随机的选择一个初始解在进行局部搜索，效果更好。
5.2扰动及其特点
在3.2节已详细介绍。但不论是迭代邻域搜索，还是变邻域搜索，其扰动强度都具备以下特点：
⑴扰动强度不能太弱。如果扰动强度太弱，不足以保证能跳出目前的局部最优困境，局部搜索将经常退回到刚刚访问过的局部最优，并且搜索的多样化将非常有限；
⑵扰动强度不能太强。如果扰动强度太强，ILS可能表现得像随机搜索，导致找到更好解决方案的概率会降低。
5.3迭代邻域搜索算法伪代码
注：s0为初始解(Initial Solution)，s*为通过局部搜索得到的局部最优解，s'为扰动后得到的新解，s*'为新解局部搜索再次找到一个局部最优解。
伪代码含义如下[1]：
⑴生成初始解决方案s0;
⑵从初始方案s0开始进行局部搜索，找到此邻域中的一个局部最优解s*；
⑶重复以下步骤；
⑷扰动当前解s*，获得一个新解s'；
⑸从新解s'开始进行局部搜索，再次找到一个局部最优解s*'；
⑹基于接受标准，对局部最优解s*'好坏进行判断，选择是否接受s*'作为新的最优解。
⑺直到满足终止条件，不然跳回第二步一直循环搜索。
5.4 ILS的三种接受标准
接受标准的选择，可以用来控制搜索的强化和多样化之间的平衡。
⑴只接受更好的解决方案。强化并集中搜索那些看起来可能有更优解的邻域，以找到最好的解决方案；
⑵任何解都可接受。这个标准明显倾向于多样化或探索性；
⑶二者均衡，类似SA的接受标准。如果新解更好，则直接接受；如果新解较差，则概率性接受（详见LocalSearch之模拟退火算法）。
六、用迭代邻域搜索算法解决TSP问题
6.1 ILS算法相关信息
⑴解的表示：对城市进行编号，编号序列表示城市的访问顺序，不同的编号序列即表示TSP问题不同的解。
⑵初始解的生成方式：随机生成编号序列。
⑶邻居解的选择策略：bestImprove/firstImprove
⑷邻域算子：swap、insert、2-opt中的一个或多个。
⑸扰动算子：doublebridge/swap/insert/2opt。
6.2 解决思路
⑴设置参数：最大迭代次数maxIter，如果接受标准为SA，还需设置温度ck、降温系数α等参数。
⑵初始化：Bestsol用于记录最优解，Bestsol.Cost的初始值为无限大；迭代次数初始值为1，随机生成初始解sol作为当前解，并计算该解的路径长度Cost。
⑶从初始解sol开始进行VND搜索，找到一个局部最优解Bestsol。
⑷通过扰动算子，对Bestsol进行扰动，得到新解shakeSol。
⑸从新解shakeSol开始进行VND搜索，再次找到shakeSol邻域内的最优解newsol。
⑹本文是基于SA接受标准，判断sol与newsol的好坏。如果newsol优于sol，则接受newsol为当前解（sol）；否则，则概率性接受。
⑺直至达到最大迭代次数时终止程序，否则一直循环运行步骤3至步骤6。
6.3 Matlab代码实现（代码见文末链接）
本文借助Matlab，对TSP问题中经典的Berlin52算例做了分析。接受标准SA参数设定初始温度c0=350，降温系数alpha=0.995，邻近解的选择策略为bestImprove。为保证结果可复现，以rng函数确定随机种子，实验结果如下：
由实验结果可知，其他条件相同时,适用于目标问题的算子数量增加，实验结果相对会有所改善。此外，即使同样VND数量算子，顺序不同导致的结果也会不同。比如2opt,swap,insert的结果不同于swap,insert,2opt。
七、算法对比
比较本文所涉及算法的邻域算子、扰动算子如下表所示：
由表可知，VNS算法的特点是多邻域、多扰动，即多变则通；而ILS算法扰动性要比VNS差点。经实验可得，同一算例下，其他条件皆相同，VNS算法有swap、insert、doublebridge三个扰动算子，得到目标值为7542；而ILS算法只有doublebridge一个扰动算子，得到目标值为7898。
八、小结
本篇主要介绍了VND（Variable Neighborhood Descent）算法、变邻域搜索算法（VNS）和迭代邻域搜索算法（ILS）的原理，并使用Matlab展示了相关算法解决TSP问题实例以及扰动算子、领域算子对于实验结果的影响。最后对算法进行了横向比较。
【囿于作者的学术水平，本文的诸多表述或许不够严谨，用途仅限于优化算法入门者的非正式学术交流，不足之处还望各位读者指正。】
参考文献：
相关资料：
作者：刘梦迪 张雨沁
校对：任珈岳
