一種改進的變參數粒子群算法

檀蕊蓮，柏 鵬，李 哲，盧 虎，王 澈

(1.西安武警工程大學，陜西西安710086;2.空軍工程大學，陜西 西安710051)

粒子群優(yōu)化算法(PSO)是由美國電氣工程師Eberhart和社會心理學家Kennedy基于群鳥覓食提出來的一種智能算法［1-2］。由于該算法算法簡單、所需參數少、易于實現(xiàn)等優(yōu)點從而廣泛應用于科學和工程領域［3-4］。由于算法參數較少，也使得其容易陷入局部最優(yōu)和維數災難。針對這些問題，尤其是針對算法參數調整方面，相關學者針提出了很多改進算法［5-7］。其中，Shi和Eberhart最早引入了慣性權重的概念［5］，即后來普遍認為的標準粒子群算法(SPSO)，這也為后續(xù)學者在參數調整方面的研究奠定了基礎;Clerc提出一種帶收縮因子的粒子群算法(CPSO)［6］，使用收縮因子可以通過平衡局部開發(fā)能力與全局搜索能力從而改善粒子群算法收斂性能。然而，對于如何尋求更合適該算法的參數問題仍然是研究的重點和難點。本文在前人研究的基礎上，提出了一種新的參數調整方案，將SPSO算法和CPSO算法的精華部分進行融合，根據粒子運動的特點進行參數調整，對速度更新公式各項配以相應的權重因子，從而提高了算法的尋優(yōu)性能。對三個基準函數進行測試，并與已有SPSO算法和CPSO算法進行對比，證明了本文所提算法在尋優(yōu)精度和執(zhí)行性能方面都具有較好的性能，在求解高維函數優(yōu)化問題時亦能有效避免維數災難。

1 標準粒子群算法

假設由m個粒子組成種群X=(X1，X2，…，Xm)，則在一個d維的搜索空間中，問題的一個可能解即為第i個粒子在d維搜索空間的位置向量 Xi=(Xi1，Xi2，…，Xid)T。若以Pi=(Pi1，Pi2，…，Pid)T代表粒子i所經歷的最好位置，Pg=(Pg1，Pg2，…，Pgd)T代表種群的全局最優(yōu)位置，Vi=(Vi1，Vi2，…，Vid)T代表第i個粒子在d維空間的飛行速度，則在每次迭代過程中，粒子將按式(1)、式(2)更新自身的速度和位置

式中:ω為慣性權重;i=1，2…，n;Vid為粒子的速度;c1和c2稱為加速因子，通常取2.0;r1和r2為均勻分布的隨機數，分布于［0，1］之間。加入慣性權重ω的PSO算法即為標準粒子群算法(SPSO)，由于其參數較少，操作簡單，尋優(yōu)效果較好而得到廣泛應用。按照Shi和Eberhart最早提出的概念，慣性權重ω按式(3)線性遞減

式中:ωstart為初始慣性權重;ωend為迭代到最大次數時的慣性權重;k為當前迭代次數;Kmax為最大迭代次數。然而，SPSO算法可調整參數過少，使得該算法的數學基礎相對薄弱，當面對非線性函數或者是多維函數的優(yōu)化問題時，往往過早陷入局部最優(yōu)，尋優(yōu)效果并不理想。

2 改進的PSO算法

2.1 帶約束因子的PSO算法

Clerc提出的帶收縮因子的粒子群算法(CPSO)定義如下

式中:CPSO 算法中Clerc設定l=4.1，c1=c2=2.05，則收縮因子 χ為 0.729，后兩項系數為 0.729 × 2.05ri=1.494 45ri，相當于速度跟新公式中所有的項都乘一樣的權重因子，并未考慮到各個項的單獨作用，雖然算法在收斂性方面有所改善，但是必須預先對算法進行限定，而且必須針對一定的函數，否則在給定的迭代次數下很難找到全局最優(yōu)，應用范圍受限。

2.2 改進的PSO算法

如何選取合適的參數從而使得算法具有更好的收斂性是研究的熱點和難點，迭代初期本文期望得到較大的慣性權重使得算法保存較強的全局搜索能力，而迭代后期則期望得到較小的慣性權重，有利于算法進行更精確的局部搜索。文獻［6］指出通過設定約束因子可以得到更好的收斂性能，然而實際上期望的是在全局最優(yōu)位置一定的情況下粒子的個體最優(yōu)位置更新得更快，從而使得算法的局部搜索能力與全局搜索能力相平衡，達到更好的尋優(yōu)效果。綜合SPSO和CPSO的優(yōu)缺點，本文提出一種新的參數調整策略，速度更新公式各項配以不同的權重因子。其表達式如下

式(7)第一部分是對當前速度的調整，后兩部分是對粒子個體與全局位置的調整。式(7)第一部分保持SPSO算法的慣性權重因子，可以使得粒子搜索速度加快;第三部分保持CPSO算法的約束因子，可以保證粒子具有更好的全局尋優(yōu)性能;第二部分則融入了SPSO算法和CPSO算法的精華部分，權重因子為慣性權重因子與約束因子相乘，既達到了約束的目的，又可以保證粒子個體更新按前期速度加速更新，從而使得個體尋優(yōu)和全局尋優(yōu)達到平衡。

2.3 算法實現(xiàn)

步驟1:初始化參數。設置慣性權重ω的取值范圍，隨機因子r1和r2，最大迭代次數Kmax，初始速度Vid，空間維數D，并在所定義的搜索空間中隨機生成m個粒子組成初始種群。

步驟2:計算種群中每個粒子的適應度函數值。

步驟3:根據式(7)更新各粒子的飛行速度，根據更新的飛行速度按照式(2)更新各粒子的位置，從而產生新的種群，實現(xiàn)個體極值和群體極值的更新。

步驟4:判斷是否滿足終止條件，若滿足，則算法結束，輸出最優(yōu)解;否則轉入步驟2，直到達到最大迭代次數才終止。

3 仿真實驗及性能分析

3.1 測試函數

為檢驗本文所提算法的性能，選擇3個較常用于測試優(yōu)化算法性能的基準函數進行測試，各個測試函數的表達式及其搜索空間如表1所示。其中，Sphere函數為非線性對稱單峰函數，極易實現(xiàn)，主要用于測試算法的尋優(yōu)精度;Rosenbrock函數是很難極小化的病態(tài)二次函數，主要用于評價優(yōu)化算法的執(zhí)行性能;Rastrigrin函數為典型的具有大量局部最優(yōu)點的復雜多峰函數，極易陷入局部最優(yōu)，主要用于測試算法的局部尋優(yōu)能力，3個基準測試函數的最優(yōu)解均為0。

表1 測試函數

3.2 仿真結果與分析

粒子種群規(guī)模分別取20，40，60;最大迭代次數在維數為10，20，30 維時分別對應300，600，900 次;慣性權重ωstart=0.9，ωend=0.4;每個基準測試函數獨立在SPSO 算法，CPSO算法，本文算法中各運行100次，分別求出最小適應度函數的平均值最優(yōu)值作為評價標準。表2～表4為各基準函數在這3種算法中的測試結果。

表2 Sphere函數平均最優(yōu)解比較

表3 Rosenbrock函數平均最優(yōu)解比較

表4 Rastrigrin函數平均最優(yōu)解比較

由表2數據對比可以看出，在對單峰函數f1(x)的優(yōu)化中，當種群規(guī)模為20時，空間維數較小則3種算法的平均最優(yōu)解都接近于理論最優(yōu)解，隨著空間維數和迭代次數的增加，尋優(yōu)難度相應增大，本文算法在相同空間維數和迭代次數下取得了更接近理論最優(yōu)值的數值，隨著種群規(guī)模的增加到60，本文算法比SPSO算法和CPSO算法的最優(yōu)解低了一個數量級，證明本文算法在求解多維函數時具有更好的尋優(yōu)精度。

由表3數據對比可以看出，雖然f2(x)為很難極小化的病態(tài)二次函數，但是當空間維數較小時，本文算法相較于SPSO算法和CPSO算法，尋優(yōu)結果更貼近與理論最優(yōu)值，當空間維數由10增加到30，本文算法也表現(xiàn)出更好的尋優(yōu)性能，隨著種群規(guī)模的增加，尋優(yōu)精度更好，證明本文算法在求解多維函數時具有更好的尋優(yōu)執(zhí)行能力。

由表4數據對比可以看出，對于具有大量局部最優(yōu)點的復雜多峰函數，CPSO算法在空間維數增加時局部尋優(yōu)能力逐漸變弱，而SPSO算法在種群規(guī)模增加時尋優(yōu)結果變動不大，證明極有可能以及陷入局部最優(yōu)而無法跳出，而本文所提算法則隨著種群規(guī)模的增加取得了更好的尋優(yōu)數值，證明本文所提算法在求解多維函數時局部尋優(yōu)能力更強，整體性能更好。

為了更直觀反映算法的尋優(yōu)效果，將SPSO、CPSO和本文算法在粒子種群規(guī)模為60，解空間為30維時進行比較，3種算法對測試函數的收斂曲線如圖1所示。由圖1可見，本文算法在解決多維函數優(yōu)化問題時亦能取得較好的收斂性能，有效避免了維數災難，再次證明了本文所提算法的有效性。

4 結語

本文提出了一種改進的變參數粒子群算法，該算法在SPSO算法和CPSO算法的基礎上做出改進，融合二者的精華部分，將速度更新公式做各項根據其運動特性配以不同的權重因子，算法操作簡單，易于實現(xiàn)。通過3個基準測試函數的仿真結果表明，本文所提算法具有更好的尋優(yōu)精度和執(zhí)行能力，在求解多維函數優(yōu)化問題時，亦能表現(xiàn)出優(yōu)越的收斂性能。

［1］PEREZ R，BEHDINAN K.Particle swarm approach for structural design optimization［J］. Computers ＆ Structures，2007，85(19/20):1579-1588.

［2］COELHO L，SIERAKOWSKI C.A software tool for teaching of particle swarm optimization fundamentals［J］.Advances in Engineering Software，2008，39(11):877-887.

［3］FAN S，ZAHARA E.A hybrid simplex search and particle swarm optimization for unconstrained optimization［J］.European Journal of Operational Research，2007，181(2):527-548.

［4］LI X.Niching without niching paramenters:particle swarm optimization using a ring topology［J］.IEEE Trans.Evolutionary Computation，2010，14(1):150-169.

［5］SHI Y，EBERHART R.A modified particle swarm optimizer［C］//Proc.IEEE Enternational Conference on Evolutionary Computation.Anchorage，AK:IEEE Press，1998:69-73.

［6］CLERC M.The swarm and the queen:towards a deterministic and adaptive particle swarm optimization［C］//Proc.Congress of Evolutionary Computation.Washington:IEEE Press，1999:1951-1957.

［7］李殷，李飛.基于量子粒子群優(yōu)化算法的圖像矢量量化碼書設計［J］.電視技術，2012，36(17):54-56.