一種提高粒子群算法優化性能的方法

李承 許江寧 張文成

（海軍工程大學導航工程系，武漢 430033）

0 引 言

粒子群優化算法[1]（PSO）是由 Kennedy與Eberhart于1995年提出的一種群體智能算法，用來模擬鳥群覓食的過程。PSO概念簡單易懂，收斂速度快且代碼實現容易，在優化及演化計算等領域引起許多學者的關注，成為一種解決非線性優化問題、組合優化問題與混合非線性問題等方面的重要優化工具和優化方法。針對粒子群算法本身存在的不足，學者們提出了很多改進方法[2-7]，通過引入慣性權重的概念，發展出來的標準粒子群算法成為最通用的一種。標準粒子群算法在函數優化、神經網絡訓練、模式分類和模糊控制等方面得到了廣泛的應用，國內相關研究則始于2001年。

本文提出的利用算法的初始化策略提高算法的性能，并不改變算法的尋優策略和基本原理，因而對各種改進的粒子群算法有普適性。經實驗仿真證明，該方法能夠改善幾種改進粒子群算法的尋優成功率和收斂速度，明顯提高了算法性能。

1 標準粒子群優化算法概述

粒子群優化方法提出之后，有很多學者都對基本算法進行了大量的研究。針對粒子群算法容易陷入局部最優的問題，提出了很多的改進方法。Shi與Eberhart提出了帶慣性權重的粒子群算法，此種改進方法被學者稱為標準粒子群算法[2-4]（Standard Particle Swarm Optimization，SPSO），是目前粒子群算法研究和改進的基礎。設一個D維目標空間，群體規模為 m，xi=(zi1,zi2,…,ziD)為第i個粒子的D維位置矢量，vi=(vi1,vi2,…,viD)為粒子i的D維速度矢量，pBesti是粒子當前最優位置，gBesti是群當前最優位置，SPSO算法的可表示為：

其中，i=1,2,…,m，d=1,2,…,D。慣性權重ω作為慣性部分，可以權衡算法全局能力和局部能力。r1、r2是[0,1]之間的隨機數，用來保持群體的多樣性。c1、c2被稱為學習因子，代表粒子的自身部分和社會認知部分。

慣性權重的引入使粒子群算法的性能大大提高。SPSO算法的特點是原理簡單，易于實現，需要調整的參數少，也不需要任何的梯度信息，特別是在非線性優化、組合優化和混合整數非線性優化上具有很大的優勢。

2 幾種改進的粒子群優化算法

2.1 線性遞減慣性權重粒子群算法

Shi將慣性權重取值為常數，仿真結果表明，ω在[0.8，1.2]之間時，PSO 算法有更快的收斂速度，而當ω>1.2時，算法則較多地陷入局部極值。由于在一般的全局優化算法中，希望前期具有較高的全局搜索能力，而在后期有較高的開發能力，所以動態慣性權重隨著算法迭代的進行而線性減小，算法的收斂性能得以改善。目前采用較多的慣性權重策略，是 Shi 建議的線性遞減權值(linearly decreasing weight，簡稱 LDW)策略[1]。

式中，ωmax和ωmin是慣性權重的最大值與最小值；kmax和 k分別是最大迭代次數和當前迭代次數。慣性權重取值由式（3）給出，Shi等通過實驗證明，將ω設置為從0.9到0.4線性下降，可以使PSO算法更好的控制全局搜索能力和局部搜索能力，加快了收斂速度，能夠提高算法性能。目前這種慣性權重線性遞減策略應用最為廣泛，除此之外還有很多學者提出多種不同慣性權重策略，如線性微分遞減策略、帶閥值的非線性遞減策略、非線性動態改進慣性權重策略、基于正切和反正切函數的慣性權重改進策略和模型調整ω的策略等，這些改進都使算法性能在不同方面有所提高。

通過調整慣性權重可以改進算法的性能，ω的大小決定了算法的全局搜索能力和局部搜索能力。ω較大則算法全局搜索能力強，ω較小則算法局部開發能力強，因此控制ω是改進算法的一種重要途徑。

2.2 自適應慣性權重粒子群算法

APSO算法的基本思想是通過追蹤粒子當前目標適應值和全局最優值，控制每個粒子的慣性權重。離當前最優解遠的粒子獲得的慣性權重值就大，從而加快粒子的飛行速度及算法的開拓能力；而離當前最優解近的粒子獲得的慣性權重值就小，從而增加粒子的發掘能力。自適應慣性權重策略可由式（4）給出：

3 利用初始化提高算法性能

3.1 初始化策略

在對各種改進的粒子群優化算法進行大量實驗測試過程中，發現了一些對算法尋優能力有影響的其他因素，比如粒子群位置的初始化和求解問題的維數。各種粒子群算法一般對粒子初始位置和速度沒有特殊要求，但是在已知優化問題的搜索范圍時，可以通過調整粒子初始位置和速度達到提高算法收斂速度的目的。

經過大量實驗發現，對于限定搜索范圍的優化問題，在粒子初始化時以位于搜索空間內的隨機數對其初始位置賦值，這樣既縮小了粒子起飛時到最優位置的距離，又保證了粒子群在搜索空間內充分發散，可以節約飛行時間，并提高尋優能力。因此，在已知算法搜索范圍的情況下，本文用 xmax×rand()或者 xmax/2×rand()代替 randn()對粒子的初始位置進行賦值，用 vmax×rand()代替randn()對粒子初始化粒子速度。

3.2 實驗驗證

為了更好的反應粒子位置新的初始化策略對算法性能的影響，實驗采用給定最大迭代次數和最優解的模式，以算法精確找到最優解為終止條件，執行測試算法。當達到最大迭代次數時或達到最大迭代次數前，算法找到最優解，則認為算法尋優成功。改進算法初始化策略的目的是提高算法的尋優能力，即算法搜索最優解的成功率、收斂速度和準確度。因此采用如下指標[8]：搜索成功率、平均迭代次數和平均最優適應值。

搜索成功率：進行T次實驗，如果有t次實驗成功，則成功率可表示為t/T×100%，此處所說的搜索成功是指成功搜索到精確解，不是表示算法的收斂概率。

平均迭代次數：T次實驗中，所有成功實驗迭代次數算術平均值。

平均最優適應值：T次實驗所得目標函數最優值的算術平均值。

標準差：T次實驗中算法所得最優解的標準差。

表示算法尋優結果的斂散性；選取一個典型單峰函數 Sphere函數和一個典型多峰函數 Rastrigrin函數，測試不同改進粒子群算法采用本文提出的初始化方法時的性能。

(1)Sphere函數

(2)Rastrigrin函數

Sphere函數是非線性對稱的單峰函數，不同維之間是可分離的。Rastrigrin函數是非線性多極值函數，存在大量按余弦排列的、很深的局部最優點。變量之間無任何相關性，其局部最優點隨著余弦波動，很容易使算法陷入到局部最優點，而得不到全局最優解。

測試時不仿選取LWPSO和APSO兩種算法，分別將其初始化策略改進前后的算法性能進行對比，進行 10次運算求平均值。令問題維度為D=20，種群規模M=30，最大迭代次數為N=2000，學習因子c1=2，c2=2，測試結果見表1。

為了更直觀的反映不同算法的性能，圖 1～圖4分別給出了LWPSO和APSO算法初始化策略改進前后，對文中兩個函數進行測試時的平均適應度值收斂情況（為了便于觀察只給出了迭代早期變化明顯的部分）。

圖1和圖2所示為LWPSO算法采用不同初始化策略時，對Sphere函數和Rastrigrin函數的尋優結果。

圖3和圖4所示為 APSO算法采用不同初始化策略時，對Sphere函數和Rastrigrin函數的尋優結果。

表1 Sphere函數測試結果對比

表2 Rastrigrin函數測試結果對比

圖1 LWPSO對Sphere函數的優化過程

圖2 LWPSO對Rastrigrin函數的優化過程

圖3 APSO對Sphere函數的優化過程

圖4 APSO 對Rastrigrin函數的優化過程

由表1、表2和圖1-圖4的結果可以看出，在本文提出的算法初始化策略下，LWPSO和APSO算法對典型單峰函數和多峰函數尋優時，算法的收斂速度和搜索成功率，都得到了大大提高。

4 結論

本文針對解決控制領域優化問題的粒子群算法存在的問題，提出了一種算法的初始化策略，以提高優化算法的性能。通過 LWPSO和 APSO算法對典型函數的測試，結果證明在本文提出的初始化策略下，算法收斂速度、搜索成功率和搜索精度得到了大大提高，這說明本文提出的方法是有效的。

[1]紀震，廖惠連，吳青華. 粒子群優化算法及應用[M].北京: 科學出版社, 2009:16-80.

[2]Zhang L P,Yu H J, Hu S X. A new approach to improve particle swarm optimization [C]. Lecture Notes in Computer Science. Chicago: Springer Verlag,2006: 1036-1043.

[3]鄧愛萍，王會芳. 動態改變慣性權重的自適應粒子群算法[J]. 計算機工程與設計, 2010, 31(13):3062-3065.

[4]潘峰,陳杰,甘明剛等. 粒子群優化算法模型分析[J].自動化學報, 2006, 32(3): 368-377.

[5]林川,馮全源. 粒子群優化算法的信息共享策略[J].西南交通大學學報, 2009, 44(3): 437-441.

[6]張朝龍，江巨浪，江善和等. 一種自適應混合粒子群優化算法及其應用[J]. 計算機應用研究, 2011,28(5): 1696-1698.

[7]張頂學. 遺傳算法與粒子群算法的改進及應用[D].武漢：華中科技大學， 2007.

[8]F V den Bergh, A P Engelbrecht. A study of particle swarm optimization particle trajectories [J]. Inf. Sci.,2006, 176(8): 937-971.