一種快速自適應粒子群算法

劉生建　羅林　楊艷

摘 要：為了解決標準粒子群優化算法（SPSO）不能適應復雜非線性優化過程的問題，提出了一種動態改變慣性權重的快速自適應粒子群優化算法（QAPSO），直接利用群粒子的位置分布情況控制粒子飛行的慣性權重，借助于個體最優位置和全局最優位置的平均作用避免粒子陷入局部最優。通過多個基準函數仿真結果表明，在不引入額外設計及增加實現復雜度的前提下，相對于SPOS等經典算法，QAPSO在收斂速度、最優解精度等方面獲得了大幅提升，尤其對于多峰函數效果更明顯。

關鍵詞：粒子群算法；均值粒子群算法；快速自適應

DOI：10.11907/rjdk.171514

中圖分類號：TP312 文獻標識碼：A 文章編號：1672-7800（2017）009-0042-04

Abstract：A quickly adaptive particle swarm optimization algorithm （QAPSO） with dynamically changing inertia weight was presented to solve the problem that the Standard Particle Swarm Optimization algorithm （SPSO） cannot adapt to the complex and nonlinear optimization process.The QAPSO evaluates the population distribution， and automatic control inertia weight. By using the mean of the optimal individual position and the global optimal position， the best global particle can jump out of the local optima. The QAPSO has comprehensively been evaluated based on benchmark functions. Results show that QAPSO substantially enhances the performance of paradigm such as the SPSO in terms of convergence speed， solution accuracy without introducing an additional design or implementation complexity， especially for multimodal functions.

Key Words：swarm intelligence optimizationalgorithm； mean swarm optimization algorithm； inertia weight adaptability

0 引言

自蟻群算法（Ant Colony Optimization ， ACO）成功應用于旅行商問題（TSP）之后[1]，仿生群智能研究開始迅速發展，先后出現了粒子群、蜂群、人工魚群、蝙蝠群、狼群、螢火蟲等主要解決連續問題的優化算法。

Kennedy和Eberhart在1995年提出了來源于鳥群等生物種群覓食行為的粒子群優化算法（Particle Swarm Optimizer， PSO）[2-3]，由于概念簡單，實現容易，且只有少數參數需要調整，所以PSO算法發展迅速，并廣泛應用于函數尋優、神經網絡訓練、模式分類、模糊系統控制等領域。雖然PSO相比魚群算法等有較強的全局搜索能力，但還是容易陷入局部極值，不易收斂到全局最優。所以出現了一些改進的PSO算法。例如Shi Y等[4]提出了線性遞減權值（LDIW）策略；Kusum Deep等[5]提出均值粒子群優化方法（MPSO）；Zhan Z H等[6]提出了自適應粒子群優化算法等。

本文主要對經典粒子群算法的性能及問題進行分析，并針對收斂精度低和收斂速度慢的問題，在均值粒子群算法基礎上，根據粒子間的距離函數動態調整算法中的慣性權重，合理調整粒子飛行速度。當最優粒子和其它粒子位置相距較遠時，設置較大的慣性系數，由此解決函數尋優過程中探索和開發之間的矛盾。實驗仿真結果表明，本文提出的改進算法性能有了明顯提高，具有相對收斂速度快、精度高等優點。

1 標準粒子群優化算法

設N個粒子組成一個群，其中第i個粒子的位置表示為一個D維的矢量xi=（xi1，xi2，…，xid），第i個粒子的歷史最優位置為pi=（pi1，pi2，…，pid），整個粒子群迄今為止搜索到的最好位置記為pg=（pg1，pg2，…，pgd）。第i個粒子的速度vi=（vi1，vi2，…，vid）。粒子群算法基于迭代思想，粒子按如下公式（1）、（2）調整自己的相應位置[7]：vk+1id=ω*vkid+c1*r1*（pkid-xkid）+

c2*r2*（pkgd-xkid）

（1）

xk+1id=xkid+vk+1idxid∈[xd-min，xd-max]

（2） 其中，1≤i≤N（N為種群個體總數），1≤d≤D，k為迭代次數，c1和c2是非負數，c1表示粒子個體最優位置的自我影響，而c2則表示群體最優位置的群體影響。r1和r2是[0 ，1]區間的隨機數。ω表示慣性權重因子，在公式（1）中一般是固定值，范圍一般為[0.4，0.9]，可決定粒子先前速度對目前運動的影響程度，從而起到平衡算法全局搜索和局部搜索能力的作用。當粒子速度較大時，飛行較快，有利于全局勘探，但有可能超過最優解；反之則有利于局部開發。endprint

粒子在解空間內不斷跟蹤個體極值與全局極值， 直到達到規定的迭代次數或滿足規定的誤差標準為止。在尋優初期，ω應取0.9～1.4，然后根據迭代次數線性減少到0.4，公式如下：ω=ωmax-（ωmax-ωmin）ttmax

（3） 其中，t表示目前的迭代次數，tmax表示設定的最大迭代次數，ωmax表示最大慣性權重因子，ωmin表示最小慣性權重因子。

也可以從物理含義上來解釋公式（1），一個單位質量的粒子在單位時間上受到來自Pi和Pg兩處吸引力的共同作用，從而引起加速度變化。加速度變化導致速度改變，最終改變粒子所處位置。本文將ω固定的PSO簡稱為SPSO，而依據公式（3）計算的PSO簡稱為LPSO，以對算法性能進行對比分析。

2 均值粒子群優化算法

與基本粒子群形成對比的是，均值粒子群優化算法（MPSO）速度更新公式中用線性組合pkid+pkgd2和pkid-pkgd2取代了pkid和pkgd。因此，速度更新公式（1）轉換為公式（4）：vk+1id=ω*vkid+c1*r1*（pkid+pkgd2-xkid）+

c2*r2*（pkid-pkgd2-xkid）

（4） 其中等式中的第一項與公式（1）含義相同；第二項與矢量（pkid+pkgd2-xkid）成比例變化，它吸引粒子由當前位置方向指向全局最優位置和粒子個體最優位置的平均位置方向；第三項與矢量（pkid-pkgd2-xkid）成比例變化，它吸引粒子由當前位置方向指向粒子個體最優位置方向和全局最優位置負方向的平均位置方向。其它更新和參數設置與基本粒子群算法相同。

3 快速自適應粒子群算法（QAPSO）

3.1 基本思想

計算現有粒子群中每個粒子距離其它粒子的距離因子di，現有粒子群中適應度最高的粒子，設其距離因子為dg，距離因子的最小值為dmin，最大值為dmax，計算粒子群的分布信息因子f。f值為1表示最優粒子遠離其它粒子，直接將下一次迭代的慣性權重設置為f值，即可合理控制其它粒子飛向最優位置的速度。

粒子的距離因子如公式（5）所示：di=1N-1∑Nj=1，j≠i∑Dk=1xik-xjk

（5） 公式（5）也可使用歐氏距離，但采用曼哈頓距離計算量較少。

粒子群的分布信息因子如公式（6）所示：f=dg-dmindmax-dminf∈[0，1]

（6）

ωk+1i=f

（7） 最優粒子和其它粒子之間的位置關系主要有3種情況，如圖1所示。

圖1（a）表示算法初期，所有粒子隨機分布，最優粒子與其它粒子差別不大，dg≈di，粒子群處于勘探階段；圖1（b）表示其它粒子向當前最優粒子靠攏，dgdi，處于收斂階段；圖1（c）表示出現新的更優位置后，dgdi，其它粒子紛紛跳出原有局部最優位置。

3.2 QAPSO算法描述

Step1：初始化粒子群數目N，在函數定義域內對每個粒子的初始位置和初始速度進行隨機初始化。

Step2：將粒子的pi設置為當前位置，pg設置為初始群體中最佳粒子的位置。

Step3：判斷算是否滿足終止條件，如果滿足，轉Step6；否則執行（4）。

Step4：對粒子群中的所有粒子i執行如下操作：①根據式（2）、（4）更新粒子的速度及位置；②計算粒子i的適應度值fi；③如果fi優于pi的適應度值，則更新pi為粒子i的當前位置；④如果fi優于pg的適應度值，則更新pg為粒子i的當前位置；④根據式（5）計算距離因子di，更新dg、dmin、dmax。

Step5：根據式（6）、（7）計算粒子群的分布信息因子，從而確定下一次迭代慣性權重ω的值。然后回到Step3繼續執行。

Step6：輸出pg，結束算法運行。

4 仿真實驗與數值分析

本文使用Matlab2014b對上述QAPSO算法編寫了仿真程序，同時也針對標準粒子群算法（SPSO）、均值粒子群算法（MPSO）、慣性權重線性遞減粒子群算法（LPSO）在同樣的環境下進行仿真。仿真程序中，粒子群規模N取40，對比算法中加速常數c1和c2為2，固定慣性權重ω取0.729 8。LPSO算法中，ω從0.9線性遞減到0.4。對每個測試函數均進行20次獨立實驗，函數評估精度設為10-15。參考文獻[8]選取了6個測試函數。

單峰函數有：

（1）Rosenbrock 函數。f1（X）=∑D-1i=1[100（xi+1-x2i）2+（xi-1）2]

（8）

-10≤xi≤10 當D=30，X*=（1，…，1）時，其全局最優值f（X*）=0， 尋優成功標準為f（X）≤10。該函數在全局最優位置附近變換十分平緩，當D=2時，該函數分布如圖2所示。很多優化算法很難找到全局最優位置或找到最優值需要的迭代次數較多。

（2）Schwefel′s 函數。f2（X）=∑Di=1xi+∏Di=1xi

（9）

-10≤xi≤10 當D=30，X*=（0，…，0）時，其全局最優值f（X*）=0， 尋優成功標準為f（X）≤0.01。

多單峰函數有：

（3）Dropwave函數。f3（X）=-1+cos（12x1+x2）0.5（x1+x2）+2

（10）

-2≤x1，x2≤2 當X*=（0，0）時，其全局最優值f（X*）= -1，尋優成功標準為f（X）≤-0.99。

（4）Eggcrate函數。該函數的局部峰值很多，當D=2時，該函數分布如圖3所示。f4（X）=x21+x22+25（sin2x1+sin2x2）endprint

（11）

-π≤x1，x2≤π 當X*=（0，0）時，其全局最優值 f（X*）= 0，尋優成功標準為f（X）≤0.01。

（5）Rastrigin函數。f5（X）=∑Di=1[x2i-10cos（2πxi）+10]

（12）

-5.12≤xi≤5.12 當D=30，X*=（0，…，0）時，其全局最優值f（X*）= 0，尋優成功標準為f（X）≤0.01。

（6）Ackley 函數。f6（X）=-20exp（-0.21D∑Di=1x2i）-

exp（1D∑Di=1cos（2πxi））+20+exp（1）

（13）

-32≤xi≤32 當D=30，X*=（0，…，0）時，其全局最優值f（X*）= 0，尋優成功標準為f（X）≤0.01。

表1～表6分別給出了6個函數在Intel Xeon E3-1230V2和8G DDR3內存、128G固態硬盤計算機上運行計算的結果比較，所有算法的最大迭代次數均為200。

從表1～表6中可以看出，QAPSO除單峰函數f1和其它優化算法一樣均未成功找到最優值外，其它函數尋優精度和時間都明顯優于LPSO、MPSO、SPSO，尤其是在處理變化劇烈的多峰函數（f4、f5等）時。LPSO和MPSO算法性能相差不大，SPSO表現最差。在收斂速度上，QAPSO與LPSO、MPSO、SPSO相比有明顯優勢，收斂時間大大縮短。由于收斂速度差別較大，所以圖中的橫坐標迭代次數從20開始計數，以避免縱坐標函數值差距過大。從圖2、圖3可以明顯看出，算法總體性能表現為：QAPSO>MPSO>LPSO>SPSO。

5 原因分析

由表1可知，單峰函數f1的尋優能力不太理想，其原因是函數值在最優位置區域內變化十分緩慢，各粒子的函數值非常接近，直接導致f取值接近0。QAPSO直接使用f作為慣性系數，所以使得粒子失去慣性作用。

由于SPSO采用固定慣性權重策略，在前期探索解空間時能力不強，而在后期由于慣性較大，又缺乏局部開發能力，很難搜索到最優解；LPSO則在前期加強了勘探能力，在后期采用較小的慣性權重，增強了局部尋優能力；MPSO則考慮到當前個體最優和群體最優位置對粒子群可能產生的“誤導”，增強了粒子跳出局部最優的能力；而QAPSO進一步使用群體分布因子來動態調整下一次迭代的慣性權重，從而在多峰函數的尋優過程中表現出較強的適應能力。圖4、圖5表示QAPSO、SPSO對f4尋優過程中群分布因子的變化過程，可看出在迭代后期，SPSO算法過早收斂到了局部最優值，群個體趨向相同位置，減少了群體多樣性。反之，QAPSO則在整個過程中一直充分保持了群體多樣性。

6 結語

本文提出了一種基于粒子群分布因子的均值粒子群改進優化算法，實驗結果表明，與標準粒子群算法、線性改變權重粒子群優化算法、均值粒子群算法相比，本文算法的收斂速度快、精度較高。本文以種群位置分布因子作為慣性權重，平衡了算法的全局探索和局部開發能力，使粒子跳出局部最優束縛。6個函數優化的仿真結果表明， 本文算法在成功率、平均最優值、收斂時間上都有很大改善，特別對于多峰函數，算法性能的改善更為明顯。對于單峰函數，可繼續進行研究改進，一種簡單策略是在發現最優值變化緩慢時切換為標準粒子群方法，從而擴大算法的使用范圍。

參考文獻：

[1] DORTGO M， MANIEZZO V， COLORNI A. Ant system： optimization by a colony cooperating agents[J]. IEEE Trans. on Systems， Man， and Cybernetics Part B： Cybernetics，1996，26（1）：29-41.

[2] KENNEDY J， EBERHART R. Particle swarm optimization[C]. International Conference on Neural Networks，Perth， Australia： IEEE，1995：1942-1948.

[3] EBERHART R C， KENNEDY J. A new optimizer using particle swarm theory[J]. Institute of Electrical and Electronics Engineers，1995（10）：39-43.

[4] SHI Y， EBERHART R. A modified swarm optimizer[C].IEEE International Conference of Evolutionary Computation Anchorage， Alaska： IEEE Press，1998：69-73.

[5] KUSUM DEEP， JAGDISH CHAND BANSAL. Mean particle swarm optimisation for function optimisation[J]. Computational Intelligence Studies，2009（1）：72-92.

[6] ZHANZH， ZHANGJ， LIY， et al. Adaptive particle swarm optimization[J]. IEEE Transactions on Systems Man， and Cybernetics — Part B： Cybernetics，2009，39（6）：1362-1381.

[7] X YAO， YLIU， G M LIN. Evolutionary programming made faster[J] . IEEE Trans. Evol. Comput.，1999（2）：82-102.

[8] SHI Y， EBERHART R. Empirical study of particle swarm optimization[C]. International Conference on Evolutionary Computation，Washington， USA： IEEE，1999：1945-1950.

（責任編輯：黃 健）endprint