多模態(tài)優(yōu)化問題的鄰域低密度個(gè)體差分進(jìn)化算法①

閔 濤,楊 勝

(西安理工大學(xué) 理學(xué)院應(yīng)用數(shù)學(xué)系,西安 710054)

科學(xué)與工程領(lǐng)域的大多數(shù)優(yōu)化問題本質(zhì)上都是“多模態(tài)”的,這類問題被稱為多模態(tài)優(yōu)化問題,其特點(diǎn)是目標(biāo)函數(shù)同時(shí)具有多個(gè)全局最優(yōu)解或局部最優(yōu)解.傳統(tǒng)使用的求解方法在求解MMOPs 時(shí)須反復(fù)計(jì)算多次,才有可能找到不同的最優(yōu)解,這樣既費(fèi)時(shí)又費(fèi)力.因此,尋找可行有效的求解MMOPs的新算法一直以來備受廣大科技工作者的關(guān)注[1-4].為此,許多被稱為小生境的技術(shù)包括擁擠[5]、共享[6]、聚類[7]、物種[8]和種群拓?fù)鋄9]等被提出.小生境的主要思想是將整個(gè)種群劃分為幾個(gè)小生境(亞種群),每個(gè)亞種群集中于尋找一個(gè)或幾個(gè)最優(yōu)值.

差分進(jìn)化算法(Differential Evolution,DE)[10]是由Storn和Price 在1995年提出的一種全局優(yōu)化啟發(fā)式算法.由于其簡單、有效,已被用于處理各種各樣的優(yōu)化問題,例如全局優(yōu)化問題[11],MMOPs[12],多目標(biāo)優(yōu)化問題[13]等.近年來,一些基于小生境的DE 變體[14-18]被提出以處理MMOPs,但是,這些方法在最優(yōu)解數(shù)量大、維度高和復(fù)雜性高的時(shí)候效果往往不太理想.

本文提出了一種基于鄰域低密度個(gè)體的差分進(jìn)化算法(Low Density Points Differential Evolutionary,LDPDE)求解MMOPs.算法在每一代,首先使用密度峰值聚類的方法求得每一個(gè)個(gè)體的密度,然后,優(yōu)先對鄰域范圍密度低于當(dāng)前個(gè)體的目標(biāo)個(gè)體進(jìn)行突變操作,隨著種群的進(jìn)化,種群個(gè)體逐漸收斂到小生境中心,進(jìn)化過程將會自動的從探索階段轉(zhuǎn)化為收斂階段,進(jìn)而平衡算法的探索與收斂能力.LDPDE 算法的主要特點(diǎn)有:(1)LDPDE是一種基于距離的小生境方法,它可以通過鄰域范圍內(nèi)個(gè)體的密度變化達(dá)到算法探索與收斂之間的平衡.(2)提出了一種新的DE 變異算子,稱為DE/low-density/1,該算子在算法的探索階段可以尋找盡可能多的有效個(gè)體.

1 差分進(jìn)化算法

考慮優(yōu)化模型:

其中,X=[x1,x2,···,xn]為n維向量,Ω ∈Rn為求解區(qū)域,f(·)為目標(biāo)函數(shù).

差分進(jìn)化算法是一種簡單有效的全局優(yōu)化啟發(fā)式算法.與其他進(jìn)化算法類似,DE 有4 個(gè)步驟:初始化、變異、交叉和選擇.標(biāo)準(zhǔn)的DE 算法過程如下:

(1)初始化

首先,DE 從最小和最大界限約束的搜索空間內(nèi)對個(gè)體進(jìn)行均勻隨機(jī)化,可以表示為:

(2)變異

初始化后,從當(dāng)前種群中隨機(jī)選擇的個(gè)體經(jīng)過變異算子產(chǎn)生突變個(gè)體vi.在標(biāo)準(zhǔn)DE 中,使用以下運(yùn)算方法:

(3)交叉

其中,jrand∈{1,2,···,NP}是隨機(jī)選擇的索引,可確保ui至少繼承突變個(gè)體vi中的至少一個(gè)分量.

(4)選擇

選擇運(yùn)算符確定目標(biāo)或?qū)嶒?yàn)個(gè)體是否進(jìn)入到下一代.如果新的實(shí)驗(yàn)個(gè)體的函數(shù)值等于或小于目標(biāo)個(gè)體的函數(shù)值,它將替換相應(yīng)的目標(biāo)個(gè)體.下一代xi,n+1中的目標(biāo)向量為:

最后,DE 繼續(xù)執(zhí)行變異、交叉和選擇運(yùn)算符,直到滿足終止條件為止.算法1 中以偽代碼的形式給出了標(biāo)準(zhǔn)DE的算法過程.

算法1.標(biāo)準(zhǔn)差分進(jìn)化算法(DE)輸入:目標(biāo)函數(shù)(最小值)f(x);比例因子F;交叉率Cr;種群大小NP;進(jìn)化代數(shù)MaxIt.1)隨機(jī)初始化種群 ;for n=1,···,MaxIt do X1=[x1,1,x2,1,···,xNP,1]2)3)for i=1,···,NP do()4)vi=xri1,n+F·xri2,n?xri3,n,5)uj i=■■■■■■■■■vji,rand

6)end for 7)for i=1,···,NP do 8)xi,n+1=■■■■■■■■■ui,f(ui)≥f(xi,n)xi,n,f(ui)

2 準(zhǔn)備工作

2.1 密度峰值聚類

密度峰值聚類[19]是一種簡單有效的快速聚類方法,由Rodriguez和Laio[20]通過發(fā)現(xiàn)潛在簇的密度峰值提出.對于每個(gè)數(shù)據(jù)點(diǎn)x(i),該算法都會計(jì)算其局部密度 ρ(i)以及與距其最近密度更大點(diǎn)的距離σ (i),由此可以得到每個(gè)數(shù)據(jù)點(diǎn)的孤立性.以下介紹密度峰值聚類的原理.

數(shù)據(jù)點(diǎn)x(i)的局部密度的定義如下所示:

其中,dij是第i個(gè)和第j個(gè)數(shù)據(jù)點(diǎn)之間的距離,dc是截止距離.對于截止距離dc,原始論文沒有提供正確設(shè)置的有效方法.在文獻(xiàn)[21]中,作者提出了一種基于潛在熵的方法,可以根據(jù)數(shù)據(jù)域自動設(shè)置.對于一個(gè)數(shù)據(jù)集x(i),i=1,2,···,n,計(jì)算第i個(gè)數(shù)據(jù)點(diǎn)x(i)的電勢 ψ (i):

則熵H為:

其中,歸一化因子z為:

現(xiàn)在只要找到使得H值最小的σ,記為σ′,即可得到截止距離dc.顯然,dc的值一定處于min{‖x(i)?x(j)‖}和max{‖x(i)?x(j)‖}之間,對于簡單的一維優(yōu)化問題本文使用黃金分割法求得 σ,最后將臨界值設(shè)置為dc=3·

2.2 其他多模態(tài)優(yōu)化算法

為了解決多模態(tài)優(yōu)化問題,許多策略被提出并將嵌入到DE 中.以下將簡要介紹與DE 相結(jié)合的各種策略.

(1)擁擠(CDE):文獻(xiàn)[14]將擁擠方案和健身共享嵌入到DE 中,分別形成CDE 算法和SharingDE 算法.在CDE 算法中,對于每個(gè)子代個(gè)體,通過在父代種群中隨機(jī)選擇C個(gè)父代個(gè)體,然后將子代與該群體中最相似(歐氏距離最近)的父代進(jìn)行比較.如果子代更好,它將取代該種群中最相似的父代個(gè)體.否則,子代個(gè)體將被遺棄.SharingDE 算法則利用共享方案來防止種群收斂到同一個(gè)高峰.

(2)物種(SDE):在SDE 算法[15]中,根據(jù)個(gè)體的適宜性和小生半徑r將整個(gè)種群分為幾個(gè)物種.每個(gè)物種都有一個(gè)具有最佳適應(yīng)性的物種種子,并且DE 運(yùn)算符只在當(dāng)前物種種群內(nèi)執(zhí)行.然后將生成的N個(gè)子代個(gè)體與N個(gè)父代個(gè)體合并為一個(gè)種群,從合并種群中選擇N個(gè)最佳個(gè)體,形成一個(gè)新的種群.

(3)聚類:Qu 等[16]提出了嵌入到CDE 算法和SDE算法中的鄰域突變策略(包括NCDE和NSDE)中,DE 運(yùn)算符在每個(gè)個(gè)體的歐幾里得鄰域中執(zhí)行.遵循這一思想,Gao 等[17]提出了一種具有自適應(yīng)策略(包括self-CCDE和CSDE)的聚類DE,它采用自適應(yīng)參數(shù)控制來增強(qiáng)DE的搜索能力.Zhang 等[18]提出了一種新的基于位置敏感哈希的小生境技術(shù)以降低時(shí)間復(fù)雜度,并將其應(yīng)用于NCDE 中,稱為Fast-NCDE 算法.

以上這些方法在處理MMOPs 問題時(shí)已經(jīng)顯示出各方面的有效性,但它們也有一定的缺點(diǎn).一方面,隨著MMOPs 問題全局最優(yōu)解的數(shù)量增加,這些方法將全部最優(yōu)值點(diǎn)找到的機(jī)會就越小;另一方面,在解決具有高維度和高復(fù)雜性的MMOPs 時(shí),幾乎所有這些固定方法都會失效.因此,為解決高維度和高復(fù)雜性的MMOPs,許多其他基于DE的多模態(tài)算法被提出.Biswas 等[22]提出了一種新的信息共享機(jī)制,該機(jī)制使用本地信息矩陣來誘導(dǎo)有效的利基行為,稱為LoINDE 算法(包括LoICDE 算法和LoISDE 算法).同時(shí),他們還提出了一種新的以父代為中心的標(biāo)準(zhǔn)化鄰域(PCNN)變異算子,以維持多個(gè)最優(yōu)值,稱為PNPCDE 算法[23].Wang 等[24]提出了是一種基于距離的小生境方法,稱為MSTDE算法,通過DPR 策略切割少量大的加權(quán)邊來形成多個(gè)小生境,平衡收斂性和多樣性.

3 基于低密度的差分進(jìn)化算法

在本節(jié)中,我們將提出基于密度峰值的差分進(jìn)化算法(LDPDE).

3.1 基于孤立個(gè)體的變異算子

受文獻(xiàn)[25]啟發(fā),提出一種用于多模態(tài)優(yōu)化的新DE變異算子,稱為DE/low-density/1.該算子的主要特征是它在當(dāng)前個(gè)體鄰域中隨機(jī)選擇密度低于當(dāng)前個(gè)體的個(gè)體作為變異算子的目標(biāo)個(gè)體,因此,目標(biāo)個(gè)體可以被選擇變異算子遷移到隔離區(qū)域.在典型的小生境方法中,同一山谷中的個(gè)體傾向于通過在山谷中下降聚集在一起.而在本文提出的方法中,個(gè)體積極地遷移到其他山谷.DE/low-densit/1 中使用的變異算子描述如下:

其中,是從{pnear(j)

3.2 鄰域變異算子

當(dāng)xi,n是xi,n的Nd1鄰 域內(nèi)密度最大的個(gè)體時(shí),find(i)={pnear(j)

和互不相同,Nd3∈{1,2,···,NP?1}是用戶指定的控制參數(shù).Nd3=NP?1的情況與標(biāo)準(zhǔn)DE的差分向量取法相同.F2是比例因子.

3.3 改進(jìn)的變異算子

如圖1所示[25],圖1(a)為鄰域變異算子的行為特征,圖1(b)為基于孤立個(gè)體的變異算子的行為特征.基于孤立個(gè)體的變異算子可以促使種群個(gè)體向孤立個(gè)體附近遷移,提高算法的多模態(tài)開發(fā)能力,而鄰域變異算子只在小生境內(nèi)進(jìn)行,避免差分進(jìn)化的貪婪原則帶來的錯(cuò)誤替換,提高算法的收斂性.

將以上兩種變異操作結(jié)合形成的改進(jìn)的變異算子描述如下:

隨著種群的進(jìn)化,{pnear(j)|j=1,2,···,Nd1}的值會趨于相等,find(i)為空的情況增多,基于孤立個(gè)體的變異算子的使用率下降,鄰域變異算子的使用率提升,進(jìn)而實(shí)現(xiàn)算法從探索階段到收斂階段的轉(zhuǎn)變,平衡算法的探索與收斂能力.

圖1 兩種變異算子的行為特征

LDPDE的算法過程的偽代碼的在算法2 給出.

算法2.基于鄰域低密度個(gè)體的差分進(jìn)化算法(LDPDE)輸入:目標(biāo)函數(shù)(最小值)f(x);比例因子F;交叉率Cr;種群大小NP;最大計(jì)算次數(shù)MaxFEs;鄰域大小Nd1,Nd2,Nd3 1)隨機(jī)初始化種群 ;n=0;X1=[x1,1,x2,1,···,xNP,1]2)3)while FEs<=MaxFEs do 4)n=n+1;5)for i=1,···,NP do 6)di,i=0;7)for j=i+1,···,NP do di,j=dj,i=‖xi,n?x j,n‖2;8)9)end for 10)end for 11)σ′=3·√12)2?1 argmin σ H(σ);for i=1,···,NP do (13))2)ρ(i)=∑j∈IS{i}exp?(dij dc ;14)end for 15)for i=1,···,NP do■■■■■■,find(i)非空■■■■■■,otherwise 16)vi=■■■■■■■■■■■■■■■■■xnear rp1,n+F1·■■■■■■xri2,n?x′ri2,n■■■■■■■■■xnear ri1,n+F2·vji,■■■■■■x′ri2,n?x′ri3,n 17)uj i=18)end for rand

4 實(shí)驗(yàn)與討論

4.1 測試函數(shù)

本文采用了CEC2013 測試套件[26]中所有20 種常用的多模態(tài)測試函數(shù)來評估LDPDE的性能,該測試套件中的測試函數(shù)具有各種不同的特征,這使實(shí)驗(yàn)更加全面且令人信服.下面對這20 個(gè)基準(zhǔn)測試函數(shù)作簡要說明.

F1:Five-Uneven-Peak Trap(1D),x∈[0,30].全局最優(yōu)點(diǎn)數(shù)量為2.

F2:Equal Maxima(1D),x∈[0,1].全局最優(yōu)點(diǎn)數(shù)量為5.

F3:Uneven Decreasing Maxima(1D),x∈[0,1].全局最優(yōu)點(diǎn)數(shù)量為1.

F4:Himmelblau(2D),x1,x2∈[?6,6].全局最優(yōu)點(diǎn)數(shù)量為4.

F5:Six-Hump Camel Back(2D),x1∈[?1.9,1.9],x2∈[?1.1,1.1].全局最優(yōu)點(diǎn)數(shù)量為2.

F6,F8:Shubert(2D,3D),xi∈[?10,10]D,i=1,2,···,D.全局最優(yōu)點(diǎn)數(shù)量分別為18和81.

F7,F9:Vincent(2D,3D),xi∈[0.25,10]D,i=1,2,···,D.全局最優(yōu)點(diǎn)數(shù)量分別為36和216.

F10:Modified Rastrigin-All Global Optima(2D),xi∈[0,1]D,i=1,2,···,D.全局最優(yōu)點(diǎn)數(shù)量為12.

其中,k1=3,k2=4.

剩下的10 個(gè)函數(shù)為4 個(gè)復(fù)合函數(shù)在不同維度大小的情況,把4 個(gè)函數(shù)簡稱為CF1,CF2,CF3和CF4,定義域均為xi∈[?5,5]D,i=1,2,···,D.復(fù)合函數(shù)的具體定義可以參考文獻(xiàn)[26].

F11:CF1(2D).全局最優(yōu)點(diǎn)數(shù)量為6.

F12:CF2(2D).全局最優(yōu)點(diǎn)數(shù)量為8.

F13,F14,F16,F18:CF3(2D,3D,5D,10D).全局最優(yōu)點(diǎn)數(shù)量為6.

F15,F17,F19,F20:CF4(3D,5D,10D,20 D).全局最優(yōu)點(diǎn)數(shù)量為8.

將LDPDE 與幾種基于DE的多模態(tài)算法進(jìn)行比較,包括CDE 算法,SDE 算法,NCDE 算法,NSDE 算法,LoICDE 算法,LoISDE 算法,PNPCDE 算法,Fast-NCDE 算法和MSTDE 算法.這些算法橫跨從2004年到2019年的時(shí)間間隔.此外,為了具有可比性,所有對比算法的參數(shù)配置都與原始論文中的設(shè)置相同.

4.2 參數(shù)設(shè)置

LDPDE 中的放大系數(shù)F1和F2分別設(shè)置為0.9和0.5,交叉速率Cr設(shè)置為0.9,Nd2和Nd3分別為5和15.針對不同的函數(shù)參數(shù)Nd1、種群規(guī)模N和最大計(jì)算次數(shù)MaxFEs設(shè)置如表1所示.

表1 參數(shù)設(shè)置

LDPDE 中的種群規(guī)模、最大計(jì)算次數(shù)MaxFEs和比較算法的結(jié)果參考自文獻(xiàn)[24].所有的結(jié)果都是在同一測試套件中使用相同的MaxFEs下得到的,每種算法均運(yùn)行51 次以進(jìn)行統(tǒng)計(jì)并避免隨機(jī)性.

對于給定的MaxFEs在精度水平ε=10?4下,使用峰值比(Peak Ratio,PR)和成功率(Success Ratio,SR)評估算法的性能.峰值比為找到的全局最優(yōu)解個(gè)數(shù)與所有全局最優(yōu)解數(shù)之比,成功率為所有全局最優(yōu)解被找到次數(shù)與實(shí)驗(yàn)總次數(shù)之比.PR和SR 均為0 到1.0之間的實(shí)數(shù),數(shù)值越大說明算法效果越好.當(dāng)PR和SR 均為1.0 時(shí)說明算法每次都能找到函數(shù)所有的最優(yōu)解.

4.3 結(jié)果與討論

表2列出了LDPDE 與其他多模態(tài)算法在F1-F20上PR和SR的詳細(xì)比較結(jié)果.為了結(jié)果清晰,最佳PR果用黑體標(biāo)出.符號"+"、"?"和" ≈"分別表示LDPDE的性能“顯著優(yōu)于”,“顯著低于”和“與對比算法相當(dāng)”.以CDE 算法為例,本文算法在13 個(gè)函數(shù)上優(yōu)于CDE算法,0 個(gè)低于CDE 算法,7 個(gè)與CDE 算法結(jié)果相當(dāng).

表2 LDPDE 與其他多模態(tài)算法在F1-F20 上PR和SR的詳細(xì)比較結(jié)果

從表2可以看到LDPDE 在所有函數(shù)上都表現(xiàn)很好.對于簡單函數(shù)F1?F5和具有眾多全局最優(yōu)值的函數(shù)F6?F10,LDPDE 除了對于具有216 個(gè)全局最優(yōu)點(diǎn)的F9之 外的其它九個(gè)函數(shù)的PR值 全部達(dá)到了1.0,也就是說LDPDE 算法在這九個(gè)測試函數(shù)上每次都能找到函數(shù)所有的最優(yōu)解,雖然F9的PR值只有0.587,但也明顯優(yōu)于于其它算法.對于最后的十個(gè)高度復(fù)雜多模態(tài)函數(shù)F11?F20 (其中F11?F15為低維,F16?F20為高維),LDPDE的性能幾乎處于絕對的優(yōu)勢地位,只有少數(shù)幾個(gè)算法在一到兩個(gè)函數(shù)可以與本文算法性能相當(dāng),這進(jìn)一步驗(yàn)證了LDPDE 在解決高度復(fù)雜的MMOPs方面的可行性和有效性.

多模態(tài)函數(shù)F1?F20的收斂曲線如圖2(a)-圖2(d)所示,目標(biāo)函數(shù)誤差值為每個(gè)函數(shù)運(yùn)行51 次所得每一代最小值的平均值與函數(shù)極值之差的絕對值,為方便觀察,將縱坐標(biāo)取以 10為底的對數(shù)(值為0時(shí)曲線未畫出).圖2(a)中函數(shù)F1的曲線極短,這是由于F1函數(shù)簡單,算法在很少的進(jìn)化代數(shù)就計(jì)算得出最優(yōu)函數(shù)值導(dǎo)致的.而函數(shù)F3的計(jì)算精度達(dá)到1 0?7之后很難繼續(xù)改進(jìn).其他18 個(gè)函數(shù)收斂曲線呈現(xiàn)明顯的收斂趨勢,雖然隨著函數(shù)復(fù)雜程度的提高收斂速度減慢,但收斂趨勢穩(wěn)定,收斂精度也都能達(dá)到1 0?18,這也體現(xiàn)出本文算法在高維復(fù)雜多模態(tài)函數(shù)優(yōu)化上的優(yōu)勢.

總之,LDPDE 在所有20 個(gè)函數(shù)上與CDE,SDE,NCDE,NSDE,LIPS,LoICDE,LoISDE,PNPCDE,self-CCDE,self-CSDE,fast-NCDE和MSTDE 算法相比PR值都優(yōu)于或相當(dāng)于對比算法.收斂性分析結(jié)果表明,LDPDE 可以在搜索與收斂之間找到良好的平衡,具有解決MMOPs的潛力.

圖2 目標(biāo)函數(shù)誤差值收斂曲線

5 結(jié)論與展望

針對多模態(tài)優(yōu)化問題,本文提出了一種基于鄰域低密度個(gè)體的差分進(jìn)化算法LDPDE,它可以通過鄰域范圍內(nèi)個(gè)體的密度變化達(dá)到算法探索與收斂之間的平衡,有效提升了算法的可靠性和收斂速度,結(jié)合新提出的DE/low-density/1 變異算子,使得算法在探索階段可以尋找盡可能多的有效個(gè)體.在CEC2013 多模態(tài)基準(zhǔn)測試的實(shí)驗(yàn)結(jié)果表明,LDPDE 對比其它多種基于DE的多模態(tài)優(yōu)化算法具有更好的性能,顯示了LDPDE在求解多模態(tài)優(yōu)化問題上的優(yōu)勢.