首先声明本文是在参考《数据魔术师》公众号的《干货 | 变邻域搜索算法(VariableNeighborhood Search,VNS)超详细一看就懂》这一篇文章的基础上，并结合自己的理解撰写《VNS通俗讲解》，并给出自己编写的VNS解决TSP问题的matlab代码
文章目录：
1.VNS基本知识
1.1.邻域结构
1.2 VNS操作流程
2.代码实例
1.VNS基本知识
变邻域搜索算法（Variable Neighborhood Search简称VNS）属于一种局部搜索算法。顾名思义，变邻域搜索是指通过改变邻域结构来达到搜索得到近优解的过程。
VNS基于以下2个事实：
- A local minimum w.r.t. oneneighborhood structure is not necessarily so for another;（一个邻居结构的局部最优解不一定是另一个邻域结构的局部最优解）；
- A global minimum is a local minimum w.r.t. all possible neighborhood structures.（全局最优解是所有可能邻域的局部最优解）。
看到这里各位小伙伴可能还有点蒙，没关系，接下来小编先从邻域结构的定义开始阐述，然后详细讲解VNS的操作流程。
1.1邻域结构
还是以TSP问题为例，假设初始解为1 2 3 4
那么所谓的邻域结构就是通过某种算子的变换操作所得到的新的解的集合。这里我们以交换算子和插入算子为例
1）交换算子
交换算子就是交换两个元素的位置，共有6种可能，即：
(1)2 1 3 4
(2)3 2 1 4
(3)4 2 3 1
(4)1 3 2 4
(5)1 4 3 2
(6)1 2 4 3
以上6个新解就组成了一个邻域结构
2）插入算子
插入算子就是随机选择一个元素插入到最开始的位置，其他元素依次后退。共有3种可能，即：
(1)2 1 3 4
(2)3 1 2 4
(3)4 1 2 3
以上3个解同样也组成了一个邻域结构
1.2VNS操作流程
基本VNS由两部分组成VND(variable neighborhood descent)和shaking
- 首先来看VND
VND说白了其实就是一个算法框架，当你在第1个邻域中搜索到更好的解时，这时应该及时更新解，并且还在第1个邻域中继续搜索，直到在第1个邻域中，找不到比目前的解更好的解时。这时才可以换到第2个邻域搜索（因为在第1个邻域中已经找不到比目前的解更好的解了，再不换邻域是不是傻。。。），然后重复上述动作继续搜索，直到把所有的邻域都搜索完。其实小伙伴们可以发现这是一种“变则通”的思想。
- 再来看shaking
其实shaking和算子变换操作一样，将当前解通过某种算子变换成另一个解。
通过上述两部分的讲解，VNS求解问题的流程图如下所示：
然说N_k(S)和N_l(S)可以相同，也可以不同，但小编建议最好还是将N_k(S)和N_l(S)设置为不同的邻域结构，个人建议，效果不好别打我。
2.VNS求解TSP问题matlab代码实例
运行方式打开VNS.m文件即可运行
链接：https://pan.baidu.com/s/1SLzV4cRJ9rCYtQFQBwEYIA
提取码：wqu2
最后小伙伴们可以后台留言，想学习什么优化算法，小编会尽可能给大家讲解。