基于糾錯機制的粒子群優化算法*

， ，

(1.太原理工大學 信息與工程學院，山西 太原 030024; 2.太原理工大學 電氣與動力工程學院，山西 太原 030024)

0 引 言

粒子群優化(PSO)算法[1～3]是由美國社會心理學家Kennedy J和電氣工程師 Eberhart R C于1995年共同提出的一種新的全局優化算法，起源于自然界鳥類和魚群的社會性行為的模擬。由于概念簡單、參數少、易于實現等優點，PSO算法一經提出便引起了廣泛的關注，應用于許多科學和實際工程領域[4～9]。

研究表明，PSO算法的搜索過程中存在“走彎路”現象，因此，會導致收斂速度慢，甚至不收斂。針對該缺點，在前人研究的基礎上，提出一種基于糾錯機制的粒子群優化(MPSO)算法。該算法通過建立一種簡單的糾錯機制對粒子每一步的進化方向進行判斷，如果出現倒退現象，則使粒子向完全相反的方向前進，這樣不僅降低了粒子在進化過程中出錯的概率，同時也保持了PSO算法的多樣性，從而有效地提高了PSO算法的收斂速度和搜索能力。

1 標準PSO概述

PSO算法中，每個粒子都被理解為解空間的一個解，通過事先設定的一個適應度函數來確定粒子的好壞。每個粒子將由一個速度變量來決定其在相應解空間中的飛行方向和距離。根據粒子本身的最優位置和群體找到的最優位置來動態調整自身的飛行方向和速度，通過粒子間的相互作用使其飛向最優粒子。

標準PSO算法[10]先對一群隨機粒子初始化，在n維搜索空間中，由m個粒子組成的一個種群表示為X=(x1,x2,…,xm)。其中,第i個粒子的位置為Xi=(xi1,xi2,…,xin)，速度為Vi=(vi1,vi2,…,vin)，自身最優位置為Pi=(pi1,pi2,…,pin)，全局最優位置表示為Pg=(pg1,pg2,…,pgn)。

粒子速度和位置更新策略為

V(t+1)=wVi(t)+c1r1(Pi-Xi(t))+c2r2(Pg-

Xi(t)),

(1)

Xi(t+1)=Xi(t)+Vi(t+1),

(2)

式中i=1，2，3，…，n；t表示當前進化代數；c1，c2為學習因子，且為常數，c1用來調節微粒飛向自身最好位置的步長，c2則用來調節微粒向全局最好位置方向飛行的步長，根據經驗通常在0～2之間取值；w為慣性因子，使微粒保持運動慣性的同時具有探索新區域的能力；r1，r2分別為[0,1]之間的隨機數；為了降低在進化過程中微粒飛離搜索空間的可能性，速度Vi一般需限定于一定的范圍之內，即Vi在(Vmin，Vmax)之間取值，一般情況下取變量空間的20 %～40 %。

由式(1)可知，粒子速度的更新由以下三部分構成：第一部分為粒子當前速度對下一刻速度的影響，即基于自身速度進行的慣性運動；第二部分為“自我認知”部分，通過對自身經驗的思考來實現下一步行為的決策；第三部分為“群體認知”部分，依據粒子之前迭代過程中得到的種群經驗，實現微粒間的信息合作與共享。

2 MPSO算法

本文提出的MPSO算法的基本原理是：由于粒子群算法具有隨機搜索的本質，故在粒子進化過程中速度對位移的修正可能使粒子向更靠近全局最優的方向前進，也可能使粒子向背離全局最優的方向前進，即出現倒退現象，這時如果沒有及時糾正，就會出現“走彎路”現象，即粒子向錯誤的方向前進一段時間后再走回正確的方向。為此，在粒子進化過程的每一步均增加一個糾錯機制，只要粒子出現倒退現象就及時糾正，避免了“走彎路”現象，使粒子以更快的速度向全局最優和局部最優靠近。算法設計如下：

在每一次迭代中，對每個粒子當前時刻的速度Vi取反，得到一個新的速度-Vi，分別求得速度Vi和-Vi對應的位置X1和X2，若X2對應的適應度值比X1對應的適應度值好，則用-Vi取代Vi作為該粒子的當前速度，并用X2取代X1作為該粒子的當前位置，且將X2的適應度值取代X1的適應度值；若X2對應的適應度值比X1對應的適應度值差，則該粒子維持原來的速度Vi、位置X1和對應的適應度值。

此方法的優點在于，通過引入一種簡單的糾錯機制提高了粒子群算法的收斂速度和收斂精度，降低早熟收斂的比率，提高了解的質量。在進一步強化算法的局部搜索能力的同時，算法的全局搜索能力也得到了一定的提高。

3 算法步驟

綜上所述，MPSO算法流程描述如下：

1)初始化種群，包括最大進化代數、種群規模大小、學習因子等參數的初始化，以及粒子的速度、位置，每個粒子的歷史最優值和整個群體的歷史最優值的初始化；

2)根據式(1)和式(2)對每個粒子的速度進行更新，并取反得到一個新的速度；

3)根據粒子的當前速度和取反后的速度，分別求取其對應的位置和適應值，通過對這2個適應值的比較，將適應值較好的一方賦給當前粒子；

4)根據粒子當前的適應值更新粒子的歷史最優值和整個群體的歷史最優值，即個體極值和全體極值；

5)判斷是否能夠達到最大進化代數，或能否滿足精度要求，若是滿足，則輸出結果并終止算法；否則，返回步驟(2)重新循環。

4 實驗結果分析

下面將通過3個標準測試函數來驗證文中算法的性能：

1)Sphere函數

xi∈[-100,100].

(3)

2)Ratrigrin函數

xi∈[-5.12,5.12].

(4)

3)Rosenbrock函數

xi∈[-30,30].

(5)

其中，函數1：Sphere函數，為非線性且對稱的單峰函數，其理論上最小值為0；函數2：Ratrigrin函數，為具有大量局部最優的復雜多峰函數，其理論上最小值為0；函數3：Rosenbrock函數，為很難極小化的典型的病態二次函數，理論上最小值為0。

算法參數如下初始化：學習因子取c1=c2=2。慣性權重w從0.9隨進化而線性減少到0.4。為了研究算法的拓展性能，對于每個函數的不同維數(D=20，100)用不同的種群規模(N=30，50，100)來實驗，為了能給出相關性能正確的適應值，把算法連續運行100次求平均值，最大進化代數為2 000次。統計對比數據見表1。

為了證明本文提出的算法的有效性，取3個函數在種群規模為50，維數為20的情況下的實驗結果，如圖1～圖3所示。

圖1 Sphere函數對比圖

表1 Sphere，Ratrigrin，Rosenbrock函數最優值的均值

圖2 Ratrigrin函數對比圖

通過表1、圖1～圖3可以看出：在相同迭代次數下，對所測試的3個函數的MPSO算法總體上能獲得比標準PSO算法更優的結果，而且MPSO算法對于多峰高維函數也具有較好的性能。通過觀察粒子適應值對比圖發現，標準PSO算法出現了早熟收斂情況，MPSO算法對早熟收斂情況有所改善，并且其全局收斂速度明顯快于標準PSO算法。實驗表明，MPSO算法不僅在收斂速度上有所提高，而且提高了粒子群的優化性能，因此證明了算法的性能。

圖3 Rosenbrock對比圖

5 結束語

本文針對標準PSO算法存在的收斂速度慢與早熟等現象，提出了一種MPSO算法。為了測試算法的性能，本文選取Sphere，Ratrigrin，Rosenbrock三個標準測試函數進行仿真計算，并將標準PSO,MPSO兩種算法的優化結果進行比較，結果表明：MPSO算法相對于標準PSO算法的收斂性能有顯著提高，且具有較快的收斂速度。

參考文獻:

[1] Al-Awami Ali T，Zerguine Azzedine，Cled Lahouari．A new modified particle swarm optimization algorithm for adaptive equaliza-tion[J].Digital Signal Processing,2011,21(2):195-207.

[2] Kennedy J,Eberhart R C.Particle swarm optimization[C]∥Proceedings of IEEE International Conference on Neural Networks,Piscataway:IEEE,1995:1492-1498.

[3] 潘 勇，郭曉東.一種基于遺傳算法改進的粒子群優化算法[J].計算機應用與軟件，2011，28(9)：222-224.

[4] Baskar G,Mohan M R.Contingency constrained economic load dispatch using improved particle swarm optimization for security enhancement[J].Electric Power Systems Research,2009,79(4):615-621.

[5] Siahkali H,Vakilian M.Electricity generation scheduling with large-scale wind farms using particle swarm optimization[J].Electric Power Systems Research,2009,79(5):826-836.

[6] Peng Li，Wang Maohai，Du Jiaping，et al.Isolation niches particle swarm optimization applied to traffic lights controlling[C]∥Proceedings of the 48th IEEE Conference,CDC/CCC 2009,2009.

[7] Samanta B,Nataraj C.Use of particle swarm optimization for machinery fault detection[J].Engineering Applications of Artificial Intelligence,2009,22(2):308-316.

[8] 張 靜，王萬良，徐新黎，等.基于改進粒子群算法求解柔性作業車間批量調度問題[J].控制與決策，2012，27(4)：513-518.

[9] Xin Bin,Chen Jie,Peng Zhihong,et al.An adaptive hybrid optimizer based on particle swarm and differential evolution for global optimization[J].Science China Information Sciences,2010,53(5):1869-1919.

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