王進(jìn)成,顧銀魯

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

0 引言

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

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

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

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

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

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

(1)

(2)

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

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

(3)

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

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

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

(4)

則稱(chēng)x1支配x2,記作x1x2.

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

┐?x∈Ω:xx*.

(5)

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

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

(6)

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

(7)

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

PSO是一種模擬鳥(niǎo)群覓食行為的群智能優(yōu)化算法,PSO算法的提出激發(fā)了許多研究者對(duì)群智能優(yōu)化算法的研究.在PSO算法中,每只鳥(niǎo)都被看作是一個(gè)粒子,粒子由gbest和pbest變化來(lái)尋找最優(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)重、個(gè)體經(jīng)驗(yàn)系數(shù)、社會(huì)經(jīng)驗(yàn)系數(shù),ω由式(10)確定,c1和c2一般取值為2;xi和vi表示第i個(gè)粒子的位置和速度;pbesti表示第i個(gè)粒子的pbest位置;gbest表示整個(gè)種群的gbest位置,在多目標(biāo)問(wèn)題上,gbest也被視為非支配解;j為維數(shù);t為當(dāng)前迭代次數(shù);r1和r2為[0,1]之間的兩個(gè)隨機(jī)數(shù).慣性權(quán)重ω由下式確定:

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

(10)

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

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

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

3.1 外部檔案維護(hù)策略

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

(11)

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

(12)

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

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

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

(13)

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

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

(14)

(15)

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

3.3 參數(shù)改進(jìn)策略

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

雖然多目標(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是自我認(rèn)知參數(shù)的初始值和最終值;c2s和c2f是社會(huì)認(rèn)知參數(shù)的初始值和最終值;tmax表示最大迭代次數(shù);在自適應(yīng)策略中,ωmax=0.9,ωmin=0.4,c1s=c2f=2.5,c1f=c2s=0.5,tmax=200.

3.4 擾動(dòng)策略

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

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

(20)

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

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

(21)

3.5 DSMOPSO的步驟及算法流程圖

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

圖1 DSMOPSO算法流程圖

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

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

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

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

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

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

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

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

4 仿真實(shí)驗(yàn)

4.1 性能指標(biāo)

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

(22)

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

(23)

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

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

(24)

(25)

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

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

4.2 實(shí)驗(yàn)分析與對(duì)比

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

表1 測(cè)試函數(shù)

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

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

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

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

圖1 ZDT1的測(cè)試對(duì)比

圖2 ZDT2的測(cè)試對(duì)比

圖4 ZDT4的測(cè)試對(duì)比

圖5 ZDT6的測(cè)試對(duì)比

5 結(jié)語(yǔ)

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