多種群隨機差分粒子群優化算法及其應用

王皓， 高立群， 歐陽海濱

(東北大學 信息科學與工程學院，遼寧 沈陽 110819)

?

多種群隨機差分粒子群優化算法及其應用

王皓， 高立群， 歐陽海濱

(東北大學 信息科學與工程學院，遼寧 沈陽 110819)

為提高粒子群算法的尋優性能，提出了一種新的多種群隨機差分粒子群優化算法。該方法將種群隨機分組，利用基于吸引概率的輪盤賭方法確定其可能搜索方向。尋優效果預期不明顯時，進行子種群內部隨機差分進化尋優，以增加尋優方向的隨機性和多樣性。并給出了一種新的約束處理方法，對種群粒子進行動態劃分，僅對部分粒子進行速度更新和位置更新，提高了搜索速度。并將所提出算法應用于數值優化問題和焊接梁設計問題。仿真結果表明，所提出算法在處理多峰函數問題時，尋優精度高，收斂速度快。在處理有約束問題時，提出的處理約束的方法，明顯縮短了尋優時間。算法在處理復雜的無約束問題和有約束問題上均具有很好地尋優性能。

粒子群優化算法；多峰問題；約束優化；輪盤賭方法；差分進化；速度更新；位置更新；搜索速度；數值優化；焊接梁設計

粒子群優化算法(particle swarm optimization,PSO)是Kennedy和Eberhart于1995年提出的一種模擬鳥群社會行為的群體搜索算法。該算法簡潔明了，具有良好的尋優性能，至今已廣泛應用于科學、工程等許多領域。

隨著對PSO算法及應用的不斷深入研究，發現該算法和其他智能優化算法一樣也存在著容易陷入局部最優問題。為提高其尋優性能，PSO算法不斷改進，主要圍繞三個方面：1)增加控制參數，通過引入慣性權重因子[1]、收縮因子[2]、被動聚集項[3]來防止粒子陷入局部最優；通過引入時變加速因子[4]來提高算法的效率和收斂速度。2)引入多種群協作[5]和動態種群概念[6]，通過多種群協作和種群的動態調整來提高算法的尋優能力。3)尋找有效的尋優策略，其研究主要集中在兩條途徑，一是引入隨機進化[7-8]，二是對尋優策略進行自適應調整。至今PSO算法已得到深入研究，但陷入局部最優的問題仍然沒能完全解決，還有進一步改進的空間。

鑒于工程實際中的優化問題往往需要滿足各種要求和約束，如何處理約束也是優化研究的一個重要方向。不過由于利用罰函數法可以將約束問題轉化為無約束問題，使得人們的研究更多地集中于無約束問題。后來發現，將無約束優化算法直接應用于約束問題時，尋優效果往往并不十分理想。為此，近年來人們提出了一些針對復雜約束的優化算法[9-10，15-20]，仿真結果表明這些算法對于很多復雜約束問題的尋優效果相當突出，得到了廣泛認可。但是進一步研究可以發現，這些算法往往不能很好地解決多極值點的約束優化問題。因此，尋找一個能夠很好地處理帶有復雜約束的多極值點問題的算法具有一定理論意義和實際需求。

本文將多種群并行尋優與隨機進化思想相結合，提出一種基于種群隨機分組和隨機差分策略的改進粒子群優化算法，同時給出了一種新的約束處理方法，并將該算法應用于焊接梁設計問題。

1 粒子群優化算法

一個由M粒子組成的群體在D維搜索空間中以一定的速度飛行，每個粒子在搜索時，根據自己搜索到的歷史最好點和群體內其他粒子的歷史最好點進行位置的變化。粒子的位置和速度更新公式：

xij(t+1)=xij(t)+vij(t+1)

(1)

c2r2j(t)[xbj(t)-xij(t)]，

i=1，2，…，M;j=1，2，…，D

(2)

2 多種群隨機差分粒子群算法

人們在PSO算法研究中發現，通過兩種途徑可以克服算法陷入局部最優。一種途徑是引入多種群協作[5]和動態種群概念[6]，可以使得粒子在尋優中不是單一以全局最好粒子作為尋優引導方向，而以一定概率分別向多個方向引導。尋優方向的多樣性增加了尋優路徑的多樣性。另一種途徑是不以某一個或幾個確定的方向來引導粒子尋優，而是以一定概率在某些較好方向進行隨機引導，增加了尋優路徑的隨機性，文獻[11]提出了一種基于動態拓撲的粒子群算法。在算法前期，采用概率選擇機制弱化全局最優粒子的影響力，以增強解的多樣性，而在算法后期，強化全局最優粒子的影響力，最終能夠收斂到一個最優解。本文將上述兩種改進思想加以融合提出一種多種群隨機差分粒子群算法，簡記為MPPSO算法。

2.1 MPPSO算法的基本步驟

1) 初始化。

根據實際確定問題維數D，算法中的學習因子c1、c2，最大迭代次數N，子種群個數K及每一子種群內粒子個數。為簡單起見，可取子種群中粒子個數均為m，則粒子總數為M=m×K。隨機產生m×K個初始粒子xij(0)，i=1，2，…，m，j=1，2，…，K。計算粒子適應度值，針對每個粒子計算出相應的適應度函數值f(xij(0))。

2) 計算吸引概率。

在每組中基于目標函數值找出組內最優值和最優粒子以及全局目標函數最大值fmax。計算每個粒子受到各個小組最優粒子的吸引概率：

(3)

3) 產生新的粒子。

①對于每個粒子，基于受到各個小組最優粒子的吸引的概率pij(t)，利用輪盤賭的方法確定其可能搜索方向j，即可能向第j組的最優粒子方向搜索。

②b為變異參數，取隨機數b=rand(0，1)，基于選擇的搜索方向j，利用式(4)～(6)產生新的粒子的第s維分量。

(4)

(5)

s=1，2，…，D

式中：r1=rand(0，1)，r2=rand(-0.5，0.5)，c1、c2為學習因子，xrj為任意一個不等于xij的粒子。

(6)

4) 判斷運算是否到達指定的最大迭代次數N，如果沒有達到，則轉向步驟2)；

5) 輸出結果，程序結束。

2.2 MPPSO算法中的改進和特點

MPPSO算法對現有粒子群算法進行了改進，其改進和特點主要表現在以下幾方面：

1)通過分組和吸引概率的引入增加粒子的尋優搜索方向。由于引導方向的多樣性，可以增加粒子跳出局部最優的可能性，有利于解決多極值點問題。

3)在式(5)中，取參數r2=rand(-0.5，0.5)，使得迭代尋優中進行一定的反向搜索，有助于提高尋優效率。

4)尋優中根據貪婪原則確定新的粒子，可以保證算法的收斂性。

3 約束處理

實際優化問題通常情況下都含有約束，問題越復雜，約束就越多。一般約束優化問題的數學模型可表示為

minf(x)

s.t.gj(x)≤0j=1，2，…，ng

(7)

式中：f(x)表示目標函數，gj(x)表示第j個約束條件，ng為約束條件的個數。

對約束優化問題的求解，目前有許多算法——如梯度映射法、梯度下降法、懲罰函數法、障礙函數法等，其中處理約束問題最簡單也是常見的方法是懲罰函數法，該方法通過懲罰策略將帶有約束優化問題轉化為無約束優化問題。

(8)

式中：λ為懲罰系數，本文中設置為1010。

在應用罰函數法處理約束問題時，在尋優的每一步通常都需要計算罰函數值，當約束較多、較復雜時，計算F(x)的時間要遠遠多于計算f(x)的時間，這大大增加了計算時間，降低了尋優效率。為解決這一問題，本文提出一種新的處理方法。此方法的特點是對種群進行動態劃分，只有當無約束目標函數值小于已有可行解中的最差值時才考慮約束的限制，從而不需在搜索的每一步都計算懲罰函數值，提高了尋優效率。

為方便起見，將式(8)改寫為

minF(x)=f+λf1

(9)

在第t+1代尋優中，首先計算f(x(t+1))的值，然后將其與上一代可行解中的最差值fworst(x*(t))=Fworst(x*(t))進行比較，如果f(x(t+1))≤Fworst(x*(t))，則計算懲罰函數值f1(x(t+1))，當f1(x(t+1))≤0時，取F(x(t+1))=f(x(t+1))，進入下一步尋優；當f1(x(t+1))>0時，取F(x(t+1))=f(x(t+1))+λf1(x(t+1))。如果f(x(t+1))>Fworst(x*t)，則直接進入下一代尋優。記Fg(t)=max{F(xi(t))|i=1，2，…，m×K}，針對約束問題，計算吸引概率的式(3)應改寫為

(10)

此方法只是對具有較好f值的解進行有關約束的計算，利用懲罰策略使其向可行解空間移動，而不是對每一個解都進行約束計算，因此可以大大提高尋優速度。

注意這里的較好f值的判斷是根據可行解中最差解所做出的，當然也可以根據其他準則給出判斷。判斷準則的好壞會直接影響尋優效果。比如：若采取基于可行解中最好解的準則，則限制過于苛刻，使得僅有極少數粒子參與更新(尋優)，會嚴重影響尋優效果；若采取基于所有解中最差解的準則，則限制過于寬松，不能明顯地縮短尋優時間。

上述處理方法的具體實現步驟如下：

1)算法初始化。令循環變量t=1，隨機產生若干個初始解向量，對采用的相關啟發式優化算法進行參數設置；根據式(9)計算無約束目標函數值f(x(t))和懲罰函數值f1(x(t))。當f1(x(t))=0時，所對應的解為可行解，保存可行解中的目標函數最優值fbest(x*(t))及對應的最優可行解x*(t)。保存可行解中的目標函數最差值fworst(x*(t))=Fworst(x*(t))，若沒有可行解，則重新初始化，直至找到可行解。

2)根據式(10)計算吸引概率。

3)根據式(4)、(5) 對粒子進行速度更新和位置更新。

(11)

(12)

并保存F(x(t+1))，Fbest(x*(t+1))和Fworst(x*(t+1))。

6)判斷迭代次數是否達到預先設置的最大迭

代次數，如果達到，則輸出最優解，停止迭代；否則重復步驟2)～5)。

4 數值仿真實驗

4.1 無約束優化

現行各類算法對于單峰函數的尋優效果相差不多，都比較好，而且本文算法主要是解決多峰函數優化問題，因此實驗中選取了參考文獻[12]所列舉的多峰函數及文獻[13]的Enhanced Bat Algorithm作為測試函數，具體如表1所示。對算法MPPSO進行測試比較主要基于以下幾個性能指標：算法參數的影響、優化精度即最終解的質量和收斂速度。

算法參數設置：種群規模20，每組粒子5，共4組，學習因子c1=c2=1.7，維度D=30，算法獨立運行30次。各類算法的迭代次數均為50 000次。

4.1.1 算法參數的影響

在式(5)中引入變異參數b。當參數b取不同值時的測試結果如表2所示。由表2可知當b=rand(0，1)時，既增加了尋優方向的隨機性和多樣性，又很好的解決了陷入局部最優的問題。圖1給出6個函數在不同變異參數b下的優化曲線。

表1 無約束測試函數

表2 測試結果比較

圖1 6個函數的收斂曲線(MPPSO)Fig.1 Convergence curves of 6 functions(MPPSO)

函數GPSOFIPSHPSO-TVACCLPSOAPSOEBAMPPSOf1Mean-9845.27-10113.80-10868.57-12557.65-12569.5-6.98×103-12569.50S.D588.87889.5828936.205.22×10-119.61×1020f2Mean69.0629.982.392.57×10-115.80×10-153.44×1010S.D8.0710.923.716.64×10-111.01×10-141.28×1010f3Mean21.3335.911.830.174.14×10-16-0S.D9.469.492.650.381.45×10-15-0f4Mean1.40×10-147.69×10-152.06×10-102.01×10-121.11×10-144.58×10-14.44×10-15S.D3.48×10-159.33×10-169.45×10-109.22×10-133.55×10-155.78×10-11.95×10-15f5Mean1.31×10-29.04×10-41.07×10-26.45×10-131.67×10-27.30×10-30S.D1.35×10-22.78×10-31.14×10-22.07×10-122.41×10-29.46×10-30f6Mean3.46×10-31.22×10-317.07×10-301.59×10-213.76×10-319.99×10-10S.D1.89×10-24.85×10-324.05×10-301.93×10-211.20×10-301.840

4.1.2 優化精度比較

在本小節中，利用表1所列舉的6個測試函數測試算法的尋優能力即最終解的質量，與文獻[12-13]所列各種近期典型算法優化測試比較結果如表3所示。

從表3的結果可以看出，本文算法對于無約束多峰函數f1～f6都具有很好的尋優效果。其原因是通過分組和吸引概率的引入增加粒子的尋優搜索方向。由于引導方向的多樣性，可以增加粒子跳出局部最優的可能性。式(5)中引入變異參數b，取隨機數b=rand(0，1)，既增加了尋優方向的隨機性和多樣性，又很好的解決了陷入局部最優的問題。因此在解決多峰函數問題時具有較好的效果。

4.1.3 收斂速度

圖2顯示出MPPSO算法在迭代過程中具有穩定的收斂率并且能夠快速尋找到最優值。MPPSO算法函數f1、f4、f5、f6中具有較好的收斂率，在函數f2、f3中雖然收斂不是最快，但是尋優效果好。

4.2有約束優化

參數設置：種群規模100，每組粒子25，共4組，學習因子c1=c2=1.7，最大迭代次數50 000，維度D=30，算法獨立運行30次。為測試本文提出的算法的有效性，本文采用了兩類測試函數。一類來自于文獻[14]中的測試函數，這類函數的特點在于所具有的約束比較復雜，使得通常對無約束問題有著很好尋優效果的算法，對于這類約束問題往往尋優效果可能并不理想，因此文獻[14]給出了適用于復雜約束問題的算法。另一類是對于前面的無約束多峰函數分別加上一定約束所構造的測試函數，其特點在于目標函數多峰，使得目前處理約束問題較好的算法在尋優中效果可能會收到影響。由于篇幅所限，在兩類函數中下面僅列出對比效果比較明顯的9個測試函數，其中g01、g02、g04、g06、g08和g12來自文獻[14]；h01、h02、h03是本文在無約束多峰測試函數基礎上增添約束所構造的，其構造目的在于檢驗算法對帶有約束的多峰測試效果。自定義的測試函數具體形式如表4所示。

與目前人們認為處理約束問題較好的算法FSA[15]、MicroPSO[16]、CW[17]、CMODE[18]、MHS[19]進行比較，這些算法的參數都根據算法發表的文獻進行設置，針對約束分別采用常規罰函數法和本文提出的處理方法，所用時間對比見表5，由表5可知本文提出的處理約束的方法能夠明顯縮短尋優時間。

從表6的結果可以看出，本文提出的改進算法對函數g01、g02、g04、g06、g08、g12、h01、h02、h03都有很好的尋優效果，都能找到最優值，明顯優于FSA、MicroPSO、CW、CMODE、MHS算法。其中CMOD算法尋優性能也比較好，對函數g01、g04、g06、g08、g12上也可以找到最優值，但是對于函數g02、h02、h03的尋優上效果不佳。

5 在焊接梁設計問題中的應用

為進一步驗證本文算法的有效性，下面將本文算法應用于焊接梁設計問題。參數設置：種群規模100，每組粒子25，共4組，學習因子c1=c2=1.7，最大迭代次數20 000次。

焊接梁設計問題是指在受剪應力、彎曲應力、屈曲載荷、結尾偏差和側面限制約束的限制下找到最低的制造成本[20]。數學模型如文獻[20]所示。

圖2 收斂曲線Fig.2 Convergence curves

問題測試函數維數h01minf(x)=-∑ni=0xisin(xis.t.g1(x)=2x1+2x2+x10+x11-10≤0,g2(x)=2x1+2x3+x10+x12-10≤0,g3(x)=2x2+2x3+x11+x12-10≤0;g4(x)=-8x1+x10≤0,g5(x)=-8x2+x11≤0,g6(x)=-8x3+x12≤0,g7(x)=-2x4-x5+x10≤0,g8(x)=-2x6-x7+x11≤0,g9(x)=-2x8-x9+x12≤0,g10(x)=∑ni=0x2i-n≤0,-500≤xi≤500(i=1,2,…,13)ì?í??????????13h02minf(x)=14000∑ni=1xi2-∏ni=1cosxii?è???÷+1s.t.g1(x)=∑ni=1xi+∏ni=1xi-100≤0-600≤xi≤600,i=1,2,…,20ì?í????20h03minf(x)=πn{10sin2π+π4(x1-1)()+∑n-1i=118(xi-1)21+10sin2π+π4(xi+1-1)()[]+18(xn-1)2}+∑ni=1u(xi,10,100,4)u(xi,a,k,m)=k(xi-a)m, xi>a,0, -a≤xi≤a,k(-xi-a)m, xi<-a.{s.t. g1(x)=127-2x12-3x24-x3-4x42-5x5≥0,g2(x)=282-7x1-3x2-10x32-x4+x5≥0,g3(x)=196-23x1-x22-6x62+8x7≥0,g4(x)=-4x12-x22+3x1x2-2x32-5x6+11x7≥0,-10≤xi≤10, i=1,2,…,7ì?í??????????????7

表5 尋優時間對比結果

表6 實驗結果

在Zou[20]文章中提出最優解f(x*)=1.695 266 99，表7為Zou[20]和其他研究者與本算法解決此問題的近似最優解比較。從表7中可看出，本文得出的近似最優解f(x*)=1.593 181 44，明顯優于其他所有算法的近似最優解，同時表明文獻[20]中所給出的解并不是最好解。

為了驗證本文的處理約束方法可以提高尋優速度，并可以引入到粒子群以外的其他算法，下面針對典型的和聲算法(HS)、差分進化算法(DE)和本文算法進行尋優時間對比實驗。實驗中，基于焊接梁設計問題，針對約束分別采用常規罰函數法和本文處理方法所用時間見表8。

從表8可以看出，采用本文方法相對于常規罰函數法3種算法尋優時間分別縮短了42.36%、28.72%、13.16%，這表明將本文約束處理方法引入到其他智能優化算法能夠明顯縮短尋優時間。

表7 焊接梁設計最優解表

表8 尋優時間對比結果

6 結論

針對粒子群算法收斂精度不高，容易陷入局部最優的缺點，本文提出一種新的多種群隨機差分粒子群算法，通過分組和吸引概率的引入，增加了粒子的尋優搜索方向，提高了跳出局部最優的可能性。

1)在速度更新公式中引入具有指導決策功能的變異參數b，對種群的搜索進行有效的指導，有助于解決陷入局部最優問題。

2)在該算法的基礎上還給出了一種處理約束的新方法，該方法可以減少計算量，縮短尋優時間。

3)分別對無約束和帶約束問題進行了仿真實驗，實驗結果顯示本文算法在處理各類多峰問題時效果明顯，優化精度高，收斂速度快。

4)將本文算法應用于焊接梁設計問題，仿真結果也表明其優化效果明顯好于現有文獻中的已有結果，并且縮短了尋優時間。

[1]NICKABADI A， EBADZADEH M M， SAFABAKHSH R. A novel particle swarm optimization algorithm with adaptive inertia weight[J]. Applied soft computing， 2011， 11(4): 3658-3670.

[2]ANWAR A， MAHMOOD A N. Enhanced estimation of Autoregressive wind power prediction model using constriction factor particle swarm optimization[C]// Industrial Electronics and Applications. [S.l.]， 2014: 1136-1140.

[3]ZHAO X. An enhanced particle swarm optimization algorithm with passive congregation[C]//2010 International Conference on Machine Vision and Human-machine Interface. [S.l.]， 2010: 432-435.

[4]CHIH M， LIN C J， CHERN M S， et al. Particle swarm optimization with time-varying acceleration coefficients for the multidimensional knapsack problem[J]. Applied mathematical modelling， 2014， 38(4): 1338-1350.

[5]ZHAO S Z， SUGANTHAN P N， PAN Q K， et al. Dynamic multi-swarm particle swarm optimizer with harmony search[J]. Expert systems with applications， 2011， 38(4): 3735-3742.

[6]LIANG J J， SUGANTHAN P N. Dynamic multi-swarm particle swarm optimizer[C]//Swarm Intelligence Symposium， 2005. [S.l.]， 2005: 124-129.

[7]KENNEDY J. Bare bones particle swarms[C]//Swarm Intelligence Symposium， 2003. SIS′03. Proceedings of the 2003 IEEE. [S.l.]， 2003: 80-87.

[8]SUN J， FANG W， WU X， et al. Quantum-behaved particle swarm optimization: analysis of individual particle behavior and parameter selection[J]. Evolutionary computation， 2012， 20(3): 349-393.

[9]DANESHYARI M， YEN G G. Constrained multiple-swarm particle swarm optimization within a cultural framework[J]. Systems， man and cybernetics， part a: systems and humans， 2012， 42(2): 475-490.

[10]SAHED O A， KARA K， HADJILI M L. Constrained fuzzy predictive control using particle swarm optimization[J]. Applied computational intelligence & soft computing， 2015， 2015(1): 1-15.

[11]WEN W，HAO Z．Improved particle swarm optimizer based on dynamic topology [J]．Computer engineering and applications，2005，41(34)：82-85.

[12]ZHAN Z H， ZHANG J， LI Y， et al. Adaptive particle swarm optimization[J]. Systems， man， and cybernetics， part B: cybernetics， 2009， 39(6): 1362-1381.

[14]LIANG J J， RUNARSSON T P， MEZURA-MONTES E， et al. Problem definitions and evaluation criteria for the CEC 2006 special session on constrained real-parameter optimization[J]. Journal of applied mechanics， 2006， 41: 8.

[15]VENKATRAMAN S， YEN G G. A generic framework for constrained optimization using genetic algorithms[J]. Evolutionary computation， 2005， 9(4): 424-435.

[16]CABRERA J C F， COELLO C A C. Handling constraints in particle swarm optimization using a small population size[M]//MICAI 2007: Advances in Artificial Intelligence. Springer Berlin Heidelberg， 2007: 41-51.

[17]CAI Z， WANG Y. A multiobjective optimization-based evolutionary algorithm for constrained optimization[J]. Evolutionary computation， 2006， 10(6): 658-675.

[18]WANG Y， CAI Z. Combining multiobjective optimization with differential evolution to solve constrained optimization problems[J]. Evolutionary computation， 2012， 16(1): 117-134.

[19]GAO L， LI S， KONG X， et al. On the iterative convergence of harmony search algorithm and a proposed modification[J]. Applied mathematics and computation， 2014， 247: 1064-1095.

[20]ZOU D， LIU H， GAO L， et al. Directed searching optimization algorithm for constrained optimization problems[J]. Expert systems with applications， 2011， 38(7): 8716-8723.

Multi-population random differential particle swarm optimization and its application

WANG Hao， GAO Liqun， OUYANG Haibin

(School of Information Science and Engineering， Northeastern University， Shenyang 110819， China)

To improve the performance of particle swarm optimization， a new multi-population random particle swarm optimization， based on differential evolution， is proposed in this paper. The proposed algorithm randomly divides the population into several groups and uses the roulette wheel method， based on attraction probability， to determine the possible search direction. When the expected optimization effect is not obvious， this algorithm uses random differential evolution to generate a new solution in the sub-population， aiming to increase the randomness and diversity of the search direction. In addition， a new constraint handling method is proposed to dynamically divide populations. Particle implemented velocity and position updates are proposed to improve search speed. Finally， the proposed algorithm is applied to a numerical optimization problem and a welded beam design problem. Simulation results show that this algorithm has the advantage of high precision and fast convergence when dealing with multi-peak functions. For dealing with a constrained problem， a new method is proposed to handle the constraints， which markedly shortens the search time. The proposed algorithm shows good optimization performance for complex constrained and unconstrained problems.

particle swarm optimization (PSO); multimodal problem; constrained optimization; roulette wheel method；differential evolution；velocity update；position update；search speed； numerical optimization；welded beam design

2015-12-04.

日期：2017-03-18.

國家自然科學基金項目(60674021)；遼寧省教育廳科學研究一般項目(L2014512).

王皓(1981-)，女，講師，博士; 高立群(1949-)，男，教授，博士生導師.

王皓，E-mail: haohaowang2008@126.com.

10.11990/jheu.201512017

TP301.6

A

1006-7043(2017)04-0652-09

王皓， 高立群， 歐陽海濱.多種群隨機差分粒子群優化算法及其應用[J]. 哈爾濱工程大學學報， 2017， 38(4): 652-660.

WANG Hao， GAO Liqun， OUYANG Haibin. Multi-population random differential Particle swarm optimization and its application[J]. Journal of Harbin Engineering University， 2017， 38(4): 652-660.

網絡出版地址：http://kns.cnki.net/kcms/detail/23.1390.u.20170318.0715.010.html