基于多點(diǎn)非均勻變異的多目標(biāo)極值優(yōu)化算法研究

，， ，，

(1.國(guó)網(wǎng)浙江瑞安市供電有限責(zé)任公司，浙江 瑞安 325000；2.浙江九宏電力工程有限公司，浙江 蒼南 325802；3.溫州大學(xué) 電氣數(shù)字化設(shè)計(jì)技術(shù)國(guó)家地方聯(lián)合工程實(shí)驗(yàn)室，浙江 溫州 325035)

0 引言

大量的實(shí)際工程優(yōu)化問(wèn)題都可以描述為典型的計(jì)及多個(gè)性能指標(biāo)且滿(mǎn)足多種約束條件的多目標(biāo)優(yōu)化問(wèn)題[1]。傳統(tǒng)的多目標(biāo)優(yōu)化方法往往將多個(gè)目標(biāo)函數(shù)進(jìn)行加權(quán)求和，整合成單目標(biāo)優(yōu)化問(wèn)題，而這顯然是違背多目標(biāo)優(yōu)化的基本思想。多目標(biāo)進(jìn)化算法因其在解決多個(gè)矛盾目標(biāo)函數(shù)優(yōu)化問(wèn)題時(shí)的強(qiáng)大處理能力，正受到越來(lái)越多的研究與關(guān)注[2-4]。目前，多目標(biāo)優(yōu)化算法存在的主要問(wèn)題包括：如何促使算法加快或更好地逼近問(wèn)題的真實(shí)的Pareto解集(True Pareto)，這就是所謂的收斂性問(wèn)題；另一個(gè)問(wèn)題就是如何最獲得更加均勻分布的最終的Pareto解集，這就是所謂的分布性問(wèn)題[1,5]。以上兩個(gè)問(wèn)題可以說(shuō)是多目標(biāo)優(yōu)化算法的核心問(wèn)題所在。

極值動(dòng)力學(xué)優(yōu)化算法(Extremal optimization,EO)作為一種新穎的優(yōu)化算法[6-7]，最早由Boettcher和Percus于1999年提出，起源于統(tǒng)計(jì)物理領(lǐng)域的自組織臨界(Self-organized criticality,SOC)理論和Bark-Sneppen生物演化模型(BS模型)[8]。相比于遺傳算法(GA)和粒子群算法(PSO)等傳統(tǒng)優(yōu)化算法而言，EO算法具有遠(yuǎn)離平衡態(tài)的動(dòng)力學(xué)特征，從操作上看就是EO算法總是選擇當(dāng)前的最差組員和與其有關(guān)系的組員來(lái)進(jìn)行變異。所以，算法的實(shí)質(zhì)操作只有變異操作而不存在交叉等操作。EO算法自提出起來(lái)，在離散優(yōu)化、連續(xù)優(yōu)化以及各種工程優(yōu)化問(wèn)題中得到了較為成功的應(yīng)用[9-16]，但有關(guān)多目標(biāo)EO算法的研究卻十分有限[17-21]。

本文將提出一種能夠解決連續(xù)多目標(biāo)優(yōu)化問(wèn)題的基于多點(diǎn)非均勻變異(Multi-non-uniform mutation,MNUM)的多目標(biāo)極值優(yōu)化算法，該算法以下簡(jiǎn)稱(chēng)為MOEO-MNUM。該算法的基本思想是將采用Pareto優(yōu)化的基本原理引入到極值優(yōu)化算法中，即在對(duì)當(dāng)前個(gè)體逐個(gè)組員變異后所產(chǎn)生的個(gè)體中，利用Pareto優(yōu)化的概念，選取其中一個(gè)非支配來(lái)無(wú)條件取代當(dāng)前個(gè)體并進(jìn)行外部存檔，經(jīng)逐代優(yōu)化后獲得最終的Pareto解集供決策者使用。通過(guò)對(duì)典型連續(xù)多目標(biāo)優(yōu)化測(cè)試函數(shù)的仿真測(cè)試實(shí)驗(yàn)從而驗(yàn)證本文提出算法相比其它經(jīng)典多目標(biāo)優(yōu)化算法的有效性。

1 多目標(biāo)優(yōu)化問(wèn)題

以目標(biāo)函數(shù)均為最小化問(wèn)題為例，連續(xù)多目標(biāo)優(yōu)化問(wèn)題定義如下[1]：

min{f1(x),f2(x),...,fM(x)},x= (x1,x2,...,xN)

s.t.gj(x)≥0,j= 1,2,...,J;

hk(x) = 0,k= 1,2,...,K;

xiL≤xi≤xiU

(1)

定義1(Pareto支配,Pareto Dominance)決策向量xu∈X:若Pareto支配決策向量xv∈X，記為xu

1)?i∈{1，…，m}滿(mǎn)足fi(xu)≤fi(xv)；

2)?j∈{1，…，m}滿(mǎn)足fj(xu)≤fj(xv)；

此時(shí)，也稱(chēng)決策向量xvPareto支配于決策向量xu。若決策向量xu與決策向量xv不存在Pareto支配關(guān)系，則稱(chēng)它們非支配(Non-dominated)。

定義2 (Pareto最優(yōu)解,Pareto Optimality)決策向量xu∈X稱(chēng)為X上的Pareto最優(yōu)解，當(dāng)且僅當(dāng)?xv∈X使得xv

定義3 (Pareto最優(yōu)解集,Pareto Optimal Set，POS)對(duì)于給定的多目標(biāo)優(yōu)化問(wèn)題f(x)，Pareto最優(yōu)解集(ρ*)定義為：ρ* ={xu∈X|?xv∈X，xv

定義4(Pareto前沿,Pareto Front,PF))對(duì)于給定的多目標(biāo)優(yōu)化問(wèn)題f(x)和Pareto最優(yōu)解集(ρ*)，Pareto前沿(ρf*)定義為：ρf*={f(xu) |xu∈ρ*}。顯然算法得到的最優(yōu)Pareto解集是逼近Pareto前沿。

2 MOEO-MNUM算法設(shè)計(jì)

MOEO-MNUM算法的主要部分包括：隨機(jī)產(chǎn)生單個(gè)個(gè)體，利用MNUM變異來(lái)更新后代，基于非支配排序的Pareto適應(yīng)度評(píng)價(jià)準(zhǔn)則和一個(gè)外部存檔更新機(jī)制。我們首先給出MOEO-MNUM的主要算法流程，其后在給出流程中使用的細(xì)節(jié)模塊。

2.1 主要算法流程

輸入：一個(gè)連續(xù)多目標(biāo)優(yōu)化測(cè)試問(wèn)題，MOEO-MNUM算法的可調(diào)整參數(shù)：最大迭代次數(shù)Imax、外部存檔最大個(gè)數(shù)Amax和MNUM變異的參數(shù)b。

輸出：MOEO-PLM算法優(yōu)化后的最終Pareto解集。

步驟1：隨機(jī)產(chǎn)生一個(gè)個(gè)體SC，并令外部存檔A為空。

步驟2：通過(guò)當(dāng)前個(gè)體SC逐個(gè)組員進(jìn)行MNUM變異，并保持其它組員不變，產(chǎn)生N個(gè)子代個(gè)體{Si,i=1,2,…,N}，其中N為變量個(gè)數(shù)即組員個(gè)數(shù)。MNUM變異具體實(shí)現(xiàn)如下方程所示：

(2)

(3)

其中:r和r1表示0～1范圍內(nèi)的隨機(jī)數(shù)，t表示算法運(yùn)行的當(dāng)前迭代次數(shù)。

步驟3：對(duì)這N個(gè)子代個(gè)體{Si,i=1,2,…,N}使用基于非支配排序的Pareto適應(yīng)度評(píng)價(jià)準(zhǔn)則進(jìn)行排序。

步驟4：如果只存在一個(gè)非支配個(gè)體，令該個(gè)體為Snd；如果存在多個(gè)則隨機(jī)選擇一個(gè)個(gè)體作為Snd。

步驟5：?jiǎn)⒂没趽頂D度距離的外部存檔更新機(jī)制Update_Achieve(Snd,Achieve)，用Snd來(lái)更新外部存檔。

步驟6：將當(dāng)前個(gè)體SC無(wú)條件替代為Snd。

步驟7：不斷重復(fù)步驟2～7，直至滿(mǎn)足停止條件或達(dá)到最大迭代次數(shù)。

步驟8：將外部存檔作為到目前為止最優(yōu)化的Pareto解集輸出。

2.2 基于非支配排序的Pareto適應(yīng)度評(píng)價(jià)準(zhǔn)則

MOEO-MNUM利用Pareto支配的概念來(lái)定義變異后個(gè)體的適應(yīng)度值。具體適應(yīng)度賦值準(zhǔn)則為：個(gè)體適應(yīng)度值=解集中支配該個(gè)體的其他個(gè)體的個(gè)數(shù)。顯然，適應(yīng)度值為0的個(gè)體為解集中的非支配個(gè)體，適應(yīng)度值越小該個(gè)體越優(yōu)。

以?xún)赡繕?biāo)優(yōu)化問(wèn)題為例，目標(biāo)函數(shù)分別為f1和f2，假設(shè)當(dāng)前個(gè)體為S=(x1,x2,x3,x4,x5)，通過(guò)當(dāng)前個(gè)體S逐個(gè)組員變異并保持其它組員不變的基于MNUM變異方式，產(chǎn)生5個(gè)子代個(gè)體，分別為SA=(xm1,x2,x3,x4,x5),SB=(x1,xm2,x3,x4,x5),SC=(x1,x2,xm3,x4,x5),SD=(x1,x2,x3,xm4,x5)和SE=(x1,x2,x3,x4,xm5)且如圖1所示。由Pareto適應(yīng)度評(píng)價(jià)準(zhǔn)則知，以上5個(gè)解的Pareto適應(yīng)度值分別為f(SA)=0，f(SB)=f(SC)=f(SD)=1，f(SE)=4。

圖1 Pareto適應(yīng)度評(píng)價(jià)準(zhǔn)則示意圖

2.3 外部存檔更新機(jī)制Update_Achieve

MOEO-MNUM為了不丟失歷代尋優(yōu)過(guò)程中的優(yōu)秀非支配解，引入外部存檔更新機(jī)制來(lái)保存這些優(yōu)秀個(gè)體。MOEO-MNUM的外部存檔的保存的最大個(gè)數(shù)是一定的，有用戶(hù)自行設(shè)置。因此，當(dāng)外部存檔達(dá)到最大個(gè)數(shù)時(shí)，新的個(gè)體若要進(jìn)入外部存檔就需要進(jìn)行甄別選擇，達(dá)到真正存優(yōu)的目的。

假設(shè)新產(chǎn)生的個(gè)體為Snd，則MOEO-MNUM外部存檔更新機(jī)制如下[17]：

1)如果外部存檔中至少有一個(gè)體能夠支配個(gè)體Snd，則個(gè)體Snd不能加入外部存檔。

2)如果個(gè)體Snd能夠支配外部存檔中的某些個(gè)體，則將這些個(gè)體移除，并將個(gè)體Snd加入外部存檔。

3)如果外部存檔中的個(gè)體與個(gè)體Snd互不支配時(shí)，若外部存檔個(gè)數(shù)未達(dá)到最大個(gè)數(shù)Amax，則將個(gè)體Snd加入外部存檔；若外部存檔個(gè)數(shù)達(dá)到最大個(gè)數(shù)Amax，則若個(gè)體Snd位于外部存檔最擁擠的地方(由下面的擁擠距離準(zhǔn)則判斷得出)，則不加入外部存檔；否則個(gè)體S將替代掉位于外部存檔最擁擠的地方的個(gè)體而加入外部存檔。

MOEO-MNUM利用由Deb等人[2]在NSGA-II中提出的擁擠距離準(zhǔn)則來(lái)選擇出外部存檔中處于最擁擠的地方的個(gè)體。我們首先將新產(chǎn)生的個(gè)體Snd連同外部存檔中的所有個(gè)體聯(lián)合在一起計(jì)算每個(gè)個(gè)體的擁擠距離。需要注意的是為保護(hù)每個(gè)目標(biāo)的極端值，將所在個(gè)體的擁擠距離賦值為無(wú)窮大。

3 實(shí)驗(yàn)測(cè)試與分析

采用國(guó)際上通用的6個(gè)經(jīng)典多目標(biāo)標(biāo)準(zhǔn)測(cè)試函數(shù)[2]來(lái)驗(yàn)證本文所設(shè)計(jì)的MOEO-MNUM算法的性能。表1列出了本文所用的測(cè)試函數(shù)SCH、ZDT1、ZDT2、ZDT3、ZDT4和ZDT6，包括測(cè)試函數(shù)的表達(dá)式、變量維數(shù)、變量界限、Pareto前沿特點(diǎn)。

表1 典型的連續(xù)多目標(biāo)優(yōu)化測(cè)試問(wèn)題

利用文獻(xiàn)[2]中的兩個(gè)性能指標(biāo)來(lái)衡量不同算法的性能。第一個(gè)指標(biāo)是收斂性指標(biāo)γ，衡量的是算法優(yōu)化后得到的Pareto解集與真實(shí)Pareto解集的間的逼近程度。第二個(gè)指標(biāo)是分布性指標(biāo)Δ，衡量的是算法優(yōu)化后得到的Pareto解集的分布均勻性。計(jì)算公式如下：

(4)

式中，df和dl是算法優(yōu)化后的Pareto前沿的邊界點(diǎn)和真實(shí)Pareto前沿的邊界點(diǎn)的歐氏距離，而di是算法優(yōu)化后的Pareto前沿中兩個(gè)連續(xù)點(diǎn)之間的歐氏距離，dm是所有di(1,2,…,N-1)的平均值。顯然一個(gè)越好的算法它的收斂性指標(biāo)越小，分布性指標(biāo)越小。

MOEO-MNUM算法的參數(shù)設(shè)置為Imax=6 000，Amax

=100，b=2。所有實(shí)驗(yàn)基于MATLAB2012b軟件進(jìn)行，運(yùn)行環(huán)境為3.10 GHz,i5-2400的2 GB RAM的PC機(jī)，每個(gè)測(cè)試函數(shù)獨(dú)立運(yùn)行30次。

表2列出了MOEO-MNUM與NSGA-II[2]、PAES[22]、SPEA[23]和SPEA2[24]等經(jīng)典多目標(biāo)進(jìn)化算法的性能比較數(shù)據(jù)，包括收斂性指標(biāo)γ的平均值和方差，分布性指標(biāo)Δ的平均值和方差及其兩個(gè)指標(biāo)的排名。為了便于讀者對(duì)比分析，表格中采用粗體對(duì)獲得的最好性能指標(biāo)進(jìn)行了標(biāo)記。

從表2可以看出，在收斂性方面，盡管MOEO-MNUM在求解SCH問(wèn)題時(shí)稍遜于PAES，在其它5各測(cè)試問(wèn)題的性能排名第1，但綜合來(lái)看MOEO-PLM在收斂性上面還是令人滿(mǎn)意的；在分布性方面，MOEO-MNUM占據(jù)很大優(yōu)勢(shì)，在各個(gè)測(cè)試問(wèn)題上都排名第1，體現(xiàn)出MOEO-MNUM的獨(dú)特性能即具有優(yōu)秀的分布性能。

更進(jìn)一步地，MOEO-MNUM算法求解6個(gè)典型測(cè)試問(wèn)題獲得的最優(yōu)Pareto前沿如圖2所示。不難看出，針對(duì)每個(gè)測(cè)試問(wèn)題，MOEO-MNUM獲得的最優(yōu)Pareto前沿都與真實(shí)Pareto前沿基本重合。換句話(huà)說(shuō)，MOEO-MNUM算法具有求解多目標(biāo)優(yōu)化問(wèn)題最優(yōu)Pareto前沿的潛力。

表2 MOEO-MNUM與其它經(jīng)典優(yōu)化算法的性能比較

4 結(jié)語(yǔ)

圖2 MOEO-MNUM求解6個(gè)典型測(cè)試問(wèn)題獲得的最優(yōu)Pareto前沿

本文提出了一種高效解決連續(xù)多目標(biāo)優(yōu)化問(wèn)題的基于多點(diǎn)非均勻變異的多目標(biāo)極值優(yōu)化算法，簡(jiǎn)稱(chēng)為MOEO-MNUM。通過(guò)對(duì)國(guó)際上通用的6個(gè)多目標(biāo)標(biāo)準(zhǔn)測(cè)試函數(shù)(包括SCH、ZDT1、ZDT2、ZDT3、ZDT4和ZDT6)的仿真實(shí)驗(yàn)，從而驗(yàn)證了本文所設(shè)計(jì)的MOEO-MNUM算法相比與NSGA-II[2]、PAES[22]、SPEA[23]和SPEA2[24]等經(jīng)典多目標(biāo)進(jìn)化算法在多樣性和分布性方面都具有明顯的優(yōu)勢(shì)。另外，本文也對(duì)比了MOEO-MNUM求解6個(gè)典型測(cè)試問(wèn)題獲得的最優(yōu)Pareto前沿與真實(shí)Pareto前沿，更進(jìn)一步地驗(yàn)證了MOEO-MNUM算法具有求解多目標(biāo)優(yōu)化問(wèn)題最優(yōu)Pareto前沿的潛力。

本文提出的多目標(biāo)極值優(yōu)化算法進(jìn)一步深入研究方向包括：1)通過(guò)設(shè)計(jì)更有效的變異操作因子或引入更高效的外部存檔更新機(jī)制對(duì)算法進(jìn)行改進(jìn)；2)將本文提出算法推廣應(yīng)用到復(fù)雜控制系統(tǒng)優(yōu)化設(shè)計(jì)、智能電網(wǎng)多目標(biāo)規(guī)劃和能量管理等實(shí)際工程優(yōu)化問(wèn)題中。