一種最優粒子逐維變異的粒子群優化算法

羅 強,季偉東,徐浩天,孫小晴

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

1 引 言

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

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

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

受HPSO算法啟發,發現僅僅對最優粒子進行變異就能取得較好的效果,基于此,本文提出了一種對最優粒子進行逐維重心反向學習的變異策略,逐維變異能降低維間干擾[16],重心反向學習能擴大搜索空間、增加種群的多樣性、提升收斂精度.且該變異方式可以和各種優化算法結合,都能取得更好的效果.

2 粒子群算法與反向學習

2.1 粒子群算法

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

(1)

其中t表示更新代數;i=1,2,…,n表示粒子編號;j=1,2,…,D表示維數;w為慣性權重,且w∈[0,1];c1為個體學習因子,c2為社會學習因子,且c1,c2∈[0,2];r1,r2為區間[0,1]上均勻分布的隨機數.

分析該式可知速度更新分三部分,其一為自身先前速度的一部分,受慣性權重w影響,其二為自身飛行經驗部分,是向自身Pbesti方向學習的分量,受個體學習因子c1影響,其三為社會認知部分,是向Gbest方向學習的分量,受社會學習因子c2影響.

2.2 反向學習

(2)

(3)

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

(4)

(5)

其中k為區間[0,1]上均勻分布的隨機數,其反向過程中中心點的位置是動態的并與重心M相關.

3 逐維重心反向變異粒子群優化算法

3.1 逐維重心反向變異策略

目前的對最優粒子的變異策略大多選取的所有維度或者隨機挑取部分維度進行變異,對于高維復雜函數來說,計算其適應度時會因各維相互間的干擾,造成某些維度雖然變得更優但是被另外變得較差的維度所掩蓋,變異效率低下,相較于多次的變異,逐維變異的效率更高,通過避免維間干擾,得到的變異解通常更好.

(6)

其中k為區間[0,1]上均勻分布的隨機數,Mi為重心M在第i維的分量.

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

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

2.fori=1 toD

6. end if

7.end for

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

圖1 2維空間不同學習策略對比Fig.1 Comparison of different learning strategies in two-dimensional space

圖2 2維粒子逐維重心反向學習流程圖Fig.2 Two-dimensional particle Dimensional-by-dimensional centroid opposition-based learning flow chart

表1 2維空間不同學習策略結果對比Table 1 Comparison of different learning strategies in two-dimensional space

分析表1可知逐維重心反向學習比重心反向學習評價的位置更多,所以獲得更優解的機會更大,且質量更好,但是反向學習本身的計算開銷就很大,所以僅適合單獨對最優粒子進行逐維變異,基于這個思想,下面提出一種基于最優粒子逐維重心反向變異策略的粒子群優化算法.

3.2 算法流程

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

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

Step 2.計算當前種群Pop中每個粒子的適應度fitness來確定個體最優Pbest和全體最優Gbest;

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

Step 4.計算當前種群Pop中每個粒子的適應度fitness,并更新Pbest以及Gbest;

Step 5.按照算法1進行逐維重心反向變異來更新Gbest;

Step 6.判斷當前最優解是否滿足終止條件或者達到最大迭代次數,如果是則終止算法,如果不是則返回Step 3.

4 仿真實驗與結果分析

4.1 參數設置與測試函數

本文使用Matlab2018a進行仿真實驗,選取了表2中的9個經典測試函數,每個函數的最優解均為0.將DCOPSO算法與基本PSO算法、自適應柯西變異的HPSO算法、無變異的COPSO算法進行了對比,參數設置如下:計算次數Time=100次,每次的最大迭代次數Maxgen=1000,種群規模N=30;維數D=30,慣性權重w為[0.4,0.9]之間線性遞減,學習因子c1,c2都為2;HPSO中對最優粒子的變異次數M=30;COPSO算法中的反向學習概率P=0.3.

選取的測試函數中,f1-f4為四個單峰函數,f5-f7為3個多峰函數,f8為帶旋轉和位移的單峰函數,f9為帶旋轉和位移的多峰函數.

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

表2 測試函數
Table 2 Test function

測試函數函數名稱定義域最優值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 實驗結果分析

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

表3 實驗結果
Table 3 Experimental results

測試函數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 各函數的收斂曲線Fig.3 Convergence curve of each function

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

表4記錄了HPSO和DCOPSO在9個函數中平均每次迭代變異次數,該數據是變異性能的一個指標,可以從側面體現變異效率的優劣,分析表中數據可知,DCOPSO的變異頻率明顯高于HPSO,從測試結果也驗證了DCOPSO的變異效果更好.

COBL的引入讓PSO算法獲得了較大的提升,通過對比一般地使用COBL,逐維地對最優粒子進行COBL取得的效果也很突出.

5 結 語

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