基于群體早熟程度和非線性周期振蕩策略的改進粒子群算法

朱喜華，李穎暉，李寧，范炳奎

（1. 空軍工程大學 航空航天工程學院，陜西 西安 710038；2. 中國人民解放軍95291部隊裝備部，湖南 衡陽 421002）

1 引言

粒子群優化算法（PSO）是進化算法的一個重要分支，最早由美國學者 Kennedy和 Eberhart于1995年提出，是一種基于種群迭代搜索的自適應優化算法，它通過種群粒子中個體的交互作用來尋找復雜問題空間中的優化解。與遺傳算法等其他進化算法相比，粒子群優化算法具有結構簡單、參數少及收斂速度快、容易實現等優點，具有較低的空間復雜度和時間復雜度，并被證明能夠以較小的計算代價獲得良好的優化解[1]，因此得到了廣泛的研究和應用。隨著通信技術的發展，通信領域也出現了各種優化問題，如通信星座優化設計[2]、無線傳感器網絡的感知器分布優化[3]及生存周期優化[4]等，要解決這些問題就需要采用先進的優化算法。因此，研究粒子群算法及其改進策略，并將其應用于通信領域的優化計算具有十分重要的理論及工程實際意義。

基本PSO算法具有快速收斂的特性，但存在尋優效率較低、容易停滯于局部最優值以及早熟收斂等問題[5]。早熟收斂是由于粒子群體的多樣性在迭代搜索過程中快速丟失造成的，對此，很多學者提出了改進措施，主要采用以下2種策略。1)對粒子的速度和位置采用不同的參數策略來更新，如采用線性變化的動態慣性權重。該策略的主要特點是忠實于 PSO的原始思想，速度和位置的更新由粒子自身經驗和群體經驗作指導[6]。2)引入變異算子[7]。變異操作能夠提高粒子群算法的開拓能力，并有效克服早熟收斂，但是選擇對收斂性能有顯著提升的變異算子十分困難。此外，如何變異、何時變異、變異概率以及變異位置等問題在實際操作過程中都難以確定。

本文在參考粒子群算法各種改進策略的基礎上，提出了一種新的基于群體早熟收斂程度和非線性周期振蕩參數策略的自適應混沌粒子群優化算法。該算法利用混沌的遍歷性特點初始化粒子的速度和位置，使搜索空間遍布整個優化變量的取值空間；根據粒子群的早熟收斂程度和粒子的適應度值對不同粒子的慣性權重采用不同的自適應更新策略；在算法的整個搜索迭代過程中，粒子的個體學習因子和社會學習因子都周期性地非線性變化，模擬鳥群在覓食過程中不斷分散和重組的現象。基準測試函數的仿真實驗表明，本文提出的算法能有效平衡粒子群的局部搜索能力和全局搜索能力，避免群體早熟收斂并提高最優解質量，且具有良好的穩定性。

2 粒子群算法的基本原理

PSO算法的思想來源于鳥類遷徙覓食的模型，其關鍵在于每個粒子在解空間內根據自己的記憶和從其他粒子獲取的社會信息更新自己的位置，通過個體間的協作與競爭，實現復雜空間中最優解的搜索，其數學描述為：每個粒子是D維搜索空間中的一個點，設粒子規模為N，第i個粒子的位置矢量可以表示為xi=(xi1,xi2,…,xiD)，速度矢量為vi=(vi1,vi2,…,viD)；pi=(pi1,pi2,…,piD)為第 i個粒子搜索到的最優位置，稱為個體極值，表示粒子的個體經驗；pg=(pg1,pg2,…,pgD)為整個粒子群體搜索到的最優位置，稱為全局極值，表示粒子的群體經驗。

對于第k+1次迭代，每個粒子按照式(1)更新自己的速度和位置。

其中，i=1,2,…,N，N為粒子規模；d=1,2,…,D，D為解空間的維數，即自變量的個數；ω為慣性權重；c1為粒子的個體學習因子，c2為社會學習因子，分別用于調節粒子向個體極值和全局極值方向飛行的最大步長；r1、r2為[0,1]之間均勻分布的隨機數。

3 粒子群算法的時變參數策略

慣性權重ω描述了粒子上一代速度對當前代速度的影響，控制其取值大小可調節PSO算法的全局與局部尋優能力。慣性權重值較大時，全局尋優能力強，局部尋優能力弱；反之，則局部尋優能力增強，而全局尋優能力減弱[8,9]。為此，學者對起初的固定權重策略提出了各種改進方案，典型的有線性遞減策略、非線性遞減策略和隨機策略等。

線性遞減策略的原理是：在不同的搜索階段采用不同的慣性權重，在搜索初期采用較大的慣性權重有利于搜索整個空間，不易陷入局部最優值；在后期當算法收斂到較優解時，則傾向于進行局部挖掘，使粒子迅速收斂于全局最優值，其數學描述為[10]

其中，iω、fω分別為慣性權重的初值和終值，t為當前迭代步數，T為最大迭代步數。

Eberhart和Shi經過研究發現線性遞減策略對于動態系統的效果并不理想，進而提出了一種慣性權重隨機變化的策略[10]

其中，rand為[0,1]之間均勻分布的隨機數。

經驗證，采用隨機策略時早期階段的收斂速度明顯加快，但是，在多個測試函數中所表現出的收斂性能卻并不理想。為此，有學者進一步提出了非線性遞減策略，如式(4)所示[5]。

針對慣性權重進行改進研究的同時，學者Ratnaweera對學習因子進行了改進，指出了學習因子為常數的缺陷，并提出了類似于慣性權重線性變化的策略，如式(5)所示[10]。

其中，c1i和 c1f是個體學習因子的初值和終值，c2i和c2f是社會學習因子的初值和終值。

4 基于群體早熟程度和非線性周期振蕩策略的混沌改進方法

粒子群優化算法雖然具有算法結構簡單、參數少及收斂速度快等優點，但容易陷入到局部極值點，導致得不到全局最優解，原因有兩方面：一是待優化函數的性質，二是在運行過程中由于算法的參數設計、粒子規模選擇不恰當等原因，導致在計算過程中粒子的多樣性迅速消失，造成算法“早熟”。本文主要針對算法的參數設計進行改進，同時利用混沌特性初始化粒子群的參數，以盡可能提高算法的性能。

4.1 粒子參數的混沌初始化

混沌具有遍歷性、隨機性和規律性等特點，能在一定范圍內按其自身規律不重復地遍歷所有狀態，使得混沌優化理論成為一個嶄新的課題，得到了學者們的廣泛重視和大量研究[11,12]。混沌優化是一種新穎的優化方法，它利用混沌系統特有的遍歷性特點進行優化搜索，不要求目標函數具有連續和可微的性質，其基本思想是首先產生一組與優化變量相同數目的混沌變量，用類似載波的方式將混沌引入優化變量使其呈現混沌狀態，同時把混沌運動的遍歷范圍放大到優化變量的取值范圍，然后直接利用混沌變量進行搜索。

一般應用Logistic映射（邏輯映射）來產生混沌變量，其映射形式如下

其中，μ∈[0,4]為控制變量，zk∈[0,1]，k=0,1,2,… 。當μ=4時，式(6)完全處于混沌狀態，此時，軌道布滿區間[0,1]，即混沌軌道在區間[0,1]內遍歷。由任意初值z0∈[0,1]可迭代出一個確定的混沌時間序列z1,z2,z3,…。

4.2 基于群體早熟程度的自適應慣性權重調整

在PSO算法中，搜索陷入局部極值往往表現為微粒幾乎停止不動。當群體的最優適應值長時間未發生變化（停滯）時，應根據群體早熟收斂程度自適應地調整慣性權重。如果對整個群體采用相同的自適應操作，則當群體已收斂到全局最優附近時，優秀粒子被破壞的概率會隨著其慣性權重的增加而增加，從而使PSO算法的性能下降。為了充分發揮自適應操作的效能，本文提出了一種根據群體早熟程度和粒子自身適應度值自適應調整慣性權重的策略，針對不同的粒子分別采用不同的自適應操作，使得群體始終保持慣性權重的多樣性。

其中，fg為全局最優粒子的適應度值，fap為適應度值優于當前所有粒子適應度平均值 fag的粒子的適應度平均值。Δ可用來評價粒子群的早熟收斂程度，Δ越小，粒子群越趨于早熟收斂。對于適應度值為fi的粒子，其自適應調整策略如下所示。

1)fi優于fap

此時粒子比較接近全局最優值，是群體中的較優粒子，其慣性權重應取較小值，避免“逃離”全局最優值，粒子的慣性權重按式(8)自適應調整。

其中，ωmin為ω的最小值，sω為ω取值范圍的中間值。粒子適應值越佳，其慣性權重相應越小，以加強局部尋優。

2)fi劣于fap但優于fag

此時粒子是群體中的一般粒子，具有較好的全局尋優能力和局部尋優能力，其慣性權重按式(9)所示的非線性遞減策略自適應調整。

3)fi劣于fag

此時粒子是群體中較差的粒子，應賦予較大的慣性權重，其自適應調整策略為

其中，參數k1＞1用于控制ω的上限，k1越大，ω的上限越大；k2＞0用于控制ω的調節能力。

4.3 非線性周期振蕩參數策略

受社會群體中常發生的分散和重組交替現象（如鳥類覓食過程）的啟發[10]，結合群體早熟收斂程度的概念，本文提出了一種采用非線性振蕩參數策略的粒子群優化算法，使全局搜索和局部挖掘在優化過程中交替，以提高算法的全局尋優能力。

在搜索初期，采用較大的個體學習因子和較小的社會學習因子，有利于群體搜索整個空間；在搜索后期，較小的個體學習因子和較大的社會學習因子則有利于群體收斂于全局最優。因此，粒子的個體學習因子c1采用非線性遞減策略，而社會學習因子c2采用非線性遞增策略，其數學描述如式(11)所示。

其中，c1max、c2max分別為粒子個體學習因子和社會學習因子的最大值；c1min、c2min分別為粒子個體學習因子和社會學習因子的最小值；L為振蕩周期；mod(·)表示取模運算。學習因子c1、c2的變化趨勢如圖1所示。

圖1 粒子學習因子周期振蕩策略

4.4 算法收斂性和復雜度分析

對于式(1)所示的基本粒子群算法，令φ1=c1r1，φ2=c2r2，則式(1)中的兩式可合并為

下面根據粒子群慣性權重的調整策略分3種情況對上述條件進行分析。

1)fi優于fap

綜合式(8)、式(11)和式(19)，可得

其中，a1=c1max+c2min，a2=c2max-c2min-c1max+c1min。不妨作最保守的估計，把不等式(20)的兩邊看作2個函數，要滿足式(20)，只需滿足式(20)左邊函數的最小值不小于右邊函數的最大值（以下簡稱“最小—最大”原理），經化簡可得

2)fi劣于fap但優于fag

綜合式(9)、式(11)和式(19)，可得

根據“最小—最大”原理，可將式(22)化簡為

3)fi劣于fag

綜合式(10)、式(11)和式(19)，可得

由k1＞1，k2＞0可知，不等式(24)左邊函數的值域為(0.5,1.5)，因此，根據“最小—最大”原理，滿足不等式(24)的條件為

綜上可得，算法收斂時參數需滿足的條件為

綜上可知，只需選取合適的算法參數，使其滿足式(26)，即可保證本文算法的收斂性。

下面分析算法的復雜度。設粒子群的規模為N，每一個粒子的維數為D，最大迭代步數為T，則混沌初始化粒子群速度和位置的計算復雜度為O(ND)。在每一次迭代運算中，找出適應度值小于所有粒子適應度均值的粒子的計算復雜度為O(N)，基于群體早熟程度的慣性權重自適應調整的計算復雜度為O(N)，采用非線性振蕩策略調整粒子學習因子的計算復雜度為O(1)，更新粒子速度和位置的計算復雜度為O(ND)。因此，算法總的計算復雜度為O(ND)+O(T(N+N+1+ND))=O(TND)。

5 算法步驟及仿真驗證

5.1 算法的實現步驟

根據上文中的算法原理及改進策略，本文提出的基于群體早熟收斂程度和周期振蕩參數策略的混沌自適應粒子群算法的實現步驟如下。

Step1 確定粒子群規模N、最大迭代次數T和振蕩周期L等參數，并根據4.1節中的方法對粒子的位置和速度進行混沌初始化。

Step2 初始化粒子群的局部最優值和全局最優值。

Step3 計算各粒子的適應度值，并根據各粒子的早熟收斂程度選擇相應的策略調整其慣性權重。

Step4 采用周期振蕩參數策略更新粒子的個體學習因子和社會學習因子。

Step5 更新粒子群的局部最優值和全局最優值。

Step6 若滿足停止條件，停止搜索，并輸出全局最優值及其適應度值；否則轉向Step3。

5.2 仿真驗證

為了對本文所提算法的性能進行分析和驗證，選取4個典型Benchmark優化問題進行分析。根據文獻[15]，粒子種群采用非對稱初始化。此外，對粒子的位置和速度加以限制，防止粒子遠離搜索空間。各優化函數的初始化范圍和粒子取值區間如表1所示。

為了驗證本文所提（簡稱PDNPO-PSO）算法的性能，將其與參數線性調整PSO（L-PSO，慣性權重、學習因子均線性變化）算法、參數非線性調整PSO（N-PSO，慣性權重、學習因子均非線性變化）算法、混沌粒子群（C-PSO）算法和基于群體早熟程度的自適應 PSO（PD-PSO，學習因子非線性變化）算法進行對比分析。考慮到算法每次運行的隨機性，對于每個測試函數所采用的每種優化算法都重復測試 20次，取其均值作為最終的優化結果，參數的振蕩周期取為L=300。對各基準測試函數的仿真結果如圖2所示。

圖2中的縱坐標為對最優粒子適應度值求以10為底的對數后的值。通過分析可知，對于4個基準測試函數，以上5種粒子群算法都能在有限的迭代步數內迅速向全局最優解靠攏。其中，參數線性變化策略（L-PSO）相比而言收斂速度最慢，在設置迭代步數范圍內還沒收斂到最優值，參數非線性變化策略（N-PSO）次之；混沌粒子群算法（C-PSO）的尋優速度和效果要優于參數線性變化和非線性變化策略的粒子群算法；基于粒子群體早熟程度的自適應 PSO（PD-PSO）算法全局尋優效果較好，能以較快的速度收斂到全局最優值，且尋優結果比較接近實際最優值；本文所提（PDNPO-PSO）算法則綜合了其他各算法的優點，尋優效果最佳。

表1 基準測試函數及其參數設置

圖2 基準測試函數收斂曲線

為了進一步比較以上各算法的性能，對于每一個基準測試函數，對每種算法搜索到的最優值求平均值，作為最終的全局最優值。此外，為了分析比較各算法的穩定性，分別對重復測試中每次得到的最優粒子位置的各維求標準差，然后對所有維數的標準差求和，以此作為該算法穩定性的指標，標準差越小，算法越穩定。各算法的穩定性能指標如表2所示。

由表2可知，相比其他幾種PSO算法，本文提出的基于群體早熟程度和周期震蕩參數策略的自適應混沌粒子群算法具有優越的全局尋優能力，對4個基準測試函數都能有效地找到最優值，且算法性能較穩定。

表2 各算法穩定性比較

6 結束語

本文在參考現有粒子群算法參數時變策略的基礎上，結合混沌的遍歷特性，提出了一種新的粒子群優化算法——基于群體早熟收斂程度和非線性周期振蕩參數策略的自適應混沌粒子群優化算法。該算法首先利用混沌特性初始化粒子的速度和位置信息；慣性權重根據粒子種群的早熟收斂程度和不同適應度值的粒子自適應地采用不同的調整策略；對于學習因子的調整，則采用周期振蕩策略，在每一振蕩周期內學習因子非線性調整，模擬鳥類覓食過程中交替出現的分散和重組現象。經4個基準測試函數仿真驗證表明，本文提出的算法不僅收斂速度快、搜索到的全局最優值質量高，而且算法具有良好的穩定性，在通信領域的優化問題中具有良好的應用前景。

[1]SIERRA M R,COELLO C A C. Multi-objective particle swarm optimizers: a survey of the state-of-the-art[J]. International Journal of Computational Intelligence Research,2006,2(3): 287-308.

[2]酈蘇丹,朱江,李廣俠. 采用遺傳算法的低軌區域通信星座優化設計[J]. 通信學報,2005,26(8): 122-128.LI S D,ZHU J,LI G X. Optimization of LEO regional communication satellite constellation with GA algorithm[J]. Journal on Communications,2005,26(8): 122-128.

[3]聞英友,姜月秋,趙林亮等. 傳感器網絡中基于樹的感知器分布優化[J]. 通信學報,2005,26(3): 1-6.WEN Y Y,JIANG Y Q,ZHAO L L,et al. Optimal sensor node distribution algorithm based on tree in sensor network[J]. Journal on Communications,2005,26(3): 1-6.

[4]朱劍,趙海,徐久強等. WSN中可靠通信保障下的生存周期優化問題研究[J]. 通信學報,2010,31(6): 67-73.ZHU J,ZHAO H,XU J Q,et al. Research of survival period optimization with ensuring reliable communication in WSN[J]. Journal on Communications,2010,31(6): 67-73.

[5]靳其兵,趙振興,蘇曉靜. 基于粒子健康度的快速收斂粒子群優化算法[J]. 化工學報,2011,62(8): 2328-2333.JIN Q B,ZHAO Z X,SU X J. PSO algorithm with high speed convergence based on particle health[J]. CIESC Journal,2011,62(8): 2328-2333.

[6]SHI Y H,EBERHART R C. A modified particle swarm optimizer[A].Proc of IEEE International Conference on Evolutionary Computation[C].Anchorage,Alaska,USA,1998.69-73.

[7]STACEY A,JANCIC M,GRUNDY I. Particle swarm optimization with mutation[A]. The 2003 Congress on Evolutionary Computation[C].Camberra,Australia,2003.1425-1430.

[8]張利鳳,胡小兵. 求解非線性約束問題的混合粒子群優化算法[J].計算機科學,2011,38(10A): 178-180.ZHANG L F,HU X B. Hybrid particle swarm algorithm of solving nonlinear constraint optimization problems[J]. Computer Science,2011,38(10A): 178-180.

[9]李軍軍,甘世紅,許波桅. 基于偽冪函數的離散粒子群算法及其應用[J]. 控制理論與應用,2011,28(6): 834-838.LI J J,GAN S H,XU B W. Discrete particle swarm optimization algorithm based on pseudo power function and its applications[J]. Control Theory & Applications,2011,28(6): 834-838.

[10]張治俊,羅辭勇,張帆等. 采用振蕩參數策略的粒子群優化算法[J].重慶大學學報,2011,34(6): 36-41.ZHANG Z J,LUO C Y,ZHANG F,et al. Particle swarm optimization with oscillating parameter strategy[J]. Journal of Chongqing University,2011,34(6): 36-41.

[11]王爽心,韓芳,朱衡君. 基于改進變尺度混沌優化方法的經濟負荷分配[J]. 中國電機工程學報,2005,25(24): 90-95.WANG S X,HAN F,ZHU H J. Economic load dispatch based on improved mutative scale chaotic optimization[J]. Proceedings of the CSEE,2005,25(24): 90-95.

[12]王瑞琪,張承慧,李珂. 基于改進混沌優化的多目標遺傳算法[J].控制與決策,2011,26(9): 1391-1397.WANG R Q,ZHANG C H,LI K. Multi-objective genetic algorithm based on improved chaotic optimization[J]. Control and Decision,2011,26(9): 1391-1397.

[13]吳浩揚,朱長純,常炳國等. 基于種群過早收斂程度定量分析的改進自適應遺傳算法[J].西安交通大學學報,1999,33(11): 27-30.WU H Y,ZHU C C,CHANG B G,et al. Improved adaptive genetic algorithm based on the quantificational analysis of swarm premature convergence degree[J]. Journal of Xi'an Jiaotong University,1999,33(11): 27-30.

[14]劉洪波,王秀坤,譚國真. 粒子群優化算法的收斂性分析及其混沌改進算法[J]. 控制與決策,2006,21(6): 636-640.LIU H B ,WANG X K,TAN G Z. Convergence analysis of particle swarm optimization and its improved algorithm based on chaos[J].Control and Decision,2006,21(6): 636-640.

[15]段其昌,黃大煒,雷蕾. 帶擴展記憶的粒子群優化算法仿真分析[J]. 控制與決策,2011,26(7): 1087-1100.DUAN Q C,HUANG D W,LEI L. Simulation analysis of particle swarm optimization algorithm with extended memory[J]. Control and Decision,2011,26(7): 1087-1100.