一種新型的變領(lǐng)域搜索算法

于繼江

(菏澤學(xué)院 計(jì)算機(jī)與信息工程系，山東 菏澤 274015)

0 引言

變鄰域搜索算法（VNS, Variable Neighborhood Search）是一種求解優(yōu)化問(wèn)題的啟發(fā)式算法，是有 Hansen 和Mladenovic′首次提出。它的基本思想在搜索過(guò)程中系統(tǒng)地改變鄰域結(jié)構(gòu)集來(lái)拓展搜索范圍，獲得局部最優(yōu)解，再基于此局部最優(yōu)解重新系統(tǒng)地改變鄰域結(jié)構(gòu)集拓展搜索范圍找到另一個(gè)局部最優(yōu)解的過(guò)程。由于VNS在簡(jiǎn)易性、時(shí)效性、人性化和創(chuàng)新性等方面表現(xiàn)突出，若干改進(jìn)算法已應(yīng)用于NP難問(wèn)題的求解中[1-4]。

VNS提出后被應(yīng)用于很多組合優(yōu)化問(wèn)題的求解，許多應(yīng)用實(shí)例也表明了VNS對(duì)解決組合優(yōu)化問(wèn)題的優(yōu)越性能[5-7]。對(duì)于組合優(yōu)化問(wèn)題，一個(gè)鄰域內(nèi)的可行解是有限的，因此在局部搜索過(guò)程中，是可以計(jì)算出鄰域內(nèi)的所有可行解的目標(biāo)函數(shù)值，進(jìn)而找到鄰域內(nèi)的最優(yōu)解，即局部最優(yōu)解。區(qū)別于組合優(yōu)化問(wèn)題，連續(xù)優(yōu)化問(wèn)題中的可行解空間是連續(xù)的，因此無(wú)法找到鄰域內(nèi)所有可行解，也就無(wú)法找到局部最優(yōu)解。

針對(duì)上述問(wèn)題，提出了一種結(jié)合序列二次規(guī)劃法(SQP,Sequential Quadratic Programming)的變鄰域搜索方法，并將其應(yīng)用到無(wú)約束連續(xù)優(yōu)化問(wèn)題中。

1 結(jié)合SQP的變鄰域搜索算法

SQP是當(dāng)前公認(rèn)的處理中、小規(guī)模非線(xiàn)性規(guī)劃問(wèn)題最優(yōu)秀的算法之一，它具有良好的局部收斂性和較強(qiáng)的超線(xiàn)性收斂速度。它能快速精確地獲取當(dāng)前點(diǎn)附近的局部極小點(diǎn)。為了較好處理VNS中的局部搜索過(guò)程，更快速、更精確得到局部最優(yōu)解，將SQP結(jié)合到VNS中，即應(yīng)用SQP求解局部搜索過(guò)程中的局部最優(yōu)解。這樣既保持了SQP在求解局部最優(yōu)解上的優(yōu)勢(shì)，又突出了VNS全局收斂性的特點(diǎn)。

對(duì)于一個(gè)問(wèn)題 P，設(shè)初始解為 x，鄰域結(jié)構(gòu) Nk(x),k=1,2,…,kmax，設(shè)定參數(shù)的初始值，kmax,tmax,kstep，其中kmax為最大鄰域，tmax為最大計(jì)算時(shí)間，kstep是每次迭代的鄰域步數(shù)。

結(jié)合SQP的VNS算法流程如下：

①令k=1；②隨機(jī)選取x的 p鄰域中的一點(diǎn)x′（x′ ∈Np(x)）；③以x′為初始解，運(yùn)行SQP算法，獲得局部最優(yōu)解x′；④若 f(x′′)＜f(x)，令 x=x′′，轉(zhuǎn)到步驟①，反之，令 k=k+kstep，轉(zhuǎn)到步驟②；⑤若終止規(guī)則滿(mǎn)足，則終止計(jì)算。

在VNS的應(yīng)用中，為了加快算法的運(yùn)行速度、提高算法的搜索精度，可以采用以下策略改進(jìn)算法。

（1）初始點(diǎn)策略

在VNS中初始點(diǎn)的選取，對(duì)最后得到的最優(yōu)解和運(yùn)算時(shí)間、迭代步數(shù)有直接的影響，若初始點(diǎn)選取的好，能夠盡可能的靠近全局最優(yōu)解，得到全局最優(yōu)解所需要的時(shí)間以及迭代步數(shù)就會(huì)減少。在初始點(diǎn)選取中，可以采用多點(diǎn)選擇，取目標(biāo)函數(shù)值最小的一個(gè)點(diǎn)作為初始值。

（2）多樣性策略

在VNS中一般包含3個(gè)部分：隨機(jī)擾動(dòng)、局部搜索、鄰域變換。當(dāng)通過(guò)局部搜索過(guò)程，找到一個(gè)局部最優(yōu)解時(shí)，利用隨機(jī)擾動(dòng)的方法，在距離局部最優(yōu)解一定距離的地方，選取一個(gè)可行解作為新的局部搜索的起始點(diǎn)。這樣就能夠從局部最優(yōu)解的“山谷”中脫離出來(lái)，從而找到全局最優(yōu)點(diǎn)。

一般VNS中，每次的隨機(jī)擾動(dòng)都只是選擇k鄰域中的一點(diǎn)。當(dāng)鄰域比較大時(shí)，鄰域內(nèi)的可行解數(shù)量就會(huì)比較多，由于擾動(dòng)的隨機(jī)性，只隨機(jī)選取一點(diǎn)，有可能就會(huì)漏掉全局最優(yōu)解。因此，可以采用多樣性（Diversification）策略，選取鄰域內(nèi)的多個(gè)點(diǎn)作為起始點(diǎn)，對(duì)每個(gè)點(diǎn)進(jìn)行局部搜索，選取其中最優(yōu)的局部最優(yōu)解與現(xiàn)有最優(yōu)解比較。這樣可以盡可能的搜索整個(gè)區(qū)域，以達(dá)到尋找全局最優(yōu)解的目的。

對(duì)于一個(gè)問(wèn)題 P，設(shè)初始解為x，鄰域結(jié)構(gòu)Nk(x),k=1,2,…,kmax，設(shè)定參數(shù)的初始值，kmax,tmax,kstep，其中kmax為最大鄰域，tmax為最大計(jì)算時(shí)間，kstep是每次迭代的鄰域步數(shù)。

改進(jìn)的VNS算法流程如下：

以上算法中多樣性部分可以用并行化處理。

2 數(shù)值實(shí)驗(yàn)

實(shí)驗(yàn)所用的計(jì)算機(jī)配置Core2 Duo CPU，主頻2.17 GHz，2 GB內(nèi)存，操作系統(tǒng)為 windows7，使用的編程軟件是MATLAB2009.優(yōu)化算法的比較通常是基于一些標(biāo)準(zhǔn)函數(shù)的典型問(wèn)題展開(kāi)的通過(guò)5個(gè)標(biāo)準(zhǔn)函數(shù)(見(jiàn)表1示)測(cè)試算法的性能。這些函數(shù)具有多峰、非凸等特點(diǎn),經(jīng)常被國(guó)外學(xué)者用于對(duì)優(yōu)化問(wèn)題的測(cè)試。

表1 5個(gè)標(biāo)準(zhǔn)的測(cè)試函數(shù)

首先比較所提出的VNS算法與純SQP算法的求解效果。對(duì)于VNS算法，首先在可行域內(nèi)隨機(jī)選取了20個(gè)點(diǎn)，選擇其中目標(biāo)函數(shù)值最小的作為初始解，鄰域半徑差為 0.1，最大迭代次數(shù) kmax=20。SQP算法采用MATLAB優(yōu)化工具箱中的fmincon函數(shù)。為了使結(jié)果具有可比性，兩種算法都從相同的初始解開(kāi)始，對(duì)每個(gè)函數(shù)（前兩個(gè)函數(shù)取n=2）做了 5次實(shí)驗(yàn)，對(duì)比了最優(yōu)解的情況，得到的結(jié)果如表2。

從表2可以看出，VNS算法具有很好的全局收斂性，最優(yōu)解和目標(biāo)函數(shù)值都能夠精確到 1e-8以上，尋優(yōu)的精確性都遠(yuǎn)好于單純的SQP算法。特別對(duì)于測(cè)試函數(shù)Shubert，使用 VNS算法，很容易找到了全部 18個(gè)最優(yōu)解，分別是：(-7.7083,-7.0835),(-7.7083,-0.8003),(-7.7083,5.4829),(-7.0835,-7.7083),(-7.0835,-1.4251),(-7.0835,4.8581),(-1.4251,-7.0835),(-1.4251,-0.8003),(-1.4251,5.4829),(-0.8003,-1.4251),(-0.8003,4.8581),(-0.8003,-7.7083),(4.8581,-7.0835),(4.8581,-0.8003),(4.8581,5.4829),(5.4829,-7.7083),(5.4829,4.8581),(5.4829,-1.4251)。由此可以看出，VNS算法的有效性。

然后，比較所提出的VNS算法與其他算法的求解效果。選用了粒子群算法（PSO，Particle Swarm Optimization）[8-9]、遺傳算法（GA,Genetic Algorithms）[10]與 VNS算法進(jìn)行比較。VNS算法延用上一部分的參數(shù)設(shè)置；PSO算法取了20個(gè)粒子，進(jìn)行了200次的迭代；GA算法選取種群規(guī)模為100，最大遺傳代數(shù)為200，交叉采用線(xiàn)性重組，交叉概率為0.9，高斯變異，其它參數(shù)使用缺省值。利用上述3種算法，對(duì)第1節(jié)中的5個(gè)測(cè)試函數(shù)分別進(jìn)行了50次的實(shí)驗(yàn)，其中對(duì)前兩個(gè)函數(shù)，n分別取了2、5、10。首先對(duì)比了50次實(shí)驗(yàn)的平均最優(yōu)值、最小最優(yōu)值和以及到達(dá)全局最優(yōu)值的比率(簡(jiǎn)稱(chēng)為比率)，所有數(shù)據(jù)精確到萬(wàn)分位，具體結(jié)果如表3示。

由表3可以看出，VNS在全局收斂性上要好過(guò)PSO和GA，對(duì)5個(gè)函數(shù)來(lái)說(shuō)，VNS都能夠取到全局最優(yōu)解，而且取到全局最優(yōu)解的比率也遠(yuǎn)遠(yuǎn)高于其他兩種算法，特別是當(dāng)可行解空間維數(shù)較小時(shí)，幾乎每次都能夠到達(dá)全局最優(yōu)值。隨著可行解空間維數(shù)的增大，算法的收斂性會(huì)有所下降，但是依然要好過(guò)其他兩種算法。只是再算法的穩(wěn)定性上稍差，最優(yōu)解的平均值要比其他兩種算法高，不過(guò)在可以接受的范圍之內(nèi)。

對(duì)比了50次實(shí)驗(yàn)中所用的平均時(shí)間和達(dá)到最小最優(yōu)值的最小時(shí)間，具體結(jié)果如表4。

表2 VNS算法與純SQP算法的求解效果比較

表3 算法求解的最優(yōu)值比較

表4 算法耗時(shí)比較

由表4可以看出，VNS所用的時(shí)間要比PSO和GA多，特別是當(dāng)空間維數(shù)比較大時(shí)。這是因?yàn)樵赩NS過(guò)程中，需要大量運(yùn)算求目標(biāo)函數(shù)值，當(dāng)空間維數(shù)比較大時(shí)，求解目標(biāo)函數(shù)值需要的時(shí)間就比較多。但是，相對(duì)于VNS算法的收斂性，特別是在空間維數(shù)小時(shí)，所用時(shí)間依然在可承受的范圍內(nèi)。

3 結(jié)語(yǔ)

提出了一種結(jié)合SQP的VNS算法，用來(lái)解決大量非線(xiàn)性、不可微和多峰值復(fù)雜問(wèn)題的優(yōu)化。該算法能夠保持SQP局部尋優(yōu)能力強(qiáng)的優(yōu)點(diǎn)和VNS的全局收斂性。通過(guò)實(shí)驗(yàn)證明，該算法是一種有效的全局優(yōu)化方法，相比于其他啟發(fā)法具有更強(qiáng)的尋優(yōu)能力和更高的搜索精度。

[1] HANSEN P, MLADENOVIC′ N.Variable Neighborhood Search:Principles and Applications[J].European Journal of Operational Research, 2010, 36(03): 449–467.

[2] TOKSARI D, GUNER E.Solving the Unconstrained Optimization Problem by a Variable Neighborhood Search[J].Journal of Mathematical Analysis and Applications,2009, 32(08):1178-1187.

[3] MLADENOVIC′ N, DRAZIC M.General Variable Neighborhood Search for the Continuous Optimization[J].European Journal of Operational Research, 2009, 19(01):753-770.

[4] GARCIA C, PEREZ-BRITO D.Variable Neighborhood Search for the Linear Ordering Problem[J].Computers & Operations Research,2010, 33(03): 3549-3565.

[5] 王明興.連續(xù)禁忌搜索算法改進(jìn)及應(yīng)用研究[D].杭州：浙江大學(xué)，2009.

[6] 楊敬.禁忌搜索與SQP相結(jié)合的混合優(yōu)化算法研究[D].杭州：浙江大學(xué)，2009.

[7] 劉忠耀,彭重嘉,伍乃騏.基于禁忌搜索算法的生產(chǎn)調(diào)度[J].微計(jì)算機(jī)信息,2008,24(02):55-57.

[8] 劉小聰,劉洪武.基于粒子群算法的預(yù)編碼設(shè)計(jì)[J].通信技術(shù),2010,43(09):37-39.

[9] 池越,趙東明,夏克文,等.基于QPSO算法的信道分配方法[J].通信技術(shù),2009,42(02):204-207.

[10] 肖冬榮,楊磊.基于遺傳算法的關(guān)聯(lián)規(guī)則數(shù)據(jù)挖掘[J].通信技術(shù),2010,43(01):205-207.