融合擾動策略的多目標(biāo)粒子群優(yōu)化算法

王進成,顧銀魯

(銀川能源學(xué)院 基礎(chǔ)部,寧夏 銀川 750105)

0 引言

在現(xiàn)實世界中,多目標(biāo)優(yōu)化問題廣泛存在于工業(yè)生產(chǎn)和日常生活中.在多目標(biāo)優(yōu)化問題中,由于每個目標(biāo)之間存在沖突,所以不存在唯一的最優(yōu)解[1].因此,分析多目標(biāo)優(yōu)化問題的目標(biāo)是找到一組非支配解,而不是單一的解.非支配解稱為Pareto解,它們的集合形成了客觀空間中的Pareto前沿.此外,在求解多目標(biāo)優(yōu)化問題時,有以下3個要求:①盡可能地接近真正的Pareto有效前沿;②盡可能地保持良好的多樣性;③盡可能地使粒子分散均勻.目前,出現(xiàn)了許多經(jīng)典的多目標(biāo)優(yōu)化算法.比如Dbe等[2]利用non-dominated sorting提出了NSGA-II,Zitzler等[3]利用強度Pareto支配的思想提出了SPEA2.

粒子群優(yōu)化算法(Particle Swarm Optimization Algorithm,PSO)是由Kennedy等[4]于1995年提出來的一種群智能算法,它成功地應(yīng)用于單目標(biāo)優(yōu)化.而在實際的工程應(yīng)用中很多都要解決多目標(biāo)優(yōu)化的問題,所以越來越多的研究者已經(jīng)將其擴展應(yīng)用到多目標(biāo)優(yōu)化.如何選擇局部最優(yōu)和全局最優(yōu)很重要,而且由于其不可微、不連續(xù)、非線性等特點,傳統(tǒng)的數(shù)學(xué)方法已經(jīng)很難解決此類問題.此時,智能計算方法在該問題中表現(xiàn)出很大的優(yōu)勢.傳統(tǒng)的智能算法只是將多目標(biāo)進行加權(quán),將其轉(zhuǎn)化為單目標(biāo),該算法對加權(quán)系數(shù)的要求較高.因此,PSO算法在各種優(yōu)化問題中得到了越來越廣泛的應(yīng)用,包括復(fù)雜的多目標(biāo)優(yōu)化問題[5].用于解決多目標(biāo)優(yōu)化問題的粒子群優(yōu)化算法稱為多目標(biāo)粒子群優(yōu)化算法(Multi-objective particle swarm algorithm,MOPSO).近年來,研究者通過引入混沌序列[6]和突變[7]來改進MOPSO,有效地提高了算法的搜索性能;文獻[8]提出了一種基于類圓映射的多目標(biāo)粒子群優(yōu)化算法,提高了種群尋優(yōu)性能;文獻[9]將基于集成學(xué)習(xí)的兩種代理模型分別應(yīng)用于全局搜索和局部搜索,提出了一種異構(gòu)集成代理輔助多目標(biāo)粒子群優(yōu)化算法,提高了代理模型的搜索能力,減少了評估次數(shù);文獻[10]為提高解決多目標(biāo)優(yōu)化問題的能力,提出一種改進的多目標(biāo)粒子群優(yōu)化算法,實驗結(jié)果表明,在世代距離GD(Generational Distance)和空間評價方法 SP(Spacing)性能指標(biāo)上,改進之后的算法與另外幾種對等算法相比,具有顯著的整體優(yōu)勢.

為進一步增強算法的收斂性及種群多樣性,提出了一種融合擾動策略的多目標(biāo)粒子群優(yōu)化算法.通過自適應(yīng)調(diào)整粒子參數(shù)以及在速度更新公式中增加擾動項,提高了算法的收斂速度;為了增強算法的隨機性和多樣性,擴大搜索空間,按照某一特定的發(fā)生概率對外部檔案中的粒子進行維護和擾動.最后,對多目標(biāo)測試函數(shù)進行數(shù)值實驗,并且與經(jīng)典的多目標(biāo)算法NSGA-II、SPEA2和MOPSO對比,結(jié)果表明,該算法比其他3種經(jīng)典的多目標(biāo)優(yōu)化算法在GD和SP性能指標(biāo)上都具有較好的提升.

1 多目標(biāo)優(yōu)化問題及基本概念

一般情況下,多目標(biāo)優(yōu)化問題(Multi-objective Optimization Problem,MOP)優(yōu)化兩個或兩個以上相互沖突的目標(biāo),其包含一組目標(biāo)函數(shù)和一些約束條件.一個具有m個目標(biāo)函數(shù),d個決策變量的多目標(biāo)優(yōu)化問題,其數(shù)學(xué)描述如下:

minf(x)=(f1(x),f2(x),…,fm(x)),

(1)

(2)

以下介紹多目標(biāo)優(yōu)化問題中常用的幾個基本概念[11-12].

定義1(可行域)在決策空間中,用Ω來表示可行域,其表達式為

(3)

定義2(可行解)對于決策空間中的點x,若x∈Ω,則x為可行解.

定義3(Pareto支配)對于任意向量x1,x2,當(dāng)且僅當(dāng):

?i∈Rn,fi(x1)≤fi(x2),
且?j∈Rn,fj(x1)

(4)

則稱x1支配x2,記作x1x2.

定義4(Pareto最優(yōu)解)Pareto最優(yōu)解也稱作非支配解,對于可行域內(nèi)某一解x*,如果x*不被可行域內(nèi)任何其他解支配,則稱x*為Pareto最優(yōu)解,其定義如下:

┐?x∈Ω:xx*.

(5)

定義5(Pareto最優(yōu)解集,FS)可行域內(nèi)所有的非支配解組成的集合,稱為Pareto最優(yōu)解集,定義如下:

PS={x*|┐?x∈Ω:xx*}.

(6)

定義6(Pareto最優(yōu)前沿,PF)Pareto最優(yōu)解集對應(yīng)的目標(biāo)向量集合為Pareto最優(yōu)前沿,也稱Pareto最優(yōu)前端或Pareto均衡面,定義如下:

(7)

2 粒子群優(yōu)化算法

PSO是一種模擬鳥群覓食行為的群智能優(yōu)化算法,PSO算法的提出激發(fā)了許多研究者對群智能優(yōu)化算法的研究.在PSO算法中,每只鳥都被看作是一個粒子,粒子由gbest和pbest變化來尋找最優(yōu)解.假設(shè)種群規(guī)模為N的粒子在D維空間內(nèi)搜索,粒子的速度和位置更新公式如下:

vij(t+1)=ωvij(t)+
c1r1(gbestj-xij(t))+
c2r2(pbestij-xij(t)),

(8)

xij(t+1)=xij(t)+vij(t+1),

(9)

其中:ω,c1,c2分別表示慣性權(quán)重、個體經(jīng)驗系數(shù)、社會經(jīng)驗系數(shù),ω由式(10)確定,c1和c2一般取值為2;xi和vi表示第i個粒子的位置和速度;pbesti表示第i個粒子的pbest位置;gbest表示整個種群的gbest位置,在多目標(biāo)問題上,gbest也被視為非支配解;j為維數(shù);t為當(dāng)前迭代次數(shù);r1和r2為[0,1]之間的兩個隨機數(shù).慣性權(quán)重ω由下式確定:

ω=ωmax-t*(ωmax-ωmin)/Tmax.

(10)

其中:ωmax,ωmin分別為慣性權(quán)重的最大值和最小值,一般取值為0.9和0.4;t表示當(dāng)前迭代次數(shù);Tmax表示最大迭代次數(shù).

3 融合擾動策略的多目標(biāo)粒子群優(yōu)化算法

由于解決多目標(biāo)問題的最終目標(biāo)是獲得一組均勻分布的非支配解,因此,DSMOPSO算法還需要以下操作.

3.1 外部檔案維護策略

用于存儲非支配解的集合稱為外部檔案,它的規(guī)模通常跟MOPSO的種群數(shù)量是一致的.當(dāng)非支配解的數(shù)量超過外部檔案規(guī)模時,部分非支配解需要移除.為了進一步提高非支配解的均勻性,根據(jù)文獻[13]計算粒子的個體密度,計算公式如下:

(11)

其中,PCD(Pi,Pj)表示Pi與Pj之間的平行格距離,計算公式為

(12)

外部檔案維護策略具體如下:首先輸入待更新的外部檔案A、外部檔案最大規(guī)模K以及進化算法獲得新解集P,令B=A∪P,求出B的目標(biāo)向量值,找出B中的非支配解B′,如果B′中元素的個數(shù)B

3.2 個體最優(yōu)解與全局最優(yōu)解選取策略

3.2.1 個體最優(yōu)值選取策略

(13)

3.2.2 全局最優(yōu)解選取策略

本文采用隨機權(quán)重的方法將外部檔案中的多目標(biāo)向量轉(zhuǎn)化成單目標(biāo),從該權(quán)重下隨機選取全局最優(yōu)粒子,具體方法如下:

(14)

(15)

其中,ai為隨機產(chǎn)生的權(quán)重.

3.3 參數(shù)改進策略

眾所周知,粒子群優(yōu)化算法的局部和全局搜索能力很大程度上取決于粒子的三類控制參數(shù).較大的慣性權(quán)重可以加強全局搜索能力,較小的慣性權(quán)重可以加強局部搜索能力;與社會認知能力相比,較大的自我認知能力將導(dǎo)致粒子在整個搜索空間中搜索,從而加強了算法的局部搜索能力;與自我認知能力相比,較大的社會認知能力將導(dǎo)致粒子進行局部搜索,從而加強了算法的全局搜索能力.

雖然多目標(biāo)優(yōu)化的目標(biāo)通常是獲得一組非支配解集,而不是單一的最優(yōu)解,但如何有效地平衡PSO算法的局部和全局搜索能力,仍然是尋找更好的非支配解集的關(guān)鍵.為了提高粒子群算法的性能,本文提出了一種新的自適應(yīng)策略,使其能夠很好地平衡粒子的局部和全局搜索能力,以找到高質(zhì)量的非支配解集.其自適應(yīng)更新公式如下:

ω(t+1)=(ωmax-ωmin)*δ+ωmin,

(16)

c1(t+1)=(c1s-c1f)*δ+c1f,

(17)

c2(t+1)=(c2s-c2f)*δ+c2f,

(18)

(19)

其中,ωmax和ωmin分別為慣性權(quán)重的最大值和最小值;c1s和c1f是自我認知參數(shù)的初始值和最終值;c2s和c2f是社會認知參數(shù)的初始值和最終值;tmax表示最大迭代次數(shù);在自適應(yīng)策略中,ωmax=0.9,ωmin=0.4,c1s=c2f=2.5,c1f=c2s=0.5,tmax=200.

3.4 擾動策略

通過對粒子群算法中速度更新公式的分析,在算法初期,粒子擁有較大慣性速度,較大的速度會使粒子擁有一個較強的全局搜索能力.在算法后期,粒子趨近最優(yōu)位置時,粒子速度下降直至為零,很容易陷入局部最優(yōu).為了使粒子跳出局部最優(yōu),在速度更新公式中添加速度擾動項,不影響算法前期全局搜索,在算法后期確保粒子速度不至于為零,依然給算法一個小速度,有利于增加局部搜素能力,為粒子跳出局部最優(yōu)提供可能.其更新公式如下:

vij(t+1)=ωvij(t)+c1r1(gbestj-xij(t))+
c2r2(pbestij-xij(t))+a*(t/Tmax)2,

(20)

其中,a為極小的隨機數(shù),取值為0.001.

在多目標(biāo)粒子群算法中,通過算法迭代將不斷產(chǎn)生的非支配解都存儲到一個外部檔案集中,每個粒子的gbest可以從檔案中選擇,這種選擇策略會使處于稠密區(qū)域的非支配解有更多的選擇機會,從而影響了種群的多樣性,容易使算法出現(xiàn)早熟現(xiàn)象.因此,為了使粒子存在多樣性以及避免算法陷入局部最優(yōu),本文采用以一定的發(fā)生概率p對外部存檔集進行擾動,以產(chǎn)生新的非劣解,其擾動公式如下:

(21)

3.5 DSMOPSO的步驟及算法流程圖

通過以上分析,完整的DSMOPSO算法步驟由上述操作以一定的順序組成,其具體實現(xiàn)算法步驟如下,流程圖如圖1所示.

圖1 DSMOPSO算法流程圖

步驟1:初始化種群中所有粒子的位置和速度;

步驟2:計算每個粒子的目標(biāo)函數(shù)值,保持每個粒子的初始位置和目標(biāo)函數(shù)值;

步驟3:根據(jù)式(13)和(14),選擇pbest和gbest,構(gòu)建外部檔案;

步驟4:根據(jù)式(20)和式(9)更新所有粒子的位置和速度;

步驟5:以一定的發(fā)生概率對外部存檔集進行擾動,以產(chǎn)生新的非劣解;

步驟6:評價粒子的目標(biāo)函數(shù);

步驟7:更新粒子的個體最優(yōu)值,更新粒子的外部檔案;

步驟8:判斷迭代次數(shù)是否滿足最大迭代次數(shù),若成立,則轉(zhuǎn)步驟2;否則輸出最優(yōu)結(jié)果.

4 仿真實驗

4.1 性能指標(biāo)

(1)世代距離(Generational distance,GD)是估計算法運算求得的Pareto最優(yōu)解集與真實Pareto前端的趨近程度,定義如下:

(22)

其中:n表示解集中個體的數(shù)目;di表示個體i到Pareto真實前端最小的歐幾里得距離.di表達式如下:

(23)

GD越小,表明算法得到的Pareto最優(yōu)解集越逼近真實的Pareto前端,此時算法的收斂性就越好;GD的理想值為0,即算法得到的Pareto最優(yōu)解在真實的Pareto前端上.

(2)分布均勻度量(Spacing,SP)是用來衡量算法求得的Pareto最優(yōu)解集中分布性能的好壞.定義為

(24)

(25)

其中,k表示目標(biāo)函數(shù)的個數(shù).

SP的值越小,表明算法得到的解的分布性越好;SP的理想值為0,即算法得到的Pareto最優(yōu)解在目標(biāo)空間中是均勻分布的.

4.2 實驗分析與對比

為了驗證DSMOPSO算法的性能,本文選取經(jīng)典的多目標(biāo)測試函數(shù)進行數(shù)值實驗[14-15],并將算法與NSGA-II、SPEA2和CMOPSO算法進行對比,其中CMOPSO表示基于自適應(yīng)網(wǎng)格的多目標(biāo)粒子群優(yōu)化算法.設(shè)置種群規(guī)模為100,最大迭代次數(shù)為300,外部檔案集規(guī)模為100,分別將算法NSGA-II、SPEA2、CMOPSO、DSMOPSO獨立運行30次.測試函數(shù)如表1,實驗都是在win7系統(tǒng)matlab 2012a中完成的,電腦配置為Intel(R) Core(TM) i5-3317U CPU @ 1.70GHz.

表1 測試函數(shù)

各個算法在7種測試函數(shù)上所得關(guān)于GD指標(biāo)和SP指標(biāo)的統(tǒng)計結(jié)果見表2、表3.除了DTLZ2、DTLZ4測試函數(shù),DSMOPSO算法對其它5種測試函數(shù)都具有較好的收斂性和均勻性.并且明顯優(yōu)于NSGA-II、SPEA2和CMOPSO算法.對測試函數(shù)DTLZ2、DTLZ4,DSMOPSO算法所得結(jié)果顯著優(yōu)于NSGA-II算法.綜上所述,DSMOPSO算法在收斂性和均勻性方面都有所提升.

表2 4中算法7種測試函數(shù)上的GD指標(biāo)比較結(jié)果

表3 4中算法7種測試函數(shù)上的SP指標(biāo)比較結(jié)果

各種算法在每個測試函數(shù)上所得的Pareto前沿如圖1-圖6所示,從圖1-圖4可以明顯看出,DSMOPSO算法所得的Pareto前沿要比NSAG-II、SPEA2和CMOPSO算法所得結(jié)果要好;對測試函數(shù)ZDT6,4種算法都具有較好的均勻性,但有部分偏離了真實的Pareto前沿;對測試函數(shù)DTLZ2和DTLZ4,DSMOPSO算法所得的Pareto前沿的均勻程度較差.

圖1 ZDT1的測試對比

圖2 ZDT2的測試對比

圖4 ZDT4的測試對比

圖5 ZDT6的測試對比

5 結(jié)語

針對無約束多目標(biāo)優(yōu)化問題,本文提出了一種融合擾動策略的多目標(biāo)粒子群優(yōu)化算法.通過自適應(yīng)調(diào)整粒子的參數(shù)以及在速度更新公式中增加擾動項,有效地提高了算法的收斂速度.在算法后期,按照某一特定的發(fā)生概率對外部檔案中的粒子進行擾動,增強了算法的隨機性和多樣性,并且找到了更多的非支配解.最后,通過測試函數(shù)驗證了DSMOPSO算法在收斂性和多樣性方面都有很大的改善,能有效地解決多目標(biāo)優(yōu)化問題.