一種新型的變領域搜索算法

于繼江

(菏澤學院 計算機與信息工程系，山東 菏澤 274015)

0 引言

變鄰域搜索算法（VNS, Variable Neighborhood Search）是一種求解優化問題的啟發式算法，是有 Hansen 和Mladenovic′首次提出。它的基本思想在搜索過程中系統地改變鄰域結構集來拓展搜索范圍，獲得局部最優解，再基于此局部最優解重新系統地改變鄰域結構集拓展搜索范圍找到另一個局部最優解的過程。由于VNS在簡易性、時效性、人性化和創新性等方面表現突出，若干改進算法已應用于NP難問題的求解中[1-4]。

VNS提出后被應用于很多組合優化問題的求解，許多應用實例也表明了VNS對解決組合優化問題的優越性能[5-7]。對于組合優化問題，一個鄰域內的可行解是有限的，因此在局部搜索過程中，是可以計算出鄰域內的所有可行解的目標函數值，進而找到鄰域內的最優解，即局部最優解。區別于組合優化問題，連續優化問題中的可行解空間是連續的，因此無法找到鄰域內所有可行解，也就無法找到局部最優解。

針對上述問題，提出了一種結合序列二次規劃法(SQP,Sequential Quadratic Programming)的變鄰域搜索方法，并將其應用到無約束連續優化問題中。

1 結合SQP的變鄰域搜索算法

SQP是當前公認的處理中、小規模非線性規劃問題最優秀的算法之一，它具有良好的局部收斂性和較強的超線性收斂速度。它能快速精確地獲取當前點附近的局部極小點。為了較好處理VNS中的局部搜索過程，更快速、更精確得到局部最優解，將SQP結合到VNS中，即應用SQP求解局部搜索過程中的局部最優解。這樣既保持了SQP在求解局部最優解上的優勢，又突出了VNS全局收斂性的特點。

對于一個問題 P，設初始解為 x，鄰域結構 Nk(x),k=1,2,…,kmax，設定參數的初始值，kmax,tmax,kstep，其中kmax為最大鄰域，tmax為最大計算時間，kstep是每次迭代的鄰域步數。

結合SQP的VNS算法流程如下：

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

在VNS的應用中，為了加快算法的運行速度、提高算法的搜索精度，可以采用以下策略改進算法。

（1）初始點策略

在VNS中初始點的選取，對最后得到的最優解和運算時間、迭代步數有直接的影響，若初始點選取的好，能夠盡可能的靠近全局最優解，得到全局最優解所需要的時間以及迭代步數就會減少。在初始點選取中，可以采用多點選擇，取目標函數值最小的一個點作為初始值。

（2）多樣性策略

在VNS中一般包含3個部分：隨機擾動、局部搜索、鄰域變換。當通過局部搜索過程，找到一個局部最優解時，利用隨機擾動的方法，在距離局部最優解一定距離的地方，選取一個可行解作為新的局部搜索的起始點。這樣就能夠從局部最優解的“山谷”中脫離出來，從而找到全局最優點。

一般VNS中，每次的隨機擾動都只是選擇k鄰域中的一點。當鄰域比較大時，鄰域內的可行解數量就會比較多，由于擾動的隨機性，只隨機選取一點，有可能就會漏掉全局最優解。因此，可以采用多樣性（Diversification）策略，選取鄰域內的多個點作為起始點，對每個點進行局部搜索，選取其中最優的局部最優解與現有最優解比較。這樣可以盡可能的搜索整個區域，以達到尋找全局最優解的目的。

對于一個問題 P，設初始解為x，鄰域結構Nk(x),k=1,2,…,kmax，設定參數的初始值，kmax,tmax,kstep，其中kmax為最大鄰域，tmax為最大計算時間，kstep是每次迭代的鄰域步數。

改進的VNS算法流程如下：

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

2 數值實驗

實驗所用的計算機配置Core2 Duo CPU，主頻2.17 GHz，2 GB內存，操作系統為 windows7，使用的編程軟件是MATLAB2009.優化算法的比較通常是基于一些標準函數的典型問題展開的通過5個標準函數(見表1示)測試算法的性能。這些函數具有多峰、非凸等特點,經常被國外學者用于對優化問題的測試。

表1 5個標準的測試函數

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

從表2可以看出，VNS算法具有很好的全局收斂性，最優解和目標函數值都能夠精確到 1e-8以上，尋優的精確性都遠好于單純的SQP算法。特別對于測試函數Shubert，使用 VNS算法，很容易找到了全部 18個最優解，分別是：(-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算法進行比較。VNS算法延用上一部分的參數設置；PSO算法取了20個粒子，進行了200次的迭代；GA算法選取種群規模為100，最大遺傳代數為200，交叉采用線性重組，交叉概率為0.9，高斯變異，其它參數使用缺省值。利用上述3種算法，對第1節中的5個測試函數分別進行了50次的實驗，其中對前兩個函數，n分別取了2、5、10。首先對比了50次實驗的平均最優值、最小最優值和以及到達全局最優值的比率(簡稱為比率)，所有數據精確到萬分位，具體結果如表3示。

由表3可以看出，VNS在全局收斂性上要好過PSO和GA，對5個函數來說，VNS都能夠取到全局最優解，而且取到全局最優解的比率也遠遠高于其他兩種算法，特別是當可行解空間維數較小時，幾乎每次都能夠到達全局最優值。隨著可行解空間維數的增大，算法的收斂性會有所下降，但是依然要好過其他兩種算法。只是再算法的穩定性上稍差，最優解的平均值要比其他兩種算法高，不過在可以接受的范圍之內。

對比了50次實驗中所用的平均時間和達到最小最優值的最小時間，具體結果如表4。

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

表3 算法求解的最優值比較

表4 算法耗時比較

由表4可以看出，VNS所用的時間要比PSO和GA多，特別是當空間維數比較大時。這是因為在VNS過程中，需要大量運算求目標函數值，當空間維數比較大時，求解目標函數值需要的時間就比較多。但是，相對于VNS算法的收斂性，特別是在空間維數小時，所用時間依然在可承受的范圍內。

3 結語

提出了一種結合SQP的VNS算法，用來解決大量非線性、不可微和多峰值復雜問題的優化。該算法能夠保持SQP局部尋優能力強的優點和VNS的全局收斂性。通過實驗證明，該算法是一種有效的全局優化方法，相比于其他啟發法具有更強的尋優能力和更高的搜索精度。

[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] 王明興.連續禁忌搜索算法改進及應用研究[D].杭州：浙江大學，2009.

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

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

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

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

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