1 局部搜索
1.1 局部搜索
局部搜索算法是對(duì)一類算法的統(tǒng)稱锄开，符合其框架的算法很多梳猪，比如爬山法、模擬退火算法和禁忌搜索算法都屬于局部搜索算法妆档。盡管各個(gè)算法在優(yōu)化過(guò)程中的細(xì)節(jié)存在差異僻爽，但在優(yōu)化流程上呈現(xiàn)出很大的共性。它的基本原理是在鄰近解中迭代贾惦，使目標(biāo)函數(shù)逐步優(yōu)化胸梆，直至不能再優(yōu)化為止。
1.2 局部搜索的過(guò)程
局部搜索算法的統(tǒng)一框架描述為：
1) 算法從一個(gè)或若干個(gè)初始解出發(fā)须板。
2)在算法參數(shù)控制下由當(dāng)前狀態(tài)的鄰域中產(chǎn)生若干個(gè)候選解碰镜。
3) 以某種策略在候選解中確定新的當(dāng)前解。
4)伴隨控制參數(shù)的調(diào)節(jié)习瑰，重復(fù)執(zhí)行上述搜索過(guò)程绪颖，直至滿足算法終止條件。
5) 結(jié)束搜索過(guò)程并輸出優(yōu)化結(jié)果甜奄。
1.3 局部搜索的幾大要素
局部搜索算法主要包含五大要素：
1) 目標(biāo)函數(shù)：用來(lái)判斷解的優(yōu)劣柠横。
2) 鄰域的定義：根據(jù)不同問(wèn)題窃款，有著不同的鄰域定義。
3) 初始解的產(chǎn)生方法牍氛。
4) 新解的產(chǎn)生和接受規(guī)則晨继。
5) 算法終止條件。
其中前兩個(gè)要素的定義和算法要解決的特定問(wèn)題有關(guān)搬俊，而且不同的人對(duì)同一問(wèn)題可能有完全不同的定義紊扬。后三個(gè)要素定義的不同則會(huì)產(chǎn)生各種不同的局部搜索算法，它們的效率和最終解的質(zhì)量也會(huì)有很大的差異唉擂。
2 變鄰域搜索算法
2.1 什么是變鄰域搜索
變鄰域搜索算法（VNS）是一種改進(jìn)型的局部搜索算法餐屎。它利用不同的動(dòng)作構(gòu)成的鄰域結(jié)構(gòu)進(jìn)行交替搜索。
變鄰域搜索算法依賴于以下事實(shí)：
1) 一個(gè)鄰域結(jié)構(gòu)的局部最優(yōu)解不一定是另一個(gè)鄰域結(jié)構(gòu)的局部最優(yōu)解玩祟。
2)全局最優(yōu)解是所有可能鄰域的局部最優(yōu)解啤挎。
變鄰域搜索算法主要由以下兩個(gè)部分組成：
1) VARIABLE NEIGHBORHOOD DESCENT (VND)
2) SHAKING PROCEDURE
2.2 鄰域
在組合優(yōu)化問(wèn)題中，鄰域一般定義為由給定轉(zhuǎn)化規(guī)則對(duì)給定的問(wèn)題域上每結(jié)點(diǎn)進(jìn)行轉(zhuǎn)化所得到的問(wèn)題域上結(jié)點(diǎn)的集合 卵凑。
通俗一點(diǎn)：鄰域就是指對(duì)當(dāng)前解進(jìn)行一個(gè)操作(這個(gè)操作可以稱之為鄰域動(dòng)作)可以得到的所有解的集合。那么不同鄰域的本質(zhì)區(qū)別就在于鄰域動(dòng)作的不同了胜臊。
2.3 鄰域動(dòng)作
鄰域動(dòng)作是一個(gè)函數(shù)勺卢，通過(guò)這個(gè)函數(shù)，對(duì)當(dāng)前解s象对，產(chǎn)生其相應(yīng)的鄰居解集合黑忱。例如：對(duì)于一個(gè)bool型問(wèn)題，其當(dāng)前解為：s = 1001勒魔，當(dāng)將鄰域動(dòng)作定義為翻轉(zhuǎn)其中一個(gè)bit時(shí)甫煞，得到的鄰居解的集合N(s)={0001,1101,1011,1000}，其中N(s) ∈ S冠绢。同理抚吠，當(dāng)將鄰域動(dòng)作定義為互換相鄰bit時(shí)，得到的鄰居解的集合N(s)={0101,1001,1010}弟胀。
2.4 Variable Neighborhood Descent (VND)
VND其實(shí)就是一個(gè)算法框架楷力，它的過(guò)程描述如下：
1) 給定初始解S； 定義m個(gè)鄰域孵户，記為N_k(k = 1, 2, 3......m)萧朝；i = 1。
2) 使用鄰域結(jié)構(gòu)N_i（即 N_i(S)）進(jìn)行搜索夏哭，如果在N_i(S)里找到一個(gè)比S更優(yōu)的解S′检柬，則令S=S′, i=1 。
3)如果搜遍鄰域結(jié)構(gòu)N_i仍找不到比S更優(yōu)的解竖配，則令i++何址。
4)如果i≤m ,轉(zhuǎn)步驟2里逆。
5) 輸出最優(yōu)解S。
VND的圖解如下：
1）當(dāng)在本鄰域搜索找不出一個(gè)比當(dāng)前解更優(yōu)的解的時(shí)候头朱，我們就跳到下一個(gè)鄰域繼續(xù)進(jìn)行搜索运悲。如圖中虛線所示。
2）當(dāng)在本鄰域搜索找到了一個(gè)比當(dāng)前解更優(yōu)的解的時(shí)候项钮，我們就跳回第一個(gè)鄰域重新開始搜索班眯。如圖中實(shí)線所示。
之前我們把局部搜索比作爬山的過(guò)程烁巫，那么每變換一次鄰域署隘，也可以理解為切換了搜索的地形（landscape）。效果如下 ：
偽代碼描述如下：
2.5 shaking procedure
就是一個(gè)擾動(dòng)算子亚隙，類似于鄰域動(dòng)作的這么一個(gè)東西磁餐。通過(guò)這個(gè)算子，可以產(chǎn)生不同的鄰居解阿弃。雖然名詞很多看起來(lái)很高大上诊霹，擾動(dòng)、抖動(dòng)渣淳、鄰域動(dòng)作這幾個(gè)本質(zhì)上還是沒有什么區(qū)別的脾还。都是通過(guò)一定的規(guī)則，將一個(gè)解變換到另一個(gè)解而已入愧。
2.6 VNS過(guò)程
在綜合了前面這么多的知識(shí)以后鄙漏，VNS的過(guò)程其實(shí)非常簡(jiǎn)單, 直接看偽代碼，一目了然：
偽代碼中N_k和N_l代表的鄰域集合棺蛛，分別是給Shaking和VND使用的怔蚌，這兩點(diǎn)希望大家要格外注意，區(qū)分開來(lái)哈旁赊。這兩個(gè)鄰域集合可以是一樣的桦踊，也可以不一樣。
