粒子群算法在非線性系統應用中的早熟現象及其改進

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

粒子群算法在非線性系統應用中的早熟現象及其改進

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

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

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

0 引言

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

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

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

1 PSO早熟退化現象及其分析

1.1 PSO的數學模型

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

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

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

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

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

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

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

2 局部“飛躍”策略

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

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

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

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

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

3 實驗仿真與實例分析

3.1 Benchmark測試函數

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

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

表1 Benchm ark函數Table 1 Benchmark functions

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

圖5 Restrigin函數仿真中初始點對優化結果的影響Fig.5 Effect of initial point on optimization result in Restrigin function

圖6 Griewank函數仿真中初始點對優化結果的影響Fig.6 Effect of initial point on optimization result in Griewank function

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

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

表2 多維測試函數的仿真結果Table 2 Results of benchmarks w ith different dimensions

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

3.2 系統工程實例

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

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

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

表3 10SP2算例流體參數表Table 3 Fluid parameters for case 10SP2

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

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

圖8 對文獻[21]中的結構進行PSO優化得到的費用－迭代次數折線圖Fig.8 Decline curve of 10SP2 in Ref.[21]for PSO

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

圖10 對文獻[21]采用結合局部“飛躍”策略的PSO算法優化后的換熱網絡結構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優化的費用下降曲線Fig.11 Decline curve of10SP2 for PSO

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

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

圖12 對文獻[25]采用結合局部“飛躍”策略后的PSO算法優化后的換熱網絡結構Fig.12 HEN structure of improved PSO in Ref.[25]

表5 文獻[23]算例優化結果對比Table 5 Results com parison w ith 10SP2 in Ref.[23]

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

4 結論

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

[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“leap”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；“leap”strategy

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

TP18

A

2014－11－11；

2015－04－14

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

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