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

，， ，，

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

0 引言

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

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

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

1 多目標優(yōu)化問題

以目標函數(shù)均為最小化問題為例，連續(xù)多目標優(yōu)化問題定義如下[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}滿足fi(xu)≤fi(xv)；

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

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

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

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

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

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

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

2.1 主要算法流程

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

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

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

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

(2)

(3)

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

步驟3：對這N個子代個體{Si,i=1,2,…,N}使用基于非支配排序的Pareto適應(yīng)度評價準則進行排序。

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

步驟5：啟用基于擁擠度距離的外部存檔更新機制Update_Achieve(Snd,Achieve)，用Snd來更新外部存檔。

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

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

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

2.2 基于非支配排序的Pareto適應(yīng)度評價準則

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

以兩目標優(yōu)化問題為例，目標函數(shù)分別為f1和f2，假設(shè)當(dāng)前個體為S=(x1,x2,x3,x4,x5)，通過當(dāng)前個體S逐個組員變異并保持其它組員不變的基于MNUM變異方式，產(chǎn)生5個子代個體，分別為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)度評價準則知，以上5個解的Pareto適應(yīng)度值分別為f(SA)=0，f(SB)=f(SC)=f(SD)=1，f(SE)=4。

圖1 Pareto適應(yīng)度評價準則示意圖

2.3 外部存檔更新機制Update_Achieve

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

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

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

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

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

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

3 實驗測試與分析

采用國際上通用的6個經(jīng)典多目標標準測試函數(shù)[2]來驗證本文所設(shè)計的MOEO-MNUM算法的性能。表1列出了本文所用的測試函數(shù)SCH、ZDT1、ZDT2、ZDT3、ZDT4和ZDT6，包括測試函數(shù)的表達式、變量維數(shù)、變量界限、Pareto前沿特點。

表1 典型的連續(xù)多目標優(yōu)化測試問題

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

(4)

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

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

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

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

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

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

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

4 結(jié)語

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

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

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