融合擾動策略的多目標粒子群優化算法

王進成,顧銀魯

(銀川能源學院 基礎部,寧夏 銀川 750105)

0 引言

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

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

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

1 多目標優化問題及基本概念

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

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

(1)

(2)

以下介紹多目標優化問題中常用的幾個基本概念[11-12].

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

(3)

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

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

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

(4)

則稱x1支配x2,記作x1x2.

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

┐?x∈Ω:xx*.

(5)

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

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

(6)

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

(7)

2 粒子群優化算法

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

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

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

(10)

其中:ωmax,ωmin分別為慣性權重的最大值和最小值,一般取值為0.9和0.4;t表示當前迭代次數;Tmax表示最大迭代次數.

3 融合擾動策略的多目標粒子群優化算法

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

3.1 外部檔案維護策略

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

(11)

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

(12)

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

3.2 個體最優解與全局最優解選取策略

3.2.1 個體最優值選取策略

(13)

3.2.2 全局最優解選取策略

本文采用隨機權重的方法將外部檔案中的多目標向量轉化成單目標,從該權重下隨機選取全局最優粒子,具體方法如下:

(14)

(15)

其中,ai為隨機產生的權重.

3.3 參數改進策略

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

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

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

(16)

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

(17)

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

(18)

(19)

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

3.4 擾動策略

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

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

(20)

其中,a為極小的隨機數,取值為0.001.

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

(21)

3.5 DSMOPSO的步驟及算法流程圖

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

圖1 DSMOPSO算法流程圖

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

步驟2:計算每個粒子的目標函數值,保持每個粒子的初始位置和目標函數值;

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

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

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

步驟6:評價粒子的目標函數;

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

步驟8:判斷迭代次數是否滿足最大迭代次數,若成立,則轉步驟2;否則輸出最優結果.

4 仿真實驗

4.1 性能指標

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

(22)

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

(23)

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

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

(24)

(25)

其中,k表示目標函數的個數.

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

4.2 實驗分析與對比

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

表1 測試函數

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

表2 4中算法7種測試函數上的GD指標比較結果

表3 4中算法7種測試函數上的SP指標比較結果

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

圖1 ZDT1的測試對比

圖2 ZDT2的測試對比

圖4 ZDT4的測試對比

圖5 ZDT6的測試對比

5 結語

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