首先聲明本文是在參考《資料魔術師》公衆号的《幹貨 | 變鄰域搜尋算法(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