動(dòng)態(tài)環(huán)境下運(yùn)用對(duì)稱位移映射的PSO算法

劉子坤,李枚毅,張 曉

(湘潭大學(xué)信息工程學(xué)院,湖南湘潭411105)

動(dòng)態(tài)環(huán)境下運(yùn)用對(duì)稱位移映射的PSO算法

劉子坤,李枚毅,張 曉

(湘潭大學(xué)信息工程學(xué)院,湖南湘潭411105)

粒子群優(yōu)化算法在求解動(dòng)態(tài)優(yōu)化問(wèn)題時(shí)存在多樣性缺失和尋優(yōu)效率低的問(wèn)題,為此,提出一種運(yùn)用對(duì)稱位移映射的雙子群算法。該算法通過(guò)2組相互協(xié)同的主、輔子群并行地搜索變化的最優(yōu)值。輔子群采取差異進(jìn)化機(jī)制不斷探索新環(huán)境,在感知環(huán)境變化時(shí)引入一種對(duì)稱位移映射策略,使粒子對(duì)稱分布在最優(yōu)解的周圍,以提高算法收斂到最優(yōu)解的概率。使用MPB和DF1兩種經(jīng)典的Benchmark測(cè)試函數(shù)生成復(fù)雜的動(dòng)態(tài)環(huán)境,對(duì)該算法進(jìn)行實(shí)驗(yàn)仿真,結(jié)果表明,該算法能提高跟蹤動(dòng)態(tài)變化極值的準(zhǔn)確性。

粒子群優(yōu)化;動(dòng)態(tài)環(huán)境;優(yōu)化問(wèn)題;雙子群協(xié)同;對(duì)稱位移映射;差異進(jìn)化

1 概述

粒子群優(yōu)化算法操作簡(jiǎn)便、收斂能力較強(qiáng),自問(wèn)世以來(lái)備受關(guān)注,并在很多領(lǐng)域的靜態(tài)優(yōu)化問(wèn)題中得到成功的應(yīng)用［1］。然而真實(shí)世界中遇到的最優(yōu)化問(wèn)題大部分是隨時(shí)間變化的動(dòng)態(tài)環(huán)境,頻繁變化的解空間使得這一時(shí)刻的最優(yōu)解不一定是下一時(shí)刻的最優(yōu)解。因此,在求解動(dòng)態(tài)優(yōu)化問(wèn)題時(shí),算法的目標(biāo)不再是為了獲得一個(gè)滿意解,而是要具有較強(qiáng)的對(duì)環(huán)境變化的適應(yīng)能力,盡可能追蹤到最優(yōu)解的變化軌跡。

文獻(xiàn)［2］提出利用粒子群優(yōu)化(Particle Swarm Optimization,PSO)來(lái)求解動(dòng)態(tài)優(yōu)化問(wèn)題。為了改善PSO算法在動(dòng)態(tài)環(huán)境下的性能,文獻(xiàn)［3］提出了一種帶有電荷粒子的PSO,通過(guò)粒子間模擬的庫(kù)侖排斥力防止群體的收斂;文獻(xiàn)［4］提出了基于多個(gè)物種部落的PSO,通過(guò)對(duì)物種大小、半徑的設(shè)置保持粒子間的距離;文獻(xiàn)［5］提出了一種分層聚類的方法,把種群劃分成多個(gè)子種群,子群粒子初始化依據(jù)適應(yīng)值曲面的分布自動(dòng)產(chǎn)生;文獻(xiàn)［6］提出了一種多種群方法,利用一種模糊準(zhǔn)則可以阻止低質(zhì)量種群的聚集。

為了增強(qiáng)PSO算法求解動(dòng)態(tài)優(yōu)化問(wèn)題的能力,本文提出一種運(yùn)用對(duì)稱位移映射機(jī)制的雙子群PSO算法。該算法把整個(gè)種群等分為主、輔2個(gè)子群,其中輔子群部分采用差異性的進(jìn)化策略,以增加種群對(duì)環(huán)境的探索能力。當(dāng)檢測(cè)到環(huán)境發(fā)生變化時(shí),主子群部分引入對(duì)稱位移映射機(jī)制,及時(shí)對(duì)粒子的位置進(jìn)行對(duì)稱性的調(diào)整,以保持算法的局部開(kāi)發(fā)能力,在環(huán)境變化的同時(shí)及時(shí)做出響應(yīng)。

2 對(duì)稱分布的雙子群協(xié)同PSO算法

PSO算法源于生物界群體行為的啟發(fā),通過(guò)群體中個(gè)體行為的協(xié)作,實(shí)現(xiàn)粒子在解空間的搜索［7］。在引入本文改進(jìn)的算法之前,先給出標(biāo)準(zhǔn)PSO算法的速度-位置進(jìn)化方程如下:

其中:i=1,2,…,M;d=1,2,…,D;M和D分別代表粒子群規(guī)模和搜索空間的維數(shù);c1和c2分別表示認(rèn)知因子和社會(huì)學(xué)習(xí)因子;r1和r2是 2個(gè)分布在[0,1]區(qū)間的隨機(jī)數(shù);w是自適應(yīng)調(diào)整慣性因子,表示粒子對(duì)自身速度的記憶程度。粒子i在D維解空間中自身的位置向量xi=(xi1,xi2,…,xiD),粒子i位置移動(dòng)的速度向量vi=(vi1,vi2,…,viD),pi=(pi1,pi2,…,pid)是粒子i迄今為止所經(jīng)歷的最優(yōu)位置,pg=(pg1,pg2,…,pgd)是整個(gè)種群中所有粒子所經(jīng)歷的最優(yōu)位置。

2.1 差異進(jìn)化策略

本文提出一種運(yùn)用對(duì)稱位移映射的雙子群PSO算法(Two Subpopulation Swarm PSO with Symmetric Displacement Mapping,TSDPSO)。算法在運(yùn)行開(kāi)始時(shí)把整個(gè)種群等分為主、輔2個(gè)子群。主子群按照式(1)、式(2)對(duì)粒子的速度和位置進(jìn)行更新,為了保持種群的探索能力,對(duì)輔子群采取差異進(jìn)化的策略;即輔子群按照式(2)、式(3)對(duì)粒子的位置和速度進(jìn)行更新。

種群的進(jìn)化過(guò)程示意圖如圖1所示,主子群Part I部分的粒子始終被全局最優(yōu)粒子所吸引,而采取差異進(jìn)化策略的輔子群Part II部分每個(gè)粒子都以50%的概率與全局最優(yōu)粒子保持吸引和排斥的關(guān)系。

圖1 種群的進(jìn)化示意圖

當(dāng)檢測(cè)到環(huán)境發(fā)生變化時(shí),優(yōu)化算法需要及時(shí)地反映以適應(yīng)環(huán)境的變化。因此,為了及時(shí)有效地追蹤最優(yōu)解,正確及時(shí)地檢測(cè)環(huán)境的改變非常重要。本文算法采用Eberhart提出的通過(guò)檢測(cè)主子群的全局最優(yōu)和次全局最優(yōu)的方法來(lái)感知壞境的變化;即檢測(cè)相鄰2次迭代適應(yīng)度的差值ΔFi=Fi(iter+1)-Fi(iter)。

當(dāng)檢測(cè)到環(huán)境發(fā)生變化,主子群對(duì)粒子的空間位置分布進(jìn)行對(duì)稱性的調(diào)整,引入一種對(duì)稱位移映射策略以保持種群的多樣性,增加尋找到最優(yōu)解的概率。文獻(xiàn)［8］提出了一種基于對(duì)稱分布多樣性的PSO算法,通過(guò)對(duì)粒子空間分布的研究發(fā)現(xiàn),粒子在最優(yōu)解周圍更對(duì)稱的分布可大幅提高算法收斂到全局最優(yōu)解的概率。粒子空間分布的調(diào)節(jié)如圖2所示,在圖2(b)中粒子分布在局部最優(yōu)和全局最優(yōu)的周圍。算法收斂到全局最優(yōu)解的概率增加,從而提高算法的收斂精度。但其只在粒子的個(gè)數(shù)上做了對(duì)稱性調(diào)整,當(dāng)粒子在全局最優(yōu)一側(cè)空間位置上聚集的程度過(guò)于密集,這種調(diào)整方式并不能使種群的多樣性得到保持,為了增加粒子收斂到全局最優(yōu)解的概率,本文在其基礎(chǔ)上提出了一種對(duì)稱位移映射機(jī)制,使粒子在空間位置上進(jìn)行了對(duì)稱性的調(diào)整。

圖2 粒子的二維空間分布示意圖

2.2 算法流程

算法步驟如下:

Step1 隨機(jī)初始化粒子群中粒子的速度向量vi= (vi1,vi2,…,viD)和位置向量xi=(xi1,xi2,…,xiD)。

Step2 將隨機(jī)初始化的粒子群等分為主、輔兩個(gè)子群,計(jì)算每個(gè)粒子的適應(yīng)值,設(shè)置pi為初始群體的當(dāng)前位置,pg為全局最優(yōu)粒子的位置。

Step3 主子群按式(1)、式(2)進(jìn)行粒子的位置和速度更新,輔子群按式(2)、式(3)進(jìn)行粒子的位置和速度更新。

Step4 根據(jù)適應(yīng)值更新主、輔子群的個(gè)體最優(yōu)位置,若粒子的適應(yīng)值更優(yōu)于pi的適應(yīng)值,則pi更新為新位置;反之pi保持不變。

Step5 比較主、輔2組子群的全局最優(yōu)位置對(duì)應(yīng)的適應(yīng)值,更優(yōu)者更新為整個(gè)粒子群的全局最優(yōu)位置pg。

Step6 每n次迭代檢測(cè)一次全局最優(yōu)和次全局最優(yōu)解是否發(fā)生變化,若沒(méi)有變化則執(zhí)行Step7,若發(fā)生變化則執(zhí)行Step8。

Step7 重新計(jì)算輔子群的適應(yīng)值,對(duì)主子群的粒子空間位置執(zhí)行對(duì)稱性的調(diào)整,重新評(píng)估全局最優(yōu)位置pg。

Step8 判斷算法是否滿足收斂準(zhǔn)則,若滿足,則輸出全局最優(yōu)粒子pg,算法運(yùn)行結(jié)束,否則跳轉(zhuǎn)到Step3。

TSDPSO算法的流程如圖3所示。

2.3 空間對(duì)稱位移映射

空間對(duì)稱位移映射具體操作步驟如下:

Step1 在每一維上計(jì)算主群中每個(gè)粒子i(i= 1,2,…,M)的位置分量Xij(j=1,2,…,D)與局部最優(yōu)Gbest的位置的差值。

Step2 統(tǒng)計(jì)每一維度上的位置差值的正負(fù)值個(gè)數(shù),正值的個(gè)數(shù)記為n1d(d=1,2,…,D),負(fù)值個(gè)數(shù)記為n2d(d=1,2,…,D)。

Step4 將粒子個(gè)數(shù)較少的一側(cè)按粒子個(gè)數(shù)較多一側(cè)粒子的位置作式(4)的變換,得到其新的位置,即在粒子數(shù)目較少的一側(cè)映射較多一側(cè)的粒子。

粒子對(duì)稱位移映射調(diào)節(jié)示意圖如圖4所示。

圖4 粒子對(duì)稱位移映射調(diào)節(jié)示意圖

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

在本文的實(shí)驗(yàn)中,利用標(biāo)準(zhǔn)動(dòng)態(tài)測(cè)試函數(shù)MPB (Moving Peaks Benchmarks)和 DF1(Dynamic Function)構(gòu)造出一系列動(dòng)態(tài)環(huán)境用于測(cè)試算法的性能。MPB問(wèn)題可以被描述為在n維實(shí)空間內(nèi)存在m個(gè)可以改變位置、高度和寬度的峰,其函數(shù)描述如下:

實(shí)驗(yàn)中采用的MPB參數(shù)設(shè)置對(duì)應(yīng)其標(biāo)準(zhǔn)測(cè)試網(wǎng)站上的Scenariol［9］。這種MPB函數(shù)定義在一個(gè)含有5個(gè)移動(dòng)峰的5維空間中。每經(jīng)過(guò)γ次迭代,每個(gè)峰的高度和寬度都會(huì)被加上一個(gè)隨機(jī)的高斯變量,而位置會(huì)根據(jù)一個(gè)固定長(zhǎng)度為ρ的隨機(jī)向量v進(jìn)行移動(dòng)。變化可以通過(guò)如下公式描述:

參數(shù)γ可以用來(lái)控制環(huán)境變化的快慢;參數(shù)ρ可以用來(lái)控制環(huán)境變化的強(qiáng)度。為了檢驗(yàn)算法在不同變化強(qiáng)度環(huán)境中的性能,利用MPB測(cè)試函數(shù)構(gòu)造了一系列動(dòng)態(tài)測(cè)試環(huán)境。參數(shù)ρ分別設(shè)為0.1,1.0, 2.0和5.0。變化的速度參數(shù)γ分別設(shè)為50,100和200,分別代表環(huán)境變化的快、中等和慢3種情況。MPB的具體參數(shù)設(shè)置如表1所示。

表1 MPB測(cè)試函數(shù)的參數(shù)設(shè)置

文獻(xiàn)［10］提出DF1動(dòng)態(tài)函數(shù),它通過(guò)利用一些椎體的組合產(chǎn)生復(fù)雜的環(huán)境。DF1函數(shù)描述如下:

其中,f(x,y)是點(diǎn)(x,y)的適應(yīng)度值;N是該環(huán)境中椎體的個(gè)數(shù);(xi,yi)是第i個(gè)椎體的頂點(diǎn)位置;Hi是第i個(gè)椎體的的高度;Ri是第i個(gè)椎體的斜度參數(shù)。優(yōu)化算法的目標(biāo)是在環(huán)境發(fā)生變化后找到椎體最高峰值的位置。在本文實(shí)驗(yàn)中,利用DF1在五維空間產(chǎn)生4個(gè)椎體A,B,C,D;椎體的高度和位置每經(jīng)過(guò)50迭代進(jìn)行一次變化更新,算法分別在椎體的高度和位置變化步長(zhǎng)恒定和隨機(jī)步長(zhǎng)2種情況下進(jìn)行了對(duì)比測(cè)試。

3.1 實(shí)驗(yàn)設(shè)置

為了直觀說(shuō)明SDTPSO算法在復(fù)雜動(dòng)態(tài)環(huán)境下的適應(yīng)能力,在MPB函數(shù)和DF1函數(shù)生成的動(dòng)態(tài)環(huán)境中進(jìn)行了多個(gè)實(shí)驗(yàn);并在同樣的實(shí)驗(yàn)條件下與TSPSO算法［11］及LPSO-SOFCMA算法［12］進(jìn)行了比較。所有算法的粒子總數(shù)設(shè)定為100,c1=c2=1.494,對(duì)于算法LPSO-SOFCMA,其中,rs=1.0,rr=5,t_ri= 25,w=0.729 48。本文提出的 TSDPSO算法和TSPSO算法的慣性權(quán)重為w=0.5+rand()/2,2種算法都每迭代20次檢測(cè)一次環(huán)境是否發(fā)生變化。算法在MPB產(chǎn)生的動(dòng)態(tài)環(huán)境中每次運(yùn)行都經(jīng)歷10個(gè)變化周期,由DF1產(chǎn)生的動(dòng)態(tài)環(huán)境算法每次運(yùn)行都經(jīng)歷20個(gè)變化周期。所有的實(shí)驗(yàn)結(jié)果都是采用相同隨機(jī)種子運(yùn)行30次后所獲得的平均值。

由于動(dòng)態(tài)環(huán)境中并不存在一個(gè)唯一的最優(yōu)解,因此本文利用離線性能指標(biāo)EBG來(lái)評(píng)價(jià)算法的性能,EBG的計(jì)算公式如下:

其中,G表示算法運(yùn)行代數(shù)(G=10×i);N=30是算法運(yùn)行的次數(shù);FBGij表示算法第j次運(yùn)行第i代所獲得最好解的適值;表示全局最優(yōu)解的適應(yīng)值,顯然,在最優(yōu)解適應(yīng)值已知的情況下,這種離線性能指標(biāo)能夠很好地評(píng)估算法對(duì)它的追蹤能力。

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

從表2可以看出,隨著環(huán)境變化強(qiáng)度的增大,跟蹤極值點(diǎn)難度隨之增加,因?yàn)榄h(huán)境變化強(qiáng)度越大會(huì)導(dǎo)致算法陷入局部極值的可能性加大。當(dāng)環(huán)境變化周期變長(zhǎng)時(shí),算法會(huì)有更長(zhǎng)的時(shí)間去尋找到最優(yōu)解,跟蹤極值點(diǎn)的難度隨之減小。

表2 3種算法尋找到最優(yōu)解所用的時(shí)間 s

在上面的動(dòng)態(tài)環(huán)境中,本文提出的TSDPSO算法采取了對(duì)稱位移映射機(jī)制,有效地避免了整個(gè)種群過(guò)于發(fā)散,算法能夠快速跟蹤到變化的最優(yōu)解。其表現(xiàn)更優(yōu)于其他2種算法,而僅當(dāng)環(huán)境變化強(qiáng)度較小,即γ=200,ρ=0.1時(shí)LPSO-SOFCMA的性能優(yōu)于本文的TSDPSO算法。

在圖5～圖8所示的2組DF1實(shí)驗(yàn)中,4個(gè)椎體的位置和高度都不斷地發(fā)生變化。

圖5 椎體的高度變化1

圖6 跟蹤變化極值的誤差變化過(guò)程1

圖7 椎體的高度變化2

圖8 跟蹤變化極值的誤差變化過(guò)程2

從算法跟蹤極值點(diǎn)的誤差變化過(guò)程可以看出,當(dāng)椎體的位置和高度小步變化時(shí),所有算法跟蹤變化的最優(yōu)值效果較好。因?yàn)樽兓笮聠?wèn)題的解和老問(wèn)題的解存在一定的關(guān)聯(lián),2次變化之間的差異性不大,算法可以利用環(huán)境變化前的有用信息便于其找到最優(yōu)解。當(dāng)椎體位置和高度隨機(jī)變化時(shí),尋找最優(yōu)解的困難加大,3種算法在跟蹤椎體高度變化的誤差明顯增加。在上面環(huán)境變化強(qiáng)度不同的2組實(shí)驗(yàn)中,本文的TSDPSO算法對(duì)粒子的空間分布進(jìn)行了調(diào)整,增加了種群收斂到全局最優(yōu)解的概率,能有效避免陷入局部最優(yōu),及時(shí)跟蹤到椎體高度的變化,其表現(xiàn)更優(yōu)于其他2種算法。

4 結(jié)束語(yǔ)

本文提出了一種運(yùn)用對(duì)稱位移映射的雙子群PSO算法,利用2組相互協(xié)同的主、輔子群,并行搜索變化的最優(yōu)值。輔子群采取差異進(jìn)化機(jī)制不斷探索新環(huán)境,若檢測(cè)到環(huán)境發(fā)生變化,主子群引進(jìn)一種對(duì)稱位移映射策略來(lái)保持種群的多樣性。該算法通過(guò)雙子群相互協(xié)作充分挖掘搜索域內(nèi)的有用信息,保持了開(kāi)發(fā)和探索之間的平衡,當(dāng)環(huán)境發(fā)生變化時(shí)能及時(shí)地跟蹤到變化的最優(yōu)解。利用2種標(biāo)準(zhǔn)的動(dòng)態(tài)測(cè)試函數(shù)所產(chǎn)生的動(dòng)態(tài)環(huán)境對(duì)算法進(jìn)行了測(cè)試,實(shí)驗(yàn)結(jié)果表明,所提出的TSDPSO算法具有較好的魯棒性和適應(yīng)環(huán)境變化的能力。

［1］ Kennedy J,Eberhart R C.Particle Swarm Optimization［C］//Proceedings of IEEE International Conference on Neural Networks.［S.l.］:IEEE Press,1995:1942-1948.

［2］ Eberhart R C,Shi Yuhui.Tracking and Optimizing Dynamic Systems with Particle Swarms［C］//Proceedings of Congress on Evolutionary Computation.New York, USA:IEEE Press,2001:94-97.

［3］ Blackwell T M,Branke J.Multiswarms Exclusion,and Anti-convergence in Dynamic Environments［J］.IEEE Transactions on Evolutionary Computation,2006, 10(4):459-472.

［4］ Parrott D,Li Xiaodong.Locating and Tracking Multiple Dynamic Optima by a Particle Swarm Model Using Speciation［J］.IEEE Transactionson Evolutionary Computation,2006,10(4):440-458.

［5］ Yang Shengxiang.A Clustering Particle Swarm Optimizer for Locating and Tracking Multiple Optima in Dynamic Environments［J］.IEEE Transactions on Evolutionary Computation,2010,14(6):959-974.

［6］ Hernandez P N,Corona C C,Pelta D A.Efficient Multiswarm PSO Algorithms for Dynamic Environments［J］.Memetic Computing,2011,(3):163-174.

［7］ 王 偉,李枚毅,彭霞丹.一種雙層可變子群的動(dòng)態(tài)粒子群優(yōu)化算法［J］.小型微型計(jì)算機(jī)系統(tǒng),2012, 33(1):1000-1220.

［8］ 孫越泓,魏建香,夏德深.一種基于粒子對(duì)稱分布多樣性的 PSO算法［J］.模式識(shí)別與人工智能,2010, 23(2):137-143.

［9］ Morrison R W,Jong K A.A Test Problem Generator for Non-stationary Environments［C］//Proceedings of Congress on Evolutionary Computation.［S.l.］:IEEE Press, 1999:2047-2053.

［10］ Branke J.The Moving Peaks Benchmark［EB/OL］.(2010-01-02).http://people.aifb.kit.edu/jbr/MovPeaks/.

［11］ 焦 魏,劉光斌.動(dòng)態(tài)環(huán)境下的雙子群PSO算法［J］.控制與決策,2009,24(7):1083-1086.

［12］ Wang Hongfeng,YangShengxiang,WangDingwei, et al.Aparticle Swarm Optimization Based Memetic Algorithm for Dynamic Optimization Problems［J］.Natural Computing,2010,9(3):703-725.

編輯 顧逸斐

PSO Algorithm with Symmetric Displacement Mapping in Dynamic Environment

LIU Zikun,LI Meiyi,ZHANG Xiao
(School of Information Engineering,Xiangtan University,Xiangtan 411105,China)

Particle Swarm Optimization(PSO)algorithm is inclined to fall into diversity loss and low optimizing efficiency in dynamic environment.In this paper,a PSO algorithm with symmetric displacement mapping is proposed.The main subpopulation and assistant subpopulation particle swarm work with each other to search the changing global optimum by the parallel searching.The assistant subpopulation particle swarm uses differential evolutionary mechanism to constantly explore the new environment,when the environment is changed,and a symmetrical displacement mapping strategy is introduced to improve the convergence probability to the global optimum through symmetrical particle distribution surrounding the global optimum.The simulative environment in experiments is generated by MPB and DF1 two benchmark functions,the results demonstrate that the algorithm can improve the accuracy of tracking the changing global optimum.

Particle Swarm Optimization(PSO);dynamic environment;optimization problem;two subpopulation swarm cooperation;symmetric displacement mapping;differential evolution

1000-3428(2014)11-0200-05

A

TP301.6

10.3969/j.issn.1000-3428.2014.11.039

國(guó)家自然科學(xué)基金資助項(xiàng)目(61070232)。

劉子坤(1989-),男,碩士研究生,主研方向:智能計(jì)算;李枚毅,教授、博士;張 曉,碩士研究生。

2013-11-11

2014-01-02E-mail:liuzikunedu@163.com

中文引用格式:劉子坤,李枚毅,張 曉.動(dòng)態(tài)環(huán)境下運(yùn)用對(duì)稱位移映射的PSO算法［J］.計(jì)算機(jī)工程,2014,40(11): 200-204.

英文引用格式:Liu Zikun,Li Meiyi,Zhang Xiao.PSO Algorithm with Symmetric Displacement Mapping in Dynamic Environment［J］.Computer Engineering,2014,40(11):200-204.