嵌入局部一維搜索技術的混合粒子群優化算法

摘 要:通過將粒子群優化算法(PSO)與經典局部一維搜索技術相結合，提出一種嵌入局部一維搜索技術的混合粒子群優化算法(LLS-PSO)。該算法在基本粒子群優化算法中引入一維搜索技術，選取最優粒子進行局部一維搜索，增強了在最優點附近的局部搜索能力，以加快算法的收斂速度。對三個經典復雜優化問題進行數值實驗，并與基本PSO算法進行比較。實驗分析和結果表明，LLS-PSO具有更好的優化性能。

關鍵詞:粒子群算法; 一維搜索技術; 優化; 混合

中圖分類號:TP18; TP301.6文獻標志碼:A

文章編號:1001-3695(2009)09-3279-03

doi:10.3969/j.issn.1001-3695.2009.09.022

Hybrid particle swarm optimization based on local line search technique

LONG Wen， LIANG Xi-ming， DONG Shu-hua， YAN Gang

(College of Information Science Engineering， Central South University， Changsha 410083， China)

Abstract:This paper proposed a new hybrid particle swarm optimization algorithm based on co-line search technique by integrating local line search technique and basic particle swarm optimization. In the LLS-PSO algorithm， it would introduce one dimension search technique based on elementary particle algorithm， select the best population for local search to speed up the convergence rate of the algorithm. The performance of the algorithm tested using three typical nonlinear optimization problem was reported and compared with that of basic PSO. Results show that performance of LLS-PSO algorithm is much better than basic PSO.

Key words:particle swarm optimization; line search technique; optimization; hybrid

粒子群優化算法(PSO)是由Kennedy等人[1] 于1995年提出的一種模擬鳥類捕食行為的全局優化算法。其主要優點是算法不依賴于問題的信息、通用性強;前期收斂速度快、設置參數少、算法簡單、容易實現;群體搜索并具有記憶能力，能夠保留局部個體和全局種群的最優信息，還可利用個體和群體信息指導算法的下一步搜索，能夠有效地解決復雜優化問題。在函數優化、模式識別、機器人學習、組合優化以及一些工程領域都得到了廣泛的應用[2~4]。

在科學研究和工程實踐中，許多實際問題最終都可歸結為求解函數的優化問題。然而目前已有的數值方法均基于局部搜索技術[5，6]，能在較少次數迭代后快速收斂到問題的局部最優解，但當問題存在多個局部最優解時，這類方法很難獲得其全局解;基于進化機制的全局優化算法[7，8]，能收斂到問題的全局解，但是存在收斂速度慢、解精度不高的缺點。目前一些改進的混合算法研究得比較多，都是利用兩種或多種算法的優點結合來提高算法的性能。局部一維搜索算法往往只需很少的迭代次數，具有局部搜索能力強和收斂速度快的優點，能保證迭代后的適應度值比迭代前的適應度值好。因此，合理融合局部搜索技術和進化機制的全局混合優化算法成為解決復雜優化問題的有效方法。鑒于目前對協同局部一維搜索的混合優化技術研究得較少，本文將局部一維搜索技術與標準粒子群算法結合起來，提出一種嵌入局部一維搜索技術的混合粒子群優化算法。

1 混合粒子群優化算法

1.1 標準粒子群優化算法

假設用Xi=(xi1，xi2，…，xiD)T表示第i個粒子。其中D是粒子的維數。經歷的最好位置表示為Pi=(pi1，pi2，…，piD)T，而整個群體經歷的最好位置表示為Pg=(pg1，pg2，…，pgD)T，粒子i的速度為Vi=(vi1，vi2，…，viD)T。按追隨當前最優粒子的原理，粒子i將按式(1)和(2)改變速度和位置，即

vn+1id=wvnid+c1rand()(pnid-xnid)+c2rand()(pngd-xngd)(1)

xn+1id=xnid+vn+1id(2)

其中:n為當前的進化代數;c1、c2為學習因子;rand()為分布于(0，1)的隨機數;w為慣性權重。研究表明，較大的w值有利于跳出局部極值點;較小的w值有利于算法的收斂和提高解的精度，慣性權重w起到平衡全局搜索和局部搜索能力的作用。

標準粒子群優化算法的流程如下:

a)隨機初始化粒子的位置和速度。

b)計算粒子的適應度值，將粒子的pi設置為當前位置;pg設置為初始群體的最佳粒子的位置。

c)對所有粒子按式(1)(2)更新位置和速度，并計算粒子的適應度值。

d)判斷算法停止準則是否滿足，如果滿足，則結束;否則，轉向b)。

1.2 局部一維搜索算法

一維搜索是從某個點出發，沿某個方向尋找函數最優點的方法，它是加快最優化方法收斂的一個基本和有效的技術。若在點x處沿適當的方向進行一維搜索，可得出比x更好的點。本文利用基于Wolfe-Powell不精確一維搜索產生步長的算法來加快算法的收斂。無約束優化問題可表示為min f(x)，x∈Rn。求解上述問題的一維搜索算法可表示如下:

a)選取初始點xk∈Rn，令k=1。

b)計算f(xk)，若f(xk)=0，則停止;否則，確定搜索方向dk，使得f(xk)Tdk<0，計算步長因子λk>0滿足搜索準則。

c)令xk+1=xk+λkdk，k=k+1，轉b)。

步驟b)中的步長因子λk要滿足由Wolfe等人提出的不精確一維搜索準則，即Wolfe-Powell準則[9]:

(λk)≤(0)+ρλkgTkdk(3)

|gTk+1dk|≤-σgTkdk(4)

其中:0<ρ<0.5，gk=f(xk)，dk是搜索方向，λk是步長因子，σ∈(ρ，1)。結合式(3)和(4)即是著名的Wolfe-Powell準則，它具有良好的收斂性質和不錯的數值表現，能夠保證目標函數在每一步迭代以后產生一充分的下降，所以在許多數值計算和工程中被廣泛應用。

1.3 嵌入局部一維搜索的混合粒子群優化算法

1.3.1 算法思路

粒子群優化算法具有較強的全局搜索能力，但其局部搜索能力較弱。由于粒子初始化和演化過程的隨機性，并不能完全保證迭代后的下一代粒子的適應度值一定比迭代前的上代粒子好。也就是說，粒子不一定沿著最優的方向進行迭代，從而影響了算法的收斂性能。局部一維搜索算法是一種以梯度信息確定搜索方向的算法，它能夠保證每次迭代以后的目標函數值都有充分的下降，向著目標函數值下降的方向進行迭代，因此一般只需較少次數的迭代過程即可獲得問題的局部最優解。

基于以上的分析，本文充分利用兩種搜索算法的優點，在粒子群算法中合理融入局部一維搜索算法來改善其性能。其思路是:在每一次粒子群算法迭代以后，每個粒子都有對應的適應度值，將所有粒子的適應度值進行排序，將粒子按照適應度值的優劣分為精英粒子和普通粒子，數量分別為n1和n2且n1+n2=n，即適應度值最好的n1個粒子為精英粒子，其余的粒子則為普通粒子。兩類粒子采取不同的進化方式，即每輪迭代中，精英粒子采用局部一維搜索，在這里不采取隨機選擇粒子進行局部一維搜索，因為隨機選取粒子的方法有時無法提高整體性能并且可能白白耗費運行時間，使得要花費很長時間才能收斂到最優點。對各個精英粒子直接進行一次以其梯度信息確定搜索方向的Wolfe-Powell一維搜索，搜索以后得到的后代粒子，保證其適應度值比上一代更優。如果一維搜索后粒子的適應度值優化不明顯，則不必要進行一維搜索，否則可能計算量增大，而算法性能又得不到改善。沒有參與一維Wolfe-Powell搜索的其他粒子則進行一次基本粒子群算法迭代，能夠很好地保持粒子群優化算法的優點。隨著迭代的進行，兩類粒子之間相互轉換，共同演化，增強混合算法的優化性能。

1.3.2 算法流程

a)初始化參數，隨機產生初始粒子。

b)計算所有粒子的適應度值并排序，并更新粒子的位置和速度。

c)按適應度值選取最優的n1個粒子組成精英粒子，剩下的n2個粒子組成普通粒子。

d)對精英粒子直接進行一維Wolfe-Powell搜索;而對普通粒子進行基本粒子群迭代。

e)合并子群體并更新粒子的位置和速度。

f)判斷算法是否結束，若是，輸出最優解;否則，轉向b)。

2 仿真實驗與分析

下面采用三個典型測試函數來評價所提出的嵌入局部一維搜索技術混合粒子群優化算法(LLS-PSO)的性能，并與標準粒子群算法(SPSO)的測試結果進行比較。

為了進一步比較算法的性能和減少偶然性的影響，對每個函數隨機進行30次實驗，對于LLS-PSO算法，c1=c2=1.696 4，w=0.729 6， 最大迭代次數maxDT=200， 而對于標準PSO算法，一些參數的設置如下:c1=c2=2，w=0.634 8，maxDT=200。在計算中，對每個函數取不同維數且不同個體數目的種群進行測試，n分別取為20和40，維數D分別取10和20。

a)Spherical函數。f1(x)=∑Di=1x2i，-100≤xi≤100，是單峰二次函數，它在xi=0時達到最小值0。

對Spherical函數的計算結果如表1所示。在相同維數和個體數目的條件下，與標準粒子群算法相比，LLS-PSO算法的尋優結果最接近最優值，算法迭代花費的時間較短。在維數為20時，SPSO算法的尋優結果誤差較大。SPSO算法和LLS-PSO算法的收斂軌跡曲線如圖1所示(測試條件:粒子數為40，維數為20，以下的測試條件相同)。由圖1可以看出，LLS-PSO算法對Spherical函數測試所得的最優值已非常接近理論最小值，引入局部一維搜索技術能夠使算法快速收斂，LLS-PSO算法的收斂性能明顯優于SPSO算法。

表1 Spherical函數的尋優結果

算法維數種群規模平均最優值平均迭代次數時間/s

LLSPSO102020400.000 006 240.000 014 6346520.2380.402

SPSO102020400.000 060 860.001 544 581041230.2660.432

b)Rosenbrock函數。f2(x)=∑Di=1[100(xi+1-x2i)2+(xi-1)2]，-30≤xi≤30。函數在xi=1時取到全局最小值0，是個很難極小化的病態二次函數，其極小點所在的山谷易于找到，但要收斂到全局極小點則十分困難，計算中一些參數的設置同Spherical函數。

表2的計算結果表明，在相同的迭代次數和搜索范圍下，LLS-PSO算法的優化性能強于SPSO算法，而且其搜索精度也有顯著提高。圖2是兩種算法對Rosenbrock函數尋優的收斂曲線。從圖2中可以得知，嵌入局部一維搜索技術的LLS-PSO算法的平均收斂代數與SPSO算法相比有大幅減少，算法的收斂速度加快，同時收斂精度也有很大的提高。

表2Rosenbrock函數的尋優結果

算法維數種群規模平均最優值平均迭代次數時間/s

LLSPSO102020401.859 676 943.433 522 19941060.2290.417

SPSO102020408.765 716 1719.983 948 01101220.2370.436

c)Rastrigin函數。f3(x)=∑Di=1[x2i-10cos(2πxi)+10]，-5.12≤xi≤5.12，有很多正弦凸起的局部極小點，在xi=0處取得全局最小值0。

表3和圖3分別是LLS-PSOS算法和PSO算法對Rastrigin函數的尋優計算結果和尋優曲線。尋優過程中的參數設置同上述兩個函數。從表3可以看出，在給定最大代數的前提下，LLS-PSO算法求得的平均最優值優于SPSO算法得到的最優值，無論是搜索速度還是搜索精度都比SPSO要優。因此，LLS-PSO較SPSO更有較強的尋優能力和較高的搜索精度。從圖3的尋優曲線可以得知，由于在算法中加入了局部一維搜索，使粒子在尋優的過程中始終沿著最優的方向進行迭代，加快了算法的收斂速度和收斂到較精確的值。

表3 Rastrigin函數的尋優計算結果

算法維數種群規模平均最優值平均迭代次數時間/s

LLSPSO102020400.000 046 280.000 938 8968750.2500.440

SPSO102020400.003 705 360.026 674 171241720.2580.445

SPSO是基于隨機初始化的種群進行迭代求解，并使用適應度值來評價個體進行搜索，且都不能保證一定找到全局最優值(有些復雜問題求最優值的近似值)，尤其對于大規模的復雜問題，很容易陷入局部極值點。LLS-PSO算法的優勢源于算法的混合，在標準PSO的基礎上引入局部一維搜索技術。局部一維搜索算法是基于梯度信息確定搜索方向的，所以它的搜索方向不是隨機的，而是按照一個確定的方向進行搜索，能保證在每次迭代后的目標函數值都有充分的下降，也就是沿著最優方向進行迭代，改善了算法的隨機性，有助于提高算法尋優的效率和精度。實驗的結果也很好地體現了這一點。

3 結束語

本文在粒子群優化算法中結合局部一維搜索技術，將粒子分為精英粒子和普通粒子，分別執行不同的進化策略，協同優化，構建一種高效易實現的嵌入局部一維搜索技術的混合粒子群算法。對三個經典高維復雜函數進行仿真實驗，優化結果表明，與標準PSO相比，LLS-PSO算法具有較強的全局尋優能力，尋優效率高。

參考文獻:

[1]KENNEDY J， EBERHART R C. Particle swarm optimization[C]//Proc of IEEE International Conference on Neural Networks. Piscata-way: IEEE Press， 1995: 1942-1948.

[2]SHI Y， EBERHART R C. Empirical study of particle swarm optimization [C]//Proc of Congress on Evolutionary Computation. Piscata-way， NJ: IEEE Service Center， 1999:1945-1950.

[3]XIE X F， ZHANG W J， YANG Z L. A dissipative particle swam optimization[C]//Proc of IEEE International Conference on Evolutio-nary Computation. Honolulu: IEEE Inc，2002: 1456-1461.

[4]VAN B F， ENGEJBRECHT A. Using neighborhood with the guaranteed convergence PSO [C]//Proc of IEEE Swarm Intelligence Symposium. 2003: 235-242.

[5]LI D， FUKUSHIMA M. A derivative free line search and DFP method for symmetric equation with global and super-linear convergence[J]. Numerical Function Analysis and Optimization， 1999，20(1): 59-77.

[6]ARIYAWAMSA K A. Line search termination criteria for collinear scaling algorithm for minimizing a class of convex function[J]. Numerische Mathematic， 1998，80: 363-376.

[7]FAN S K S， LIANG Y C， ZAHARA E. Hybrid simplex search and particle swarm optimization for the global optimization of multimodal functions[J]. Engineering Optimization， 2004， 36(4):401-418.

[8]PARSOPOULOS K E， VRAHATIS M N. Initializing the particle swarm optimizer using the nonlinear simplex method [C]//Advances in Intelligent Systems， Fuzzy Systems， Evolutionary Computation. [S.l.]: WSEAS Press， 2002:216-221.

[9]POTRA F A， SHI Y. Efficient line search algorithm for unconstrained optimization[J]. Journal Optimization and Applications， 1995，85(3): 677-704.