基于糾錯(cuò)機(jī)制的粒子群優(yōu)化算法*

， ，

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

0 引 言

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

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

1 標(biāo)準(zhǔn)PSO概述

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

標(biāo)準(zhǔn)PSO算法[10]先對一群隨機(jī)粒子初始化，在n維搜索空間中，由m個(gè)粒子組成的一個(gè)種群表示為X=(x1,x2,…,xm)。其中,第i個(gè)粒子的位置為Xi=(xi1,xi2,…,xin)，速度為Vi=(vi1,vi2,…,vin)，自身最優(yōu)位置為Pi=(pi1,pi2,…,pin)，全局最優(yōu)位置表示為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表示當(dāng)前進(jìn)化代數(shù)；c1，c2為學(xué)習(xí)因子，且為常數(shù)，c1用來調(diào)節(jié)微粒飛向自身最好位置的步長，c2則用來調(diào)節(jié)微粒向全局最好位置方向飛行的步長，根據(jù)經(jīng)驗(yàn)通常在0～2之間取值；w為慣性因子，使微粒保持運(yùn)動慣性的同時(shí)具有探索新區(qū)域的能力；r1，r2分別為[0,1]之間的隨機(jī)數(shù)；為了降低在進(jìn)化過程中微粒飛離搜索空間的可能性，速度Vi一般需限定于一定的范圍之內(nèi)，即Vi在(Vmin，Vmax)之間取值，一般情況下取變量空間的20 %～40 %。

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

2 MPSO算法

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

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

此方法的優(yōu)點(diǎn)在于，通過引入一種簡單的糾錯(cuò)機(jī)制提高了粒子群算法的收斂速度和收斂精度，降低早熟收斂的比率，提高了解的質(zhì)量。在進(jìn)一步強(qiáng)化算法的局部搜索能力的同時(shí)，算法的全局搜索能力也得到了一定的提高。

3 算法步驟

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

1)初始化種群，包括最大進(jìn)化代數(shù)、種群規(guī)模大小、學(xué)習(xí)因子等參數(shù)的初始化，以及粒子的速度、位置，每個(gè)粒子的歷史最優(yōu)值和整個(gè)群體的歷史最優(yōu)值的初始化；

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

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

4)根據(jù)粒子當(dāng)前的適應(yīng)值更新粒子的歷史最優(yōu)值和整個(gè)群體的歷史最優(yōu)值，即個(gè)體極值和全體極值；

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

4 實(shí)驗(yàn)結(jié)果分析

下面將通過3個(gè)標(biāo)準(zhǔn)測試函數(shù)來驗(yàn)證文中算法的性能：

1)Sphere函數(shù)

xi∈[-100,100].

(3)

2)Ratrigrin函數(shù)

xi∈[-5.12,5.12].

(4)

3)Rosenbrock函數(shù)

xi∈[-30,30].

(5)

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

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

為了證明本文提出的算法的有效性，取3個(gè)函數(shù)在種群規(guī)模為50，維數(shù)為20的情況下的實(shí)驗(yàn)結(jié)果，如圖1～圖3所示。

圖1 Sphere函數(shù)對比圖

表1 Sphere，Ratrigrin，Rosenbrock函數(shù)最優(yōu)值的均值

圖2 Ratrigrin函數(shù)對比圖

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

圖3 Rosenbrock對比圖

5 結(jié)束語

本文針對標(biāo)準(zhǔn)PSO算法存在的收斂速度慢與早熟等現(xiàn)象，提出了一種MPSO算法。為了測試算法的性能，本文選取Sphere，Ratrigrin，Rosenbrock三個(gè)標(biāo)準(zhǔn)測試函數(shù)進(jìn)行仿真計(jì)算，并將標(biāo)準(zhǔn)PSO,MPSO兩種算法的優(yōu)化結(jié)果進(jìn)行比較，結(jié)果表明：MPSO算法相對于標(biāo)準(zhǔn)PSO算法的收斂性能有顯著提高，且具有較快的收斂速度。

參考文獻(xiàn):

[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ìn)的粒子群優(yōu)化算法[J].計(jì)算機(jī)應(yīng)用與軟件，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ìn)粒子群算法求解柔性作業(yè)車間批量調(diào)度問題[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] 紀(jì) 震，廖惠連，吳青華.粒子群算法及應(yīng)用[M].北京:科學(xué)出版社,2009:72-76.