劉子坤,李枚毅,張 曉

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

動態(tài)環(huán)境下運用對稱位移映射的PSO算法

劉子坤,李枚毅,張 曉

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

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

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

1 概述

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

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

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

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

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

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

2.1 差異進化策略

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

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

圖1 種群的進化示意圖

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

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

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

2.2 算法流程

算法步驟如下:

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

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

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

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

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

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

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

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

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

2.3 空間對稱位移映射

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

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

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

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

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

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

3 實驗仿真及結(jié)果分析

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

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

參數(shù)γ可以用來控制環(huán)境變化的快慢;參數(shù)ρ可以用來控制環(huán)境變化的強度。為了檢驗算法在不同變化強度環(huán)境中的性能,利用MPB測試函數(shù)構(gòu)造了一系列動態(tài)測試環(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測試函數(shù)的參數(shù)設(shè)置

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

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

3.1 實驗設(shè)置

為了直觀說明SDTPSO算法在復(fù)雜動態(tài)環(huán)境下的適應(yīng)能力,在MPB函數(shù)和DF1函數(shù)生成的動態(tài)環(huán)境中進行了多個實驗;并在同樣的實驗條件下與TSPSO算法［11］及LPSO-SOFCMA算法［12］進行了比較。所有算法的粒子總數(shù)設(shè)定為100,c1=c2=1.494,對于算法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次檢測一次環(huán)境是否發(fā)生變化。算法在MPB產(chǎn)生的動態(tài)環(huán)境中每次運行都經(jīng)歷10個變化周期,由DF1產(chǎn)生的動態(tài)環(huán)境算法每次運行都經(jīng)歷20個變化周期。所有的實驗結(jié)果都是采用相同隨機種子運行30次后所獲得的平均值。

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

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

3.2 實驗結(jié)果與分析

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

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

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

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

圖5 椎體的高度變化1

圖6 跟蹤變化極值的誤差變化過程1

圖7 椎體的高度變化2

圖8 跟蹤變化極值的誤差變化過程2

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

4 結(jié)束語

本文提出了一種運用對稱位移映射的雙子群PSO算法,利用2組相互協(xié)同的主、輔子群,并行搜索變化的最優(yōu)值。輔子群采取差異進化機制不斷探索新環(huán)境,若檢測到環(huán)境發(fā)生變化,主子群引進一種對稱位移映射策略來保持種群的多樣性。該算法通過雙子群相互協(xié)作充分挖掘搜索域內(nèi)的有用信息,保持了開發(fā)和探索之間的平衡,當(dāng)環(huán)境發(fā)生變化時能及時地跟蹤到變化的最優(yōu)解。利用2種標(biāo)準(zhǔn)的動態(tài)測試函數(shù)所產(chǎn)生的動態(tài)環(huá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］ 王 偉,李枚毅,彭霞丹.一種雙層可變子群的動態(tài)粒子群優(yōu)化算法［J］.小型微型計算機系統(tǒng),2012, 33(1):1000-1220.

［8］ 孫越泓,魏建香,夏德深.一種基于粒子對稱分布多樣性的 PSO算法［J］.模式識別與人工智能,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］ 焦 魏,劉光斌.動態(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

國家自然科學(xué)基金資助項目(61070232)。

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

2013-11-11

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

中文引用格式:劉子坤,李枚毅,張 曉.動態(tài)環(huán)境下運用對稱位移映射的PSO算法［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.