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

，， ，，

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

0 引言

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

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

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

1 多目標優化問題

以目標函數均為最小化問題為例，連續多目標優化問題定義如下[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支配關系，則稱它們非支配(Non-dominated)。

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

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

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

2 MOEO-MNUM算法設計

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

2.1 主要算法流程

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

輸出：MOEO-PLM算法優化后的最終Pareto解集。

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

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

(2)

(3)

其中:r和r1表示0～1范圍內的隨機數，t表示算法運行的當前迭代次數。

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

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

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

步驟6：將當前個體SC無條件替代為Snd。

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

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

2.2 基于非支配排序的Pareto適應度評價準則

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

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

圖1 Pareto適應度評價準則示意圖

2.3 外部存檔更新機制Update_Achieve

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

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

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

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

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

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

3 實驗測試與分析

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

表1 典型的連續多目標優化測試問題

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

(4)

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

MOEO-MNUM算法的參數設置為Imax=6 000，Amax

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

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

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

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

表2 MOEO-MNUM與其它經典優化算法的性能比較

4 結語

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

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

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