粒子群算法在非線性系統(tǒng)應(yīng)用中的早熟現(xiàn)象及其改進

肖 媛, 崔國民, 彭富裕, 周 靜（上海理工大學能源與動力工程學院,上海 200093）

粒子群算法在非線性系統(tǒng)應(yīng)用中的早熟現(xiàn)象及其改進

肖 媛, 崔國民, 彭富裕, 周 靜
（上海理工大學能源與動力工程學院,上海 200093）

通過分析粒子群算法早熟現(xiàn)象的機理,研究早熟收斂的本質(zhì),并提出一種克服粒子群算法早熟現(xiàn)象的局部“飛躍”策略.應(yīng)用仿真及系統(tǒng)工程實例表明,該方法能有效地改善粒子群算法在非線性全局優(yōu)化上的早熟問題,提高了粒子群算法的全局搜索能力.

粒子群算法；早熟收斂；系統(tǒng)工程；局部“飛躍”策略

0 引言

粒子群算法,也稱粒子群優(yōu)化算法（Particle Swarm Optimization,PSO）,是1995年Kennedy＆Eberhart[1]首次提出的模擬鳥類捕食行為的群體智能算法.Clerc＆Kennedy[2]對PSO的全局搜索能力、算法穩(wěn)定性和收斂性能進行了理論分析,該算法具有易實現(xiàn)、收斂速度快、調(diào)整參數(shù)少的優(yōu)點,且對于目標函數(shù)和約束條件的要求不高,為解決復(fù)雜非線性系統(tǒng)的優(yōu)化問題提供了新的求解途徑和方法,已經(jīng)成功應(yīng)用于系統(tǒng)工程的各個領(lǐng)域[3－9],并且在求解約束優(yōu)化問題、離散優(yōu)化問題和多目標優(yōu)化問題等方面都得到了相應(yīng)的發(fā)展.

然而,PSO存在早熟收斂的問題,尤其是在求解多維非線性問題時,會出現(xiàn)種群聚集到局部極值或局部極值鄰域內(nèi)的一個點停滯不動的現(xiàn)象.這一現(xiàn)象引起了國內(nèi)外學者們的廣泛關(guān)注,也對該缺陷作了改進嘗試.Peram等[10]提出了FDR-PSO（Fitness-Distance-Ratio Based PSO）來改進粒子速度的更新模式,改善了早熟收斂現(xiàn)象；Peer等[11]提出了GCPSO（Guaranteed Convergence PSO）,利用不同的鄰域拓撲結(jié)構(gòu)來保持粒子搜索過程中的種群多樣性,盡量避免其早熟收斂；劉華鎣等[12]提出了基于混沌優(yōu)化搜索解決早熟收斂的粒子群算法,增強了粒子群算法的避免局部極小能力；吳敏等[13]提出了在粒子群收斂停滯時,通過引入共軛梯度算法計算的信息來影響粒子速度的更新以保持群體的活性；Chaturvedi等[14]提出了 SOH_PSO（selforganizing hierarchical PSO）,采用動態(tài)加速因子來增強種群多樣性；魏建香等[15]提出了一種基于免疫選擇的粒子群優(yōu)化算法來調(diào)節(jié)種群的多樣性；Sun等[16]提出了PSO-GSA（PSO with gravitational search algotithm）來平衡PSO的全局搜索能力和局部搜索能力,采用移動因子來改進速度更新公式而保持其種群多樣性.以上的改進或是通過動態(tài)參數(shù)來活躍進化過程中的種群多樣性,或是在粒子群收斂停滯后采用外部動力影響粒子的速度更新.然而應(yīng)用到有約束、非線性的復(fù)雜系統(tǒng)的優(yōu)化時,這一早熟現(xiàn)象還是沒能從根本上得到解決,原因在于以上種種嘗試尚未對PSO早熟的機理明確分析和解釋,且無法克服優(yōu)化問題本身的非線性而難以實現(xiàn)進化后期局部極小值的逃離.

本文通過分析PSO在復(fù)雜非線性系統(tǒng)進化的特點,及其在不同局部最優(yōu)解周圍的進化進程,揭示粒子群算法進化后期局部退化現(xiàn)象的原因和機理；在此基礎(chǔ)上,提出克服進化后期早熟的局部“飛躍”策略,使停滯收斂的粒子獲得“重生”,力圖完善粒子群算法的全局搜索能力.

1 PSO早熟退化現(xiàn)象及其分析

1.1 PSO的數(shù)學模型

粒子群算法的基本思想是通過群體中個體之間的協(xié)作和信息共享來尋找最優(yōu)解,群體由N個粒子組成,每個粒子代表了搜索空間中一組d維潛在解,包括當前位置xi＝（xi1,xi2,…,xid）和當前飛行速度vi＝（vi1,vi2,…,vid）,i＝1,2,…,N.在每次迭代中,粒子通過追蹤兩個“經(jīng)驗”來調(diào)整下一次迭代的位置和速度,這兩個“經(jīng)驗”就是個體極值pi＝（pi1,pi2,…,pid）和種群的全局極值pg＝（pg1,pg2,…,pgd）.粒子根據(jù)自身慣性vi、個體極值pi、種群極值pg更新飛行的速度和位置：

式中,慣性因子ω是非負常數(shù),學習因子c1和c2是非負常數(shù),γ1和γ2是取值介于（0,1）的偽隨機數(shù),k是迭代次數(shù).

式（1）中的第一項表示粒子對其歷史信息的“遺傳”,ω控制了算法的開發(fā)和控制能力,當ω較大時可擴展粒子的搜索空間,增強算法的全局尋優(yōu)能力,當ω較小時算法的局部搜索能力得以改善；后兩項表示粒子對自身經(jīng)驗的認知及粒子之間的信息共享和相互作用,可認為是PSO優(yōu)化過程中的“進化項”.粒子更新模式如圖1所示.進化初期,每個粒子的位置和速度是隨機初始化的,種群中的最優(yōu)粒子pg吸引其它結(jié)構(gòu),使種群中的大部分粒子在“進化項”的作用下快速聚集到全局最優(yōu)區(qū)域[17].因此,粒子群算法具有較強的全局搜索能力,且在進化初期收斂速度較快.

1.2 PSO的早熟收斂的機理分析

通過實例發(fā)現(xiàn)在求解多維復(fù)雜非線性問題時,PSO容易陷入早熟收斂.文獻[12]引入了早熟收斂判斷機制,利用種群適應(yīng)度方差σ2來反映粒子的聚集程度,σ2越小,粒子聚集程度越大,若此時算法不滿足約束條件,將使種群失去多樣性而陷入早熟狀態(tài).因此當σ2＜c（c為給定常數(shù)）時,必須進行早熟處理,以避免優(yōu)化陷入局部極小值.為了實現(xiàn)種群跳出早熟收斂,首先必須分析PSO早熟的機理,探尋其搜索能力退化的本質(zhì).為簡化分析,本文以二維粒子為例,將粒子飛行速度的更新表示在二維直角坐標系如圖2.

圖1 粒子群算法更新模式Fig.1 Updatemode for PSO

圖2 二維粒子更新示意圖Fig.2 Velocity update of particle for d＝2

2 局部“飛躍”策略

為了改進PSO的局部退化現(xiàn)象,必須激活進化后期停滯的粒子,使粒子飛行獲得“重生”,恢復(fù)種群的多樣性,本文提出一種局部“飛躍”策略,當PSO陷入停滯時,對式（2）中的xik＋1在當前局部極值點對應(yīng)的x?

k的鄰域范圍內(nèi)給予一個新的隨機量,而不再按照先前的尋優(yōu)方向搜索,進而隨機搜索到更優(yōu)解.當粒子搜索到更優(yōu)解,以搜索到的該解作為PSO下一輪搜索的初始點,強制跳出極小值點,并繼續(xù)搜索全局最優(yōu)解.引入早熟收斂判斷及局部“飛躍”策略的粒子群算法流程圖如圖3.

圖3 引入早熟收斂判斷及局部“飛躍”策略的PSO流程圖Fig.3 Flow chart of PSO with premature judgement and“l(fā)eap”handling strategy

局部“飛躍”策略充分利用了隨機變量的隨機性、遍歷性以及PSO的開放式結(jié)構(gòu)特點,對優(yōu)化問題的目標函數(shù)要求不高,無須優(yōu)化問題具有連續(xù)性和可微性,因此采用該策略解決PSO優(yōu)化復(fù)雜非線性系統(tǒng)中的早熟收斂問題,在局部極值的鄰域范圍隨機搜索以在解空間找到更優(yōu)值作為PSO下一次迭代的初始點.

圖4 粒子隨機搜索示意圖Fig.4 Stochastic search pattern of particles trapped into localminimum

3 實驗仿真與實例分析

3.1 Benchmark測試函數(shù)

選取Rastrigin函數(shù)、Griewank函數(shù)作為Benchmark測試函數(shù),函數(shù)的名稱、公式、維數(shù)、范圍、目標最小值如表1.

兩種函數(shù)均屬于多峰非線性函數(shù),搜索空間大,局部極值點多,一般算法難以找到其全局最優(yōu)解,因此可以用來檢驗改進前后的粒子群算法跳出局部最優(yōu)的能力.為了保證算法的收斂,慣性因子ω取0.9,學習因子c1和c2均取0.5.在進行算法仿真時,改進前后的PSO的迭代次數(shù)均為1 000,其它參數(shù)設(shè)置均相等.

表1 Benchm ark函數(shù)Table 1 Benchmark functions

首先,以二維函數(shù)的仿真來研究初始點對粒子群算法優(yōu)化效能的影響,如圖5和圖6.對于Rastrigin函數(shù),標準PSO基本都能找到目標最小值0,但當初始點偏離全局最優(yōu)點較遠時,PSO優(yōu)化仍會陷入早熟,優(yōu)化結(jié)果為0.994 954 425 017 109.對于非線性更強的Griewank函數(shù),初始點距離全局最優(yōu)區(qū)域越遠,PSO仿真結(jié)果偏離目標最小值越大,只有在（－1,1）范圍內(nèi)才能準確搜索到目標最小值.

圖5 Restrigin函數(shù)仿真中初始點對優(yōu)化結(jié)果的影響Fig.5 Effect of initial point on optimization result in Restrigin function

圖6 Griewank函數(shù)仿真中初始點對優(yōu)化結(jié)果的影響Fig.6 Effect of initial point on optimization result in Griewank function

針對PSO在非線性系統(tǒng)優(yōu)化中的早熟收斂現(xiàn)象,引入局部“飛躍”策略,極大地解決了PSO進化后期陷入局部極值點的問題,增強了PSO的全局搜索能力,提高了算法的優(yōu)化精度.對Restrigin函數(shù)的仿真均找到了全局最優(yōu)解,如圖5.對于Griewank函數(shù),從圖6中發(fā)現(xiàn),當初始點在（－600,493）范圍,改進后的PSO算法克服了標準PSO的早熟收斂,準確搜索到了目標最小值；當初始點在（494,600）范圍,改進后的PSO仿真結(jié)果相較目標最小值仍有較小的偏離,其原因在于目標函數(shù)的復(fù)雜非線性而難以找到全局最優(yōu)解.

其次,維數(shù)越高,PSO算法的早熟收斂現(xiàn)象越明顯,對10維、15維、20維的Rastrigin函數(shù)和Griewank函數(shù)采用PSO、改進后的PSO進行仿真實驗,在定義域范圍內(nèi)隨機生成相同的初始結(jié)構(gòu),參數(shù)設(shè)置同上,實驗結(jié)果如表2.

表2 多維測試函數(shù)的仿真結(jié)果Table 2 Results of benchmarks w ith different dimensions

15維的Rastrigin函數(shù)的仿真收斂曲線如圖7,顯示了引入局部“飛躍”策略的PSO算法跳出局部極小值并搜索到全局最優(yōu)解的過程,驗證了該策略能有效地解決PSO在非線性系統(tǒng)優(yōu)化中的早熟問題.

3.2 系統(tǒng)工程實例

換熱網(wǎng)絡(luò)優(yōu)化是過程系統(tǒng)工程中的重要領(lǐng)域,對系統(tǒng)能量的有效利用起著至關(guān)重要的作用.換熱網(wǎng)絡(luò)綜合就是要使熱回收目標最大或者費用目標最小,該問題本質(zhì)上屬于混合整數(shù)非線性規(guī)劃[18],其非線性主要源于對數(shù)平均溫差及費用計算時的非線性項,而表示換熱器有無的整型變量又極大地增加了非線性的復(fù)雜程度[19],因此即使小規(guī)模換熱網(wǎng)絡(luò)也無法證實能夠找到其全局最優(yōu)解[20].PSO應(yīng)用到換熱網(wǎng)絡(luò)優(yōu)化過程中,還是經(jīng)常出現(xiàn)飛行速度退化而使算法陷入早熟收斂的問題.本文將改進前后的PSO應(yīng)用于換熱網(wǎng)絡(luò)優(yōu)化算例,慣性因子取0.9、學習因子均取0.5,選取文獻中的固定結(jié)構(gòu)進行連續(xù)變量的優(yōu)化,通過實例分析PSO應(yīng)用于復(fù)雜非線性系統(tǒng)的早熟收斂問題,并驗證以上局部“飛躍”策略的有效性.

10SP2算例流體參數(shù)取自文獻[21],換熱器、冷卻器和加熱器的傳熱系數(shù)均為0.025 kW·（m2·℃）－1,換熱器面積計算公式為60A ＄·year－1,熱公用工程費用為100＄·（kW·year）－1,冷公用工程費用為15＄· （kW·year）－1,其它物流參數(shù)見表3.

圖7 Rastrigin函數(shù)的仿真收斂曲線對比Fig.7 The contrastive convergence cuves of simulation for Rastrigin fuction

表3 10SP2算例流體參數(shù)表Table 3 Fluid parameters for case 10SP2

文獻[21]中采用遺傳算法優(yōu)化得到換熱網(wǎng)絡(luò)最小年綜合費用5 666 755＄·year－1,對文獻[21]的換熱網(wǎng)絡(luò)結(jié)構(gòu)采用粒子群算法優(yōu)化得到的最小年綜合費用為5 641 344＄·year－1,其費用－迭代次數(shù)折線圖如圖8.進化初期,年綜合費用快速下降,但在進化后期趨于平穩(wěn),保持在5 641 344＄·year－1.由早熟收斂判斷機制可知,當前PSO的優(yōu)化費用是局部極小值而非全局最優(yōu)解,即此時的收斂屬于早熟現(xiàn)象.

為了使種群快速跳出早熟收斂,引入上文提出的改進策略,在局部極小值的鄰域范圍內(nèi)隨機搜索,如圖3進行迭代計算,并增加迭代次數(shù),擴大隨機搜索的空間,得到了新的費用下降曲線.將兩次的費用下降曲線對比如圖9,從圖中可明顯看出局部“飛躍”策略有效地處理了粒子群的早熟收斂問題,多次跳出了局部極小值點,最終得到的最小年綜合費用為5 640 721＄·year－1,對應(yīng)的換熱網(wǎng)絡(luò)結(jié)構(gòu)的能量分布如圖10,本文的優(yōu)化費用與文獻對比結(jié)果如表4.

圖8 對文獻[21]中的結(jié)構(gòu)進行PSO優(yōu)化得到的費用－迭代次數(shù)折線圖Fig.8 Decline curve of 10SP2 in Ref.[21]for PSO

圖9 改進前后的PSO優(yōu)化費用下降對比圖Fig.9 Contrastive decline curves of10SP2 for PSO with and without improvement

圖10 對文獻[21]采用結(jié)合局部“飛躍”策略的PSO算法優(yōu)化后的換熱網(wǎng)絡(luò)結(jié)構(gòu)Fig.10 HEN structure of improved PSO in Ref.[21]

文獻[21] 標準PSO 文獻[22] 本文5 666 755＄·year－1 5 641 344＄·year－1 5 640 730＄·year－1 5 629 721＄·year－1

圖11 PSO優(yōu)化的費用下降曲線Fig.11 Decline curve of10SP2 for PSO

文獻[23]采用局部優(yōu)化方法得到的最小年綜合費用為5 631 380＄·year－1,對文獻[23]對應(yīng)的換熱結(jié)構(gòu)采用粒子群算法優(yōu)化后費用為5 632 308＄·year－1,其費用－迭代次數(shù)折線圖如圖11.粒子群算法在進化初期收斂速度快,費用下降快,但在進化后期趨于平穩(wěn),費用保持在5 632 308＄·year－1,對比文獻[23]得到的5 631 380＄·year－1可知,當前PSO的優(yōu)化費用是局部極小值而非全局最優(yōu)解,即此時的收斂屬于早熟現(xiàn)象.

引入本文提出的局部“飛躍”策略,在局部極小值的鄰域范圍搜索,最終多次跳出了局部極值點,而得到了更優(yōu)換熱網(wǎng)絡(luò)結(jié)構(gòu),其能量分布如圖12.改進前后的費用下降對比曲線圖如圖13,本文的優(yōu)化費用與文獻對比結(jié)果如表5.從費用下降曲線能明顯地看出粒子跳出局部極小值的“重生”過程,驗證了局部“飛躍”策略的有效性.

圖12 對文獻[25]采用結(jié)合局部“飛躍”策略后的PSO算法優(yōu)化后的換熱網(wǎng)絡(luò)結(jié)構(gòu)Fig.12 HEN structure of improved PSO in Ref.[25]

表5 文獻[23]算例優(yōu)化結(jié)果對比Table 5 Results com parison w ith 10SP2 in Ref.[23]

圖13 改進前后的PSO優(yōu)化費用下降對比圖Fig.13 Contrastive decline curves of 10SP2 for PSO with and without improvement

4 結(jié)論

改進PSO在復(fù)雜非線性系統(tǒng)應(yīng)用中的早熟收斂,提出了局部“飛躍”策略的PSO算法,增強了PSO的全局搜索能力.通過Benchmark測試函數(shù)仿真驗證,引入局部“飛躍”策略的PSO具有更大的全局搜索區(qū)域,使Griewank函數(shù)的全局搜索區(qū)域從 （ －1,1）擴大到 （－600,493）；對于嚴重非線性的換熱網(wǎng)絡(luò)優(yōu)化問題,通過10SP2算例驗證,改進的PSO跳出了標準PSO進化后期陷入的局部極小費用,重新分配了換熱網(wǎng)絡(luò)的能量分布,使換熱網(wǎng)絡(luò)性能均得到了一定的提升.

[1] Kennedy J,Eberhart R.Particle swarm optimization[C]∥1995 IEEE International Conference on Neural Nerworks Proceedings.Perth：IEEE,1995：1942－1948.

[2] Clerc M,Kennedy J.The particle swarm-explosion,stability,and convergence in a multidimensional complex space[J].Evolutionary Computation,IEEE Transactions on,2002,6（1）：58－73.

[3] Abido M.Optimal design of power-system stabilizers using particle swarm optimization[J].IEEE Transactions on Energy Conversion.2002,17（3）：406－413.

[4] Yoshida H,Kawata K,Fukuyama Y,Takayama S,Nakanishi Y.A particle swarm optimization for reactive power and voltage control considering voltage security assessment[J].IEEE Transactions on Power Systems,2000,15（4）：1232－1239.

[5] Zhang JR,Zhang J,Lok T M,Lyu M R.A hybrid particle swarm optimization-back-propagation algorithm for feedforward neural network training[J].Applied Mathematics and Computation,2007,185（2）：1026－1037.

[6] Zhang X,Yu L,Zheng Y.Two-stage adaptive PMD compensation in a 10 Gbit/s optical communication system using particle swarm optimization algorithm[J].Optics Communications,2004,231（6）：233－242.

[7] Liu HW,Li J.A particle swarm optimization-based multiuser detection for receive-diversity-aided STBC systems[J].Signal Processing Letters,2008,15：29－32.

[8] Silva A P,Ravagnani M A S S,Biscaia Jr E C,et al.Optimal heat exchanger network synthesis using particle swarm optimization[J].Optimization and Engineering,2010,11（3）：459－470.

[9] Gudise V G,Venayagamoorthy G K.FPGA placement and routing using particle swarm optimization[C]∥IEEE Computer Society Annual Symposium on VLSI：Emerging Trends in VLSISystems Design,Lafayette,LA,USA,2004：307－308.

[10] Peram T,Veeramachaneni K,Mohan C K.Fitness-distance-ratio based particle swarm optimization[C]∥Swarm Intelligence Symposium,2003.SIS'03.Proceedings of the 2003 IEEE.IEEE,2003：174－181.

[11] Peer E S,Van den Bergh F,Engelbrecht A P.Using neighbourhoods with the guaranteed convergence PSO[C]∥Swarm Intelligence Symposium,2003.Proceedings of the 2003.IEEE,2003：235－242.

[12] Liu Huaying,Lin Yuer,Zhang Junshi.A hybrid particle swarm optimization based on chaos strategy to handle local convergence[J].Computer Engineering,2006,42（13）：77－79.

[13] Wu Min,Ding Lei,Cao Weihua,et al.A kind of hybrid optimization algorithmwith prevention of premature convergence of particleswarm[J].Control and Decision,2008,23（5）：511－514.

[14] Chaturvedi K T,Pandit M,Srivastava L.Self-organizing hierarchical particle swarm optimization for nonconvex economic dispatch[J].Power Systems,IEEE Transactions on,2008,23（3）：1079－1087.

[15] W Jianxiang,SYuehong,SXinning.A novel particle swarm optimization based on immune selection[J].Journal of Nanjing University（Natural Science）,2010,46（1）：1－9.

[16] Sun S,Peng Q.A hybrid PSO-GSA strategy for high-dimensional optimization andmicroarray data clustering[C]∥Information and Automation（ICIA）,2014 IEEE International Conference,2014：41－46.

[17] Kennedy J.Smallworlds and mega-minds：Effects of neighborhood topology on particle swarm performance[C]∥Evolutionary Computation,1999.Proceedings of the 1999 Congress IEEE,1999：3.

[18] Yee T F,Grossmann IE.Simultaneous optimizationmodels for heat integration（II）：Heatexchanger network synthesis[J].Compute Chem Eng,1990,14（10）：1165－1184.

[19] Hu Xiangbai,Cui Guomin,Tu Weimin.The non-linear characteristics analyze of the minlp in the complex heat exchanger networks[J].Journal of Engineering Thermophysics,2012,33（002）：285－287.

[20] Yerram setty K M,M urty C V S.Synthesis of cost—optimal heat exchanger networks using differential evolution[J].Computers and Chemical Engineering,2008,32（8）：1861－1876.

[21] RavagnaniM,Silva A P,Arroyo PA,et al.Heat exchanger network synthesis and optimization using genetic algorithm[J].Applied Thermal Engineering,2005,25（7）：1003－1017.

[22] He Qiaole,Cui Guomin,Xu Haizhu.Application of memetic particle swarm optimization to continuous variable global optimization of cost-optimal heat exchanger networks[J].Petrochemical Techonology,2014,（1）：37－45.

[23] Hu Xiangbai.Global synthesis of heat exchanger networks[D].Shanghai：Journal of University of Shanghai for Science and Technology,2013.

An Im proved Particle Swarm Optim ization for Precocious Phenomenon in Nonlinear System Engineering

XIAO Yuan, CUIGuomin, PENG Fuyu, ZHOU Jing
（School ofEnergy and Power Engineering,University of Shanghai for Science and Technology,Shanghai 200093,China）

By analyzingmechanism of premature phenomenon in particle swarm optimization（PSO）,we found nature of premature convergence and proposed a“l(fā)eap”strategy to jump out of localminimum,making halted particles“renewed”when they are trapped into a local optimum.The strategy is applied to nonlinear programming and results are encouraging.The improved PSO solves efficiently premature convergence of the algorithm applying in nonlinear optimizations and improves global search ability of PSO.

particle swarm optimization；premature converge；systems engineering；“l(fā)eap”strategy

1001-246X（2015）06-0693-08

TP18

A

2014－11－11；

2015－04－14

國家自然科學基金（51176125）及滬江基金研究基地專項（D14001）資助項目

肖媛（1991－）,女,碩士研究生,研究方向為過程系統(tǒng)工程,E-mail：yxiao0606＠yeah.net