一種最優(yōu)粒子逐維變異的粒子群優(yōu)化算法

羅 強(qiáng),季偉東,徐浩天,孫小晴

(哈爾濱師范大學(xué) 計(jì)算機(jī)科學(xué)與信息工程學(xué)院,哈爾濱 150025)

1 引 言

PSO(Particle Swarm Optimization)算法[1]是由Kennedy和Eberhart通過(guò)對(duì)鳥群捕食過(guò)程中遷徙及群居行為的模擬,于1995年提出的一種群智能算法,該算法有簡(jiǎn)單易實(shí)現(xiàn)、參數(shù)少、對(duì)優(yōu)化問(wèn)題無(wú)連續(xù)性要求等優(yōu)點(diǎn),目前廣泛運(yùn)用于多個(gè)科學(xué)及工程實(shí)踐領(lǐng)域.可是粒子群算法存在一系列問(wèn)題,比如容易陷入局部最優(yōu)、收斂速度慢、精度低等.針對(duì)這些問(wèn)題很多學(xué)者以不同方式對(duì)粒子群算法進(jìn)行優(yōu)化,其中變異策略是一個(gè)優(yōu)化熱點(diǎn),具有代表性的是柯西變異.

分析PSO算法公式可知,粒子前期飛行軌跡受自身的飛行經(jīng)驗(yàn)(個(gè)體最優(yōu))以及全局最優(yōu)信息影響,后期收斂于全局最優(yōu).這就說(shuō)明有一個(gè)更優(yōu)的全局最優(yōu)信息點(diǎn),將能引導(dǎo)粒子朝向更好的解空間飛行.為了得到一個(gè)更好的全局最優(yōu)點(diǎn)信息,Wang等[2]提出了HPSO算法,通過(guò)對(duì)最優(yōu)粒子進(jìn)行多次柯西變異實(shí)現(xiàn)位置的更新.該方法能增加跳出局部最優(yōu)的概率,加強(qiáng)全局搜索能力,且能加快收斂速度.

反向?qū)W習(xí)(Opposition-Based Learning,OBL)是Hamid R.Tizhoosh等[3]于2005年提出的一種學(xué)習(xí)方法,Rahnamayan等[4]用數(shù)學(xué)推導(dǎo)證明了反向?qū)W習(xí)的有效性;XU Qing-zheng等[5]探討了反向?qū)W習(xí)表現(xiàn)良好背后的原因;Sedigheh Mahdavia等[6]對(duì)反向?qū)W習(xí)近年的發(fā)展及發(fā)表的文獻(xiàn)進(jìn)行了綜述.目前反向?qū)W習(xí)模型已經(jīng)應(yīng)用于各種優(yōu)化算法,如蛙跳算法[7]、蝗蟲優(yōu)化算法[8]、正弦余弦算法[9]、蝴蝶優(yōu)化算法[10]等.Wang等[11]首次將反向?qū)W習(xí)應(yīng)用于粒子群算法,提出了一種基于OBL的粒子群算法OPSO,隨后又提出一般化反向?qū)W習(xí)(Generalized OBL,GOBL)概念,并增加柯西變異算子一起對(duì)OPSO進(jìn)行了優(yōu)化形成了GOPSO算法[12].反向?qū)W習(xí)的引入,有效地加快了粒子群算法的收斂速度和精度.ZHOU Xin-yu等[13]提出的精英反向?qū)W習(xí)粒子群優(yōu)化算法(EOPSO),該算法僅對(duì)精英粒子,即全局最優(yōu)粒子和個(gè)體最優(yōu)粒子進(jìn)行反向?qū)W習(xí),并對(duì)全局最優(yōu)粒子采用差分演化變異策略,該策略增強(qiáng)了算法的局部開采能力,算法相對(duì)GOPSO在收斂速度及精度上均有提升,突現(xiàn)出精英粒子在粒子群算法中起的引領(lǐng)作用.ZHOU Ling-yun等[14]提出鄰域重心反向?qū)W習(xí)的粒子群優(yōu)化算法(NCOPSO),算法引入了由Rahnamayan等[15]提出的重心反向?qū)W習(xí)(Centroid Opposition-Based Learning,COBL)策略,并以粒子的鄰域重心為反向點(diǎn)來(lái)生成反向解,同時(shí)加入了收縮因子拓展COBL的反向搜索空間.該算法充分利用了群體搜索經(jīng)驗(yàn),具有更好的收斂精度.

受HPSO算法啟發(fā),發(fā)現(xiàn)僅僅對(duì)最優(yōu)粒子進(jìn)行變異就能取得較好的效果,基于此,本文提出了一種對(duì)最優(yōu)粒子進(jìn)行逐維重心反向?qū)W習(xí)的變異策略,逐維變異能降低維間干擾[16],重心反向?qū)W習(xí)能擴(kuò)大搜索空間、增加種群的多樣性、提升收斂精度.且該變異方式可以和各種優(yōu)化算法結(jié)合,都能取得更好的效果.

2 粒子群算法與反向?qū)W習(xí)

2.1 粒子群算法

PSO算法[1]是模擬鳥類覓食過(guò)程提出的一種仿生優(yōu)化算法,其基本思想是,將解決問(wèn)題的過(guò)程抽象為:在一個(gè)空間中,存在很多飛行的鳥,它們有自己的位置以及速度,通過(guò)自身的飛行經(jīng)驗(yàn)和種群相互交流的社會(huì)經(jīng)驗(yàn),他們不斷向有食物的方向飛行.而這個(gè)空間就是問(wèn)題的解空間,鳥就是空間中的粒子,設(shè)問(wèn)題的維數(shù)為D,粒子個(gè)數(shù)為n,全局最優(yōu)為Gbest=(Gbest1,Gbest2,…,GbestD),第i個(gè)粒子xi=(xi1,xi2,…,xiD)的個(gè)體最優(yōu)為Pbesti=(Pbesti1,Pbesti2,…,PbestiD)其第j維速度為vij,位置為xij,更新公式如式(1):

(1)

其中t表示更新代數(shù);i=1,2,…,n表示粒子編號(hào);j=1,2,…,D表示維數(shù);w為慣性權(quán)重,且w∈[0,1];c1為個(gè)體學(xué)習(xí)因子,c2為社會(huì)學(xué)習(xí)因子,且c1,c2∈[0,2];r1,r2為區(qū)間[0,1]上均勻分布的隨機(jī)數(shù).

分析該式可知速度更新分三部分,其一為自身先前速度的一部分,受慣性權(quán)重w影響,其二為自身飛行經(jīng)驗(yàn)部分,是向自身Pbesti方向?qū)W習(xí)的分量,受個(gè)體學(xué)習(xí)因子c1影響,其三為社會(huì)認(rèn)知部分,是向Gbest方向?qū)W習(xí)的分量,受社會(huì)學(xué)習(xí)因子c2影響.

2.2 反向?qū)W習(xí)

(2)

(3)

定義3.重心[15](Centroid)：設(shè)(x1,x2,…,xn)是D維搜索空間上的帶有單位質(zhì)量的n個(gè)點(diǎn),則整體的重心定義為

(4)

(5)

其中k為區(qū)間[0,1]上均勻分布的隨機(jī)數(shù),其反向過(guò)程中中心點(diǎn)的位置是動(dòng)態(tài)的并與重心M相關(guān).

3 逐維重心反向變異粒子群優(yōu)化算法

3.1 逐維重心反向變異策略

目前的對(duì)最優(yōu)粒子的變異策略大多選取的所有維度或者隨機(jī)挑取部分維度進(jìn)行變異,對(duì)于高維復(fù)雜函數(shù)來(lái)說(shuō),計(jì)算其適應(yīng)度時(shí)會(huì)因各維相互間的干擾,造成某些維度雖然變得更優(yōu)但是被另外變得較差的維度所掩蓋,變異效率低下,相較于多次的變異,逐維變異的效率更高,通過(guò)避免維間干擾,得到的變異解通常更好.

(6)

其中k為區(qū)間[0,1]上均勻分布的隨機(jī)數(shù),Mi為重心M在第i維的分量.

算法1.逐維重心反向變異策略

1.據(jù)式(4)計(jì)算種群重心M;

2.fori=1 toD

6. end if

7.end for

圖1在2維空間上模擬了對(duì)Gbest(x,y)反向?qū)W習(xí)與逐維反向?qū)W習(xí)的4種可能存在的情況.

圖1 2維空間不同學(xué)習(xí)策略對(duì)比Fig.1 Comparison of different learning strategies in two-dimensional space

圖2 2維粒子逐維重心反向?qū)W習(xí)流程圖Fig.2 Two-dimensional particle Dimensional-by-dimensional centroid opposition-based learning flow chart

表1 2維空間不同學(xué)習(xí)策略結(jié)果對(duì)比Table 1 Comparison of different learning strategies in two-dimensional space

分析表1可知逐維重心反向?qū)W習(xí)比重心反向?qū)W習(xí)評(píng)價(jià)的位置更多,所以獲得更優(yōu)解的機(jī)會(huì)更大,且質(zhì)量更好,但是反向?qū)W習(xí)本身的計(jì)算開銷就很大,所以僅適合單獨(dú)對(duì)最優(yōu)粒子進(jìn)行逐維變異,基于這個(gè)思想,下面提出一種基于最優(yōu)粒子逐維重心反向變異策略的粒子群優(yōu)化算法.

3.2 算法流程

基于逐維重心反向變異粒子群優(yōu)化算法(DCOPSO)算法流程如下:

Step 1.按照均勻分布隨機(jī)初始化N個(gè)D維的粒子形成初始種群Pop;

Step 2.計(jì)算當(dāng)前種群Pop中每個(gè)粒子的適應(yīng)度f(wàn)itness來(lái)確定個(gè)體最優(yōu)Pbest和全體最優(yōu)Gbest;

Step 3.根據(jù)式(1)更新種群Pop中每個(gè)粒子的速度vij及位置xij;

Step 4.計(jì)算當(dāng)前種群Pop中每個(gè)粒子的適應(yīng)度f(wàn)itness,并更新Pbest以及Gbest;

Step 5.按照算法1進(jìn)行逐維重心反向變異來(lái)更新Gbest;

Step 6.判斷當(dāng)前最優(yōu)解是否滿足終止條件或者達(dá)到最大迭代次數(shù),如果是則終止算法,如果不是則返回Step 3.

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

4.1 參數(shù)設(shè)置與測(cè)試函數(shù)

本文使用Matlab2018a進(jìn)行仿真實(shí)驗(yàn),選取了表2中的9個(gè)經(jīng)典測(cè)試函數(shù),每個(gè)函數(shù)的最優(yōu)解均為0.將DCOPSO算法與基本PSO算法、自適應(yīng)柯西變異的HPSO算法、無(wú)變異的COPSO算法進(jìn)行了對(duì)比,參數(shù)設(shè)置如下:計(jì)算次數(shù)Time=100次,每次的最大迭代次數(shù)Maxgen=1000,種群規(guī)模N=30;維數(shù)D=30,慣性權(quán)重w為[0.4,0.9]之間線性遞減,學(xué)習(xí)因子c1,c2都為2;HPSO中對(duì)最優(yōu)粒子的變異次數(shù)M=30;COPSO算法中的反向?qū)W習(xí)概率P=0.3.

選取的測(cè)試函數(shù)中,f1-f4為四個(gè)單峰函數(shù),f5-f7為3個(gè)多峰函數(shù),f8為帶旋轉(zhuǎn)和位移的單峰函數(shù),f9為帶旋轉(zhuǎn)和位移的多峰函數(shù).

主要有2個(gè)測(cè)試目的:1)對(duì)比逐維重心反向變異與柯西變異的效率;2)分別以不同的方式引入COBL得到的結(jié)果如何.

表2 測(cè)試函數(shù)
Table 2 Test function

測(cè)試函數(shù)函數(shù)名稱定義域最優(yōu)值f1Sphere[-100,100]0f2Schwefel 2.22[-10,10]0f3Rosenbrock[-30,30]0f4Step[-100,100]0f5Ackley[-32,32]0f6Rastrigin[-5.12,5.12]0f7 Quartic[-1.28,1.28]0f8Shifted and Rotated Bent Cigar[100,100]0f9Shifted and Rotated Rastrigin[100,100]0

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

分析表3實(shí)驗(yàn)結(jié)果以及圖3(a)～圖3(i)收斂曲線可知,對(duì)于簡(jiǎn)單的單峰測(cè)試函數(shù)f1和f2,DCOPSO比HPSO和COPSO的收斂速度及精度均高出很多,這得益于DCOPSO中最優(yōu)粒子前期快速變異至一個(gè)比較好的位置,讓種群迅速朝著更優(yōu)的地方飛行,后期通過(guò)逐維的方式避免維間干擾,接受有利變異的維度,使收斂的精度更高.對(duì)于較為復(fù)雜,難以尋優(yōu)的病態(tài)單峰測(cè)試函數(shù)f3,HPSO和COPSO很難取得較好的值,而DCOPSO卻有小概率尋找到較好的解,且其平均尋優(yōu)能力也高出不少.在階梯狀的單峰測(cè)試函數(shù)f4,該函數(shù)存在很多平臺(tái),DCOPSO的收斂精度比COPSO較好,但是在計(jì)算過(guò)程中容易遇到所有的粒子處于同一個(gè)平臺(tái)后便出現(xiàn)停滯狀態(tài)的問(wèn)題,而HPSO可以借助柯西變異跳出平臺(tái)繼續(xù)尋優(yōu)取得較優(yōu)的值.在幾個(gè)多峰測(cè)試函數(shù)中,HPSO跳出局部最優(yōu)的幾率較低,平均的收斂精度也比COPSO和DCOPSO差,這意味著柯西變異在后期的全局搜索能力變差,很難跳出局部最優(yōu)解.對(duì)于f5和f6,COPSO和DCOPSO均可能收斂到一個(gè)比較好的解,但是DCOPSO的收斂精度和穩(wěn)定性更高,而在f7中情況又相反,這表明DCOPSO在前期的全局搜索能力不如COPSO,但是后期的局部搜索能力更強(qiáng).在帶旋轉(zhuǎn)和位移的函數(shù)f8和f9中,DCOPSO明顯優(yōu)于其余算法,表明其具有較好的魯棒性.

表3 實(shí)驗(yàn)結(jié)果
Table 3 Experimental results

測(cè)試函數(shù)PSOHPSOCOPSODCOPSO最小值平均值最小值平均值最小值平均值最小值平均值f13.06E+011.23E+022.61E-095.26E-072.45E-301.83E-139.72E-566.07E-45f23.41661.23E+011.84E-057.56E-044.67E-151.40E-081.31E-293.76E-23f34.18E+028.37E+039.39E-015.35E+012.87E+012.88E+011.14E-251.94f44.25E+011.11E+026.59E-095.84E-074.60E-011.72441.64E-052.46E-04f53.6815.83436.42E-052.12E-024.44E-148.36E-082.22E-143.88E-14f64.37E+018.11E+018.962.35E+0109.43E-1300f73.51E-021.05E-011.47E-024.46E-028.95E-066.51E-041.23E-041.80E-03f83.02E+079.04E+071.20E-032.65E-016.79E+026.95E+027.15E-321.70E-26f94.09E+022.66E+031.74E+022.78E+024.60E+021.08E+037.98E+012.27E+02

圖3 各函數(shù)的收斂曲線Fig.3 Convergence curve of each function

表4 平均每次迭代變異次數(shù)Table 4 Average number of mutation per iteration

表4記錄了HPSO和DCOPSO在9個(gè)函數(shù)中平均每次迭代變異次數(shù),該數(shù)據(jù)是變異性能的一個(gè)指標(biāo),可以從側(cè)面體現(xiàn)變異效率的優(yōu)劣,分析表中數(shù)據(jù)可知,DCOPSO的變異頻率明顯高于HPSO,從測(cè)試結(jié)果也驗(yàn)證了DCOPSO的變異效果更好.

COBL的引入讓PSO算法獲得了較大的提升,通過(guò)對(duì)比一般地使用COBL,逐維地對(duì)最優(yōu)粒子進(jìn)行COBL取得的效果也很突出.

5 結(jié) 語(yǔ)

本文提出了一種逐維重心反向變異的粒子群優(yōu)化算法DCOPSO,基于逐維變異的思想,采用重心反向?qū)W習(xí)模型,使全局最優(yōu)粒子在前期帶領(lǐng)種群探索了更大的空間范圍,增加了種群的多樣性,后期充分利用種群信息找到了精度更高的解.通過(guò)理論分析及實(shí)驗(yàn)證明,逐維重心反向變異策略優(yōu)于柯西變異策略.且相較一般的重心反向?qū)W習(xí)算法,其可以和各類優(yōu)化算法相結(jié)合,均能對(duì)算法的全局搜索能力、算法的精度有所提升.