基于個(gè)體位置變異的粒子群算法

鄭俊觀，王碩禾，齊賽賽，張煥東，張立園

(石家莊鐵道大學(xué) 電氣與電子工程學(xué)院，河北 石家莊 050043)

粒子群優(yōu)化(Particle Swarm Optimization，簡稱PSO)算法是由Jennedy Kennedy et al［1］于1995年提出的一種群體智能算法。該算法通過模擬鳥群隨機(jī)覓食的行為，利用鳥之間的相互協(xié)作使群體達(dá)到最優(yōu)。該算法優(yōu)點(diǎn)是編程簡單，設(shè)置參數(shù)較少，易于和其它算法或者模型相結(jié)合;缺點(diǎn)是易陷入局部最優(yōu)，算法缺乏嚴(yán)格意義上的數(shù)學(xué)證明，算法參數(shù)的設(shè)置根據(jù)經(jīng)驗(yàn)值確定，選擇的參數(shù)不同直接影響算法的跟蹤性能和收斂精度［2］。同時(shí)，該算法已經(jīng)成功應(yīng)用到自然科學(xué)、金融等領(lǐng)域的優(yōu)化問題中［3］。

針對粒子群算法易陷入局部最優(yōu)、收斂速度較慢等問題，國內(nèi)研究人員提出了很多改進(jìn)方法。改進(jìn)的粒子群算法大致可以分為4類:其一，對粒子群初始化的改進(jìn)［4］，不同的初始化方法有不同的效果，對算法的優(yōu)化性能會(huì)產(chǎn)生一定的影響;其二，對粒子群算法的參數(shù)進(jìn)行改進(jìn)［5-6］，其重要參數(shù)包括學(xué)習(xí)因子、慣性權(quán)重等，其值的大小直接與粒子群算法的開發(fā)和搜索能力有關(guān);其三，粒子群算法與其它算法機(jī)制或思想相結(jié)合，形成了許多混合算法，比如變異粒子群算法［7］、免疫粒子群算法［8］、混沌粒子群算法［9］等，混合的粒子群算法具有更好的優(yōu)化性能，是當(dāng)前算法改進(jìn)的一個(gè)重要方向;其四，對粒子種群進(jìn)行改進(jìn)，將種群劃分成若干個(gè)子群［10］，子群之間獨(dú)立進(jìn)化，有利于增強(qiáng)種群的多樣性。

本文介紹了粒子群算法、慣性權(quán)重粒子群算法、變異粒子群算法基本原理及存在的不足。針對文獻(xiàn)［11］中提出的變異粒子群算法存在最終可能不收斂和收斂速度較慢的不足，對其變異概率公式進(jìn)行改進(jìn)。基于個(gè)體位置變異粒子群算法基本思想是為了防止粒子群算法陷入局部最優(yōu)，在粒子群算法中引入變異操作，使粒子的位置以一定的概率接受變異操作。為了驗(yàn)證改進(jìn)算法的有效性，將該算法應(yīng)用于6個(gè)典型復(fù)雜測試函數(shù)中，仿真結(jié)果表明該算法優(yōu)化性能突出，具有較強(qiáng)的全局尋優(yōu)能力和較好的收斂速度。

1 粒子群算法

粒子群算法計(jì)算公式

式中，i代表粒子的序數(shù);k為迭代次數(shù);vki是指迭代k次時(shí)第i個(gè)粒子的速度;vki+1指迭代k+1次時(shí)第i個(gè)粒子的速度;xki是迭代k次時(shí)第i個(gè)粒子的位置;xki+1是迭代k+1次時(shí)第i個(gè)粒子的位置;ω為粒子的慣性權(quán)重;c1、c2為學(xué)習(xí)因子;r1、r2為相互獨(dú)立［0，1］之間的隨機(jī)數(shù)。

在式(1)中速度是由粒子的初始慣性、自我認(rèn)知和社會(huì)認(rèn)知3部分構(gòu)成，這3部分共同決定了粒子的空間搜索能力。在收斂的情況下，由于粒子的趨向同一化造成種群多樣性差，使得迭代后期收斂速度明顯變慢，容易陷入局部最優(yōu)。

2 慣性權(quán)重的粒子群算法

慣性權(quán)重ω是PSO算法中最重要的參數(shù)，它體現(xiàn)粒子繼承先前速度的能力，其值的大小對算法能否收斂具有重要關(guān)系。當(dāng)ω值較大時(shí)，有利于全局搜索;當(dāng)ω值較小時(shí)，有利于局部搜索。為了更好地平衡算法的全局搜索與局部搜索能力，合理設(shè)計(jì)慣性權(quán)重，從而達(dá)到避免陷入局部最優(yōu)。通過改變慣性權(quán)重的粒子群算法稱為慣性權(quán)重粒子群算法(inertia weight particle swarm optimization，IWPSO)［6］。Shi Y提出了線性遞減慣性權(quán)重，其表達(dá)式為

式中，ωstart為初始慣性權(quán)重;ωend為迭代至最大次數(shù)時(shí)的慣性權(quán)重;k為當(dāng)前迭代次數(shù);Tmax為最大迭代次數(shù)。迭代前期有較大的慣性權(quán)重使算法保持了較強(qiáng)的全局搜索能力，而迭代后期較小的慣性權(quán)重有利于算法進(jìn)行更加精準(zhǔn)的局部搜索。隨著研究問題的不同，一些學(xué)者也隨之提出了不同的慣性權(quán)重粒子群算法，比如自適應(yīng)權(quán)重粒子群、隨機(jī)權(quán)重粒子群等。但是，有時(shí)單純地改進(jìn)粒子群算法的參數(shù)，可能會(huì)最終導(dǎo)致粒子群算法不收斂，無法實(shí)現(xiàn)全局尋優(yōu)。

3 基于個(gè)體位置變異的粒子群算法

針對PSO算法存在易陷入局部最優(yōu)的缺點(diǎn)，文獻(xiàn)［11］提出基于變異策略粒子群算法(Mutation Particle Swarm Optimization，簡稱MPSO)。為了解決粒子群算法可能會(huì)出現(xiàn)陷入局部最優(yōu)的現(xiàn)象，將變異操作引入到粒子群算法中，當(dāng)粒子向歷史最優(yōu)粒子靠攏出現(xiàn)嚴(yán)重聚集情況時(shí)，將粒子中符合變異條件的粒子進(jìn)行變異，來增加種群的多樣性，增強(qiáng)粒子全局尋優(yōu)能力。變異操作如下

式中，xki代表第i個(gè)粒子在第k次迭代時(shí)的位置;rand代表隨機(jī)函數(shù);c代表變異因子，取值范圍為所有粒子中最小的定義域;xki+1代表第i個(gè)粒子在第k+1次迭代時(shí)的位置;(bi－ai)代表第i個(gè)粒子的定義域。

粒子是否符合變異條件進(jìn)行變異，取決于變異率pm。文獻(xiàn)［11］變異操作的思想為:在迭代初期主要發(fā)揮粒子群算法自身的特點(diǎn)，采用較小的變異率，隨著迭代次數(shù)的增多，算法的多樣性變差，采用較大的變異率，通過增加種群的變異率，以避免算法陷入局部最優(yōu)。

變異率計(jì)算公式為

式中，pm，min代表最小變異率;pm，max代表最大變異率;k代表當(dāng)前迭代次數(shù);N代表最大迭代次數(shù)。

從式(6)可以得到，隨著迭代次數(shù)的增加，該公式中的變異率逐漸增加，這樣雖然可以提高粒子群算法的全局尋優(yōu)能力，但是在實(shí)際應(yīng)用中可能導(dǎo)致解不收斂［12］。應(yīng)該在迭代初期，采用較大的變異率，增加種群的多樣性，以提高全局尋優(yōu)能力，隨著迭代次數(shù)的增加，變異率逐漸減小，以提高收斂精度。同時(shí)，公式(6)表示的是隨著迭代次數(shù)增多，變異率呈線性增加，PSO搜索過程有著非線性且復(fù)雜度高的特點(diǎn)，使得線性變化的變異率方法不能反映實(shí)際的優(yōu)化要求。

根據(jù)上述分析把式(6)改成

變異率式(6)和式(7)的優(yōu)化曲線如圖1所示。其中A表示式(6)的優(yōu)化曲線，B表示式(7)的優(yōu)化曲線。從曲線B可知，在算法初期為了保持算法的多樣性，設(shè)置較大的變異率，此時(shí)粒子選擇變異的方式概率較大，避免粒子過早陷入局部最優(yōu)解;后期隨著迭代次數(shù)的增加，變異率逐漸減小，粒子選擇PSO更新的概率逐漸加大，當(dāng)變異率降為0時(shí)，粒子不再變異，只會(huì)選擇PSO算法，加快了算法的收斂速度，使更多的粒子向后期的全局最優(yōu)值移動(dòng)，有利于提高算法的收斂精度。由此可見，這樣改進(jìn)后的算法既可以保證前期擴(kuò)大粒子的搜索范圍，又可以保證后期粒子逐漸收斂，不再變異，提高了收斂的精度。

基于個(gè)體位置變異粒子群算法計(jì)算步驟:

步驟1:初始化粒子群中各個(gè)粒子的位置和速度;

步驟2:對各個(gè)粒子的變異率進(jìn)行初始化;

步驟3:計(jì)算各個(gè)粒子的適應(yīng)度，并更新個(gè)體最優(yōu)值和種群最優(yōu)值;

步驟4:按照公式(7)粒子的變異率進(jìn)行更新;

步驟5:如果粒子的變異率大于0～1之間的隨機(jī)數(shù)rand，則用式(4)對粒子的位置進(jìn)行更新，粒子的速度保持不變，否則使用式(1)、式(2)分別對粒子的速度和位置進(jìn)行更新;

步驟6:判斷是否滿足終止條件，終止條件一般為滿足了最大迭代次數(shù)或者各粒子的所有位置的距離均小于某一個(gè)閾值，如果不滿足終止條件返回到步驟3，否則迭代終止。

個(gè)體位變異的粒子群算法流程見圖2。

圖1 變異率優(yōu)化曲線

圖2 個(gè)體位置變異的粒子群算法流程圖

4 算法測試及分析

為了驗(yàn)證標(biāo)準(zhǔn)粒子群算法(PSO)、慣性權(quán)重粒子群算法(IWPSO)、文獻(xiàn)［11］中提出的變異策略粒子群算法(MPSO1)和本文中提出的個(gè)體位置變異的粒子群算法(MPSO2)這4種粒子群算法的優(yōu)劣性，使用6個(gè)經(jīng)典測試函數(shù)對這4種粒子群算法進(jìn)行測試。測試的基準(zhǔn)函數(shù)和參數(shù)設(shè)置如表1所示。

表1 測試的基準(zhǔn)函數(shù)

上述4種算法作為對比算法進(jìn)行比較，其中的參數(shù)設(shè)置為:維數(shù)設(shè)置成50，種群粒子數(shù)為100，最大迭代次數(shù)為1 000，粒子群算法算法ω=0．729，c1=c2=1．494 45，線性遞減權(quán)重粒子群算法ωstart=0．9、ωend=0．4，c1=c2=1．494 45，變異粒子群算法ω=0．729，c1=c2=1．494 45，pmax=0．6，pmin=0．3。每種算法獨(dú)立運(yùn)行10次，最優(yōu)是指所有搜索結(jié)果中的最優(yōu)值;平均是指所有搜索結(jié)果的平均值;當(dāng)最優(yōu)值小于允許誤差時(shí)即認(rèn)為本次搜索成功;成功率是指成功搜索結(jié)果所占搜索總次的比率。4種算法對基準(zhǔn)函數(shù)測試結(jié)果如表2所示，為了更清晰地表示最優(yōu)值隨迭代次數(shù)變化情況，其收斂曲線對比如圖3所示。

表2 基準(zhǔn)函數(shù)測試結(jié)果

通過將4種算法分別應(yīng)用到6個(gè)測試函數(shù)中，從表2和圖3的尋優(yōu)曲線可以知道:慣性權(quán)重粒子群不是針對所有的優(yōu)化問題都比粒子群算法有效，比如測試函數(shù)rosenbrock，同時(shí)，如果只是單純改變權(quán)限權(quán)重參數(shù)可能會(huì)最終導(dǎo)致粒子群算法不收斂;MPSO2和MPSO1算法對于維數(shù)較高的尋優(yōu)問題具有較好的適應(yīng)性，無論在最優(yōu)值還是平均值上均獲得比PSO算法和IWPSO更優(yōu)的結(jié)果，但是MPSO2的綜合優(yōu)化性能突出，具有較快的收斂速度和全局尋優(yōu)能力，這主要是得益于MPSO2能在尋優(yōu)過程中以粒子的個(gè)體位置為依據(jù)進(jìn)行變異。在初始階段，變異率較大，能保證種群的多樣性，有利于全局尋優(yōu);在搜索后期，變異率逐漸變小直至為0，保證粒子逐漸收斂到搜索到的全局最優(yōu)。通過測試函數(shù)的測試結(jié)果可知本文中提出了基于位置變異粒子群算法適合于復(fù)雜實(shí)際工程尋優(yōu)問題，比如復(fù)雜陰影條件下光伏系統(tǒng)最大功率點(diǎn)跟蹤問題、機(jī)器人路徑規(guī)劃、發(fā)電機(jī)組組合優(yōu)化等問題。

圖3 仿真結(jié)果

5 結(jié)論

針對PSO算法易陷入局部最優(yōu)、收斂速度慢等問題，提出一種基于個(gè)體位置變異的粒子群算法。最后通過使用6個(gè)典型測試函數(shù)進(jìn)行數(shù)值實(shí)驗(yàn)，結(jié)果證明了該算法在增強(qiáng)種群多樣性的同時(shí)提高搜索速度。得出結(jié)論如下。

(1)標(biāo)準(zhǔn)粒子群算法的趨向同一化造成種群多樣性差，使得迭代后期收斂速度明顯變慢，容易發(fā)生早熟現(xiàn)象。為了解決粒子群早熟現(xiàn)象，只單純改進(jìn)粒子群算法的參數(shù)，可能會(huì)最終導(dǎo)致粒子群算法不收斂。

(2)將個(gè)體位置變異引入到粒子群算法中，將粒子中符合變異條件的粒子進(jìn)行變異，粒子是否符合變異條件取決于變異率pm。初始階段，變異率較高，此時(shí)粒子選擇變異的方式概率較大;隨著迭代次數(shù)增多，變異率的降低，粒子選擇PSO更新的概率逐漸加大，當(dāng)變異率降為0時(shí)，粒子不再變異，只會(huì)選擇PSO算法。由此可見，該算法既可以保證前期擴(kuò)大粒子的搜索范圍，又可以保證后期粒子逐漸收斂，不再變異。

(3)本文中提出的算法是一種有效的粒子群優(yōu)化算法，程序量小、相對簡單，適合解決復(fù)雜陰影條件下光伏系統(tǒng)最大功率點(diǎn)跟蹤問題、機(jī)器人路徑規(guī)劃、發(fā)電機(jī)組組合優(yōu)化等復(fù)雜的實(shí)際工程優(yōu)化問題。