李艷瑋，鄭偉勇

（河南工程學院 計算機學院，河南 鄭州451191）

0 引 言

進化算法的優(yōu)化機制與多目標問題的特性之間存在一定的偏差［1，2］，前者主要利用種群中個體之間的局部梯度信息以及隨機擾動信息，缺乏全局性的導向；后者往往需要在解空間中獲取寬廣分布的優(yōu)化曲面 （線），要求算法具有較強的全局探索能力［3］。分布估計算法是一種基于統(tǒng)計分析的新型優(yōu)化算法，利用當前種群的取值來評估最優(yōu)解集的全局分布特性，進而通過基于統(tǒng)計模型的采樣過程產生新的個體，反過來又進一步更新采樣模型，最終推動算法的迭代演進［4］，顯現出了良好的全局尋優(yōu)性能［5］，但卻嚴重依賴于統(tǒng)計模型的準確性，由于種群中個體數量以及函數計算資源都是有限的，會使得分布估計的模型與真實結果存在偏差。為此，提出了一種基于神經網絡實現分布評估的多目標差分進化算法 （MDE－ED－ASM），在流形空間中分區(qū)域建立不同的分布估計模型，采用基于神經網絡的代理模型來增加分布估計的統(tǒng)計樣本和保持樣本的準確度。同時，設計了自適應參量來調整差分進化算法和分布估計算法的選擇概率，利用高效的差分進化算法來引導種群的分布趨勢。

1 相關描述

多目標優(yōu)化問題是在解空間x∈S∈Rn（n為變量x 的維數）中同時求取函數向量F＝ ｛f1，f2，…，fm，m≥2｝的極值 （假設求取最小值）。由于函數之間存在相互制約的關系，因此不存在能同時達到各個函數極值的單一解，而是最終得到一些由Pareto占優(yōu)概念確定的折中解集，稱為Pareto占優(yōu)解集。對于該解集中的任意一個解x＊ （稱為Pareto占優(yōu)解），不存在任何一個解變量x∈S 使得：fi（x）≤fi（x＊），i＝1，2，…，m，且至少在一個函數上滿足fi（x）＜fi（x＊）。而折中解集內部的解表現為：若在一部分函數上取值優(yōu)于其它解，則必然在另一部分函數上取值差于其它解。

進化算法、分布估計算法和代理模型在求解多目標問題中的作用如圖1所示。

圖1 相關概念在求解多目標問題中的作用

進化算法在每一次迭代過程中，將父代種群Pt＝ ｛xi，i＝1，2，…，p｝通過選擇操作Θ1、交叉操作Θ2和變異操作Θ3得到子代種群P’t＝ ｛x～i，i＝1，2，…，p｜x～i＝Θ3（Θ2（Θ1（xi）））｝，再依據Pareto占優(yōu)概念實現更新操作U，得到新的父代種群Pt＋1＝U （Pt，P’t），經過若干代后，種群中滿足Pareto占優(yōu)概念的個體即為最優(yōu)解集。而分布估計算法則認為最優(yōu)解集服從某一分布模型M（θ1，θ2，…，θl），并假設當前種群Pt中的部分或全部個體反映了最優(yōu)解集的分布情況。其通過統(tǒng)計評估操作E 可以得到模型參數的估計值，，…，＝E（Pt），再基于這些估計值進行模型采樣操作A，得到服從最優(yōu)解集分布規(guī)律的新個體＝A（M（，，…，）），再用這些新個體依據Pareto占優(yōu)概念更新種群，進而提升參數的估計值。如此螺旋上升，使得最終參數估計值趨近于真實值，采樣所得解集也趨近于理論最優(yōu)解集。代理模型鑒于當前有限的種群數量會影響參數估計值的精度，而增加個體數量會增多函數調用的資源，提出采用當前已知的若干最優(yōu)解來建立變量與目標函數之間的映射關系F（x）＝Ψ（x），使得代理模型Ψ能夠在一定精度下取代函數F 的調用，且計算速度快于F。代理模型所得解集P＊t與進化算法所得種群P’t混合得到更多的評估樣本，提高了分布估計的精度。

2 算法設計

2.1 分布估計模型設計

依據Karush－Kuhn－Tucker條件，連續(xù)多目標優(yōu)化問題對應的最優(yōu)解集在解空間中是分段分布在多個流形上的［6］。因此，為了更好評估最優(yōu)解集的分布形式，文中提出的算法MDE－ED－ASM 在建立分布估計模型M 時，先將待抽取的解集做處理：

（1）將所有個體在解變量空間下分成c類，其中每次聚類時c的取值由前一次所構建的代理模型數量確定，每個代理模型有一個類中心，解變量的類別歸屬原則為選擇歐式距離最近的類中心；

（2）假設第k類的個體數量為nk，則記nk個個體的均值為ak，對其進行主成分分析，即按式 （1）求取其協(xié)方差矩陣Rk，再求取Rk的特征值和特征向量，j＝1，2，…，n，其中特征值滿足λkj≥λk（j＋1），再根據式 （2）設定的累積貢獻率η來確定主元的數量q?；谏鲜鲋鞒煞址治鏊脜?，本文算法可得到每個類對應的觀察窗口Φk和窗口的高斯噪聲σk，而該類所在區(qū)域的最優(yōu)解集即均勻分布在此觀察窗口Φk中。具體而言，將第k類中所有個體按照式 （3）投影到前q個主元中，以確定觀察窗口Φk的上界和下界。再考慮到類中個體未必能完全覆蓋所處的流形區(qū)域，因此將上下界按照式 （4）做進一步的擴展，即得到最終的Φk。高斯噪聲σk則代表了窗口的觀察誤差，其按照式（5）計算得到?？梢?，Φk和σk即為本文算法在統(tǒng)計評估操作E 中所求取的模型參數θ1，θ2，…，θl

其中，Ck表示第k 類樣本所在的類集合，α表示擴展系數，本文設定為10%。

在采樣操作階段，首先產生一個臨時變量y，該變量的每一維均從觀察窗口Φk對應維數的上下界之間隨機生成。然后再生成一個變量ε，其每一維由均值為0，方差為σk的高斯函數生成。新生成的個體即為變量y 和ε的疊加，若在某一維上疊加的結果超出解空間的邊界，則在解空間所確定的范圍內隨機生成該維的取值。本文設定對每個分布估計模型采樣相同數量的樣本，這樣有助于個體總數較少的類也產生大量的新個體，從而加強了空間中稀疏區(qū)域解的密度。

2.2 代理模型設計

采用了多個神經網絡模型分區(qū)域布置的架構。其原因不僅在于最優(yōu)解集是分段分布在不同流形上的，并且從變量x到F 的函數映射形式也通常較為復雜，單一的神經網絡模型是無法準確約近函數映射關系的［7］。設計的代理模型具有3個設計特點：①利用主成分分析方法將解變量映射到主元空間中，以減少神經網絡的節(jié)點規(guī)模；②采用基于高斯核的徑向基 （RBF）神經網絡來提高代理模型的逼近效果；③在不同的類數取值下利用聚類算法劃分出不同的區(qū)域，通過超體積指標測試不同類數下神經網絡模型集的精度，得出最佳的區(qū)域劃分數量。

假設構建c個神經網絡模型，構建模型用的解集存入一個設定最大容量的訓練樣本池，記為TP，其元素的變量取值和目標函數值都是已知的。解集TP 的來源為分布估計算法和差分進化算法所產生子代中的Pareto占優(yōu)個體。本文方法首先用K 均值算法將解集TP 劃分為c 類，c∈［2，cmax］。由于每一類樣本將用于構建一個代理模型，樣本過少將無法有效完成模型的訓練過程。因此當K 均值聚類結果中某一類的樣本數量少于閾值δ時，則計算該類樣本與其它各類中心的歐式距離，按照最近原則并入其余類中。再隨機選取一個樣本數量大于2δ的類，選擇其中距離類中心最遠的樣本s1和距離s1最遠的樣本s2，將其余樣本按照距離s1和s2的遠近劃分成兩個新的類。對于每一個類的樣本，采用與分布估計模型設計中類似的步驟進行主成分分析，得到相應的主元數量q和特征向量v’kj，j＝1，2，…，n，再將類中樣本依照式 （6）投影到主元空間中，得到維數為q的投影向量z，再以此作為神經網絡的輸入節(jié)點個數

本文具體選擇訓練速度快，非線性映射能力強的RBF神經網絡作為具體的代理模型。其輸入節(jié)點數、隱含層節(jié)點數 （即徑向基的個數）和輸出節(jié)點數分別設置為q、2q和m。其余參數，包括各個徑向基的方差、基函數中心以及隱含層與輸出層之間的權重，均以最小化輸出誤差的平方和為目標函數，采用最速梯度法進行有監(jiān)督學習來確定。

在所提算法中，類數c是分布估計模型和代理模型中的重要參數，其顯著影響了算法關于最優(yōu)解集所在分段流形空間的建模精度。因此，本文將類c從2 逐漸增加，在每種類數下進行聚類和神經網絡訓練，再從中選取最好訓練結果對應的類數為最終確定的類數。又由于神經網絡模型以最小化輸出與真實函數值的誤差為目標，不能很好顧及最優(yōu)解集要全面均勻逼近最優(yōu)曲面 （線）的準則，即可能出現曲面上某些小的區(qū)域精度高，其余大而樣本少的區(qū)域精度低。因此，本文采用超體積指標作為評價神經網絡集的訓練結果好壞的標準。該指標通常用于全面評價多目標優(yōu)化算法所得結果的質量［8，9］，如式 （7）所示

其中，IH （·）稱為超體積測度，由文獻 ［10］所述計算方法獲得。其取值越小則說明解集的質量越好。在具體操作中，首先將類數為c時每一類的樣本等分為兩份，一份用于完成前述神經網絡的訓練；另一部分作為驗證樣本，利用得到的神經網絡模型預測函數值Ψ（x），將Ψ（x）和F（x）代入式 （7）中進行計算，再將所有類的超體積指標值求和，求和值最小時對應的c值即為最佳聚類類數。

2.3 算法混合機制的設計

代理模型通過提供大量可靠樣本來提升分布估計模型的性能，但客觀上其預測值總是會與實際函數值存在差異，而差分進化算法則在現有優(yōu)化解集上進行高效搜索以提供若干均勻分布且取值準確的樣本，可加速實現分布估計模型的校準本文選用的差分算子為DE／current－to－rand／1［11］，其具有較好的探索能力，不易導致強收斂到單個極值，并且變異和交叉操作整合到同一公式中，形式簡單，如式 （8）所示

式中：β—— ［0，1］之間隨機選取的參數，r——比例因子，本文設定為 ［0.05，，0.95］之間隨機選取，xi、x1、x2和x3——隨機選取的4個不同個體。

算法MDE－ED－ASM 中每個子代個體依概率ps選擇由分布估計模型生成，或者由差分進化算法生成。概率ps在初始時取為0.5，此后隨著分布估計模型的更新而根據式（9）自適應的變化

式中：Δ——當前各個流行區(qū)間上分布估計模型的整體噪聲幅度，取值越大說明當前模型的分布估計精度受噪聲的影響越大。而Δ1和Δ2分別表示了前一次的噪聲幅度和當前的噪聲幅度，（Δ1－Δ2）的取值大于零則說明分布估計模型的精度提升，更多的個體可以用分布估計模型來生成，以加強全局搜索能力，取值小于零則需要更多調用差分算子來糾正算法的優(yōu)化方向。

2.4 算法流程

基于上述模型的闡述，算法MDE－ED－ASM 的運行流程可描述為：

步驟1 隨機生成p 個個體，記為父代種群Pt，令代數t＝0，計算中每個個體的目標函數值，并按照Pareto占優(yōu)概念選出Pareto占優(yōu)解集，放入訓練池TP中；

步驟2 當t＜ta時，按照差分進化算法的流程產生新個體并更新父代種群，同時將每代得到的Pareto占優(yōu)解放入訓練池TP 中，若TP 中已有的解相對于新放入解不再Pareto占優(yōu)，則予以剔除，若TP中的解數量超出最大值，則按照Pareto占優(yōu)和擁擠距離概念［12］予以約簡；

步驟3 當t≥ta時，依照概率ps決定每個子代個體是由差分算子或分布估計模型生成，同時在每代的末尾更新訓練池TP；

步驟4 當t＝ta時，利用父代種群構建分布估計模型，此時的類數c在 ［2，cmax］之間隨機選?。?/p>

步驟5 當t＞ta且t除以ta的余數為0時，將訓練池中的樣本按照2.2節(jié)所述方法處理，構建神經網絡模型集，并從已有分布估計模型中采樣生成10p 個樣本，用神經網絡模型預測出相應的目標函數值Ψ（x），然后根據Ψ（x）選出其中的Pareto占優(yōu)解，將這些解和父代種群Pt一并作為抽取樣本，用于更新分布估計模型，此外，根據更新前后的噪聲幅度Δ1和Δ2，對概率ps進行更新；

步驟6 當t＝tmax時，將父代中的Pareto占優(yōu)解集作為最終優(yōu)化結果輸出。

3 驗證與分析

為了驗證所提模型的有效性，選擇3 個二維問題及2個高維多目標優(yōu)化問題作為測試對象，并選擇經典多目標優(yōu)化算法NSGA－II［13］和多目標分布估計算法RM－MEDA［6］作為對比算法。其中記二維問題記為F1、F2和F3，F1為2009年進化計算年會 （CEC2009）［13］上提出的多目標測試用例中的第一個測試函數，F2和F3分別與文獻 ［6］中所使用的問題標號相對應，而高維優(yōu)化問題F4和F5分別對應CEC2009上提出的多目標測試用例中的兩個5維優(yōu)化問題R2＿DTLZ2＿M5和R2＿DTLZ3＿M5。所提算法的相關參數設置如下所示：設置種群大小p 為100，訓練池TP為500，參數ta為20，cmax為10，最大函數調用次數為50000次，即最大代數tmax為500代。所有算法均在達到最大函數調用次數時停止，每種算法獨立運行25次，記錄每次所得最優(yōu)解集的逆廣義距離指標IGD 和超體積指標IH－［14］，統(tǒng)計這25 次的指標均值作為評價算法性能的標準，取值越小說明算法的優(yōu)化性能越好。3 種算法的測試結果見表1。

表1中加粗部分表示對應算法在該函數上的優(yōu)化結果最好。可以發(fā)現，所提算法MDE－ED－ASM 除了在函數F3上的超體積指標略差于RM－MEDA 以外，其余的測試結果均好于其它算法；MDE－ED－ASM 和RM－MEDA 均采用分布估計的方法加強全局優(yōu)化能力，獲得的測試結果也表明算法性能好于無分布估計方法的NSGA－II；MDE－EDASM 在高維問題F4 和F5 上的測試結果明顯好于RMMEDA，也表明所提算法在處理高維問題時未出現明顯的性能衰退。

表1 3種算法的測試結果對比

與RM－MEDA 相比，算法MDE－ED－ASM 利用代理模型和差分進化來加強分布估計的性能。為了分析這兩種措施的作用，設計了兩個對比算法，第一種算法去除代理模型，只用差分進化和分布估計得到的子代個體來更新分布估計模型，記為MDE－ED，此時分布估計中的類數隨機生成；第二種算法將差分進化算子替換為式 （10）中的普通算術交叉算子，記為MGA－ED－ASM

以測試問題F1和F4為研究對象，算法的對比結果見表2。

表2 代理模型和差分算子的性能分析

可見代理模型顯著提升了所提算法的性能，而差分進化算子也使得算法有一定的提升。為了進一步說明二者的性能，本文記錄了各個算法優(yōu)化函數F1時，在進化過程中第100代到第5000代之間的一些取值變化情況。這些值包括算法在相應代數所得Pareto占優(yōu)解集的IGD 值，代理模型所確定的最佳類數c，以及反映分布估計模型精度的噪聲幅度值Δ，分別如圖2～圖4所示。

從圖2結果顯示MGA－ED－ASM 采用普通的交叉算子后，盡管最終也得到了較好的IGD 指標，但其相比于MDE－ED－ASM，花費了更多的函數調用次數才得到同等量級的優(yōu)化結果，而MDE－ED的效果則更差，甚至無法得到較高量級的指標。

圖2 代理模型和差分算子對IGD 值的影響

圖3 代理模型和差分算子對類數c值的影響

圖4 代理模型和差分算子對概率ps 值的影響

從圖3結果顯示MGA－ED－ASM 能夠更好的估計出一個穩(wěn)定的最佳類數c，該值在F1函數中為7，而該函數最優(yōu)解集在解空間中的流形分布可以看作是7段一維流形構成的?？梢奙GA－ED－ASM 估計出的類數較為準確地反映了流形的真實結構。

從圖4結果顯示MGA－ED 的選擇概率整體向上爬升，但進化中出現較大的抖動。這是由于去除代理模型后，分布估計模型缺少足夠的樣本，影響了評估精度，需要更多借助差分算子來改善性能。

4 結束語

設計的基于分布估計和差分進化的多目標優(yōu)化算法提出了基于RBF神經網絡的代理模型，有效建立了分布估計模型、代理模型與Pareto最優(yōu)解集所處流形之間的映射關系。通過多組優(yōu)化問題的測試和分析驗證了所提算法的性能。其整體性能好于同樣適用分布估計模型的算法RMMEDA。此外，實驗分析也表明差分算子和代理模型能夠加快算法的優(yōu)化速度，使其在同樣函數調用次數下得到更好的優(yōu)化結果。而代理模型中采用超體積指標自適應確定最佳類數c的方法，既避免了參數設置的問題，又較為準確評估出了流形的分段數量，提升了分布估計模型和代理模型的性能。

［1］GONG Maoguo，JIAO Licheng，YANG Dongdong，et al.Research on evolutionary multi－objective optimization algorithms［J］.Journal of Software，2009，20 （2）：271－289 （in Chinese）.［公茂果，焦李成，楊咚咚，等.進化多目標優(yōu)化算法研究 ［J］.軟件學報，2009，20 （2）：271－289.］

［2］Zhou A，Qu BY，Li H，et al.Multiobjective evolutionary algorithms：A survey of the state of the art［J］.Swarm and Evolutionary Computation，2011，1 （1）：32－49.

［3］KONG Weijian，DING Jinliang，CHAI Tianyou.Survey on large－dimensional multi－objective evolutionary algorithms ［J］.Control and Decision，2010，25 （3）：321－326 （in Chinese）.［孔維健，丁進良，柴天佑.高維多目標進化算法研究綜述［J］.控制與決策，2010，25 （3）：321－326.］

［4］LIANG Yujie，XU Feng.Adaptive hybrid multi－objective estimation of distribution evolutionary algorithm ［J］.Computer Engineering and Applications，2014，50 （5）：46－50 （in Chinese）.［梁玉潔，許峰.自適應混合多目標分布估計進化算法［J］.計算機工程與應用，2014，50 （5）：46－50.］

［5］LI Li，LI Yanyan.Multi－objective clustering ensemble algorithm based on knees solutions and differential evolution ［J］.Computer Engineering and Design，2014，35 （8）：2912－2916（in Chinese）.［李莉，李妍琰.基于熱點解和差分進化的多目標聚類集成算法 ［J］.計算機工程與設計，2014，35 （8）：2912－2916.］

［6］Zhang Q，Zhou A，Jin Y.RM－MEDA：A regularity modelbased multiobjective estimation of distribution algorithm ［J］.IEEE Transactions on Evolutionary Computation，2008，12（1）：41－63.

［7］LONG Teng，GUO Xiaosong，PENG Lei，et al.Optimization strategy using dynamic radial basis function metamodel based on trust region ［J］.Chinese Journal of Mechanical Engineering，2014，50 （7）：184－190 （in Chinese）.［龍騰，郭曉松，彭磊，等.基于信賴域的動態(tài)徑向基函數代理模型優(yōu)化策略 ［J］.機械工程學報，2014，50 （7）：184－190.］

［8］LI Miqing，ZHENG Jinhua.An indicator for assessing the spread of solutions in multi－objective evolutionary algorithm［J］.Chiness Journal of Computers，2011，34 （4）：647－664（in Chinese）.［李密青，鄭金華.一種多目標進化算法解集分布廣度評價方法［J］.計算機學報，2011，34 （4）：647－664.］

［9］Ulrich T，Bader J，Zitzler E.Integrating decision space diversity into hypervolume－based multiobjective search ［C］／／In Proceeding of 12th Annual Conference on Genetic and Evolutionary Computation，2010：455－462.

［10］Bader J，Zitzler E.HypE：An algorithm for fast hypervolume－based many－objective optimization ［J］.Evolutionary Computation，2011，19 （1）：45－76.

［11］Mininno E，Neri，Cupertino F，et al.Compact differential evolution ［J］.IEEE Transactions on Evolutionary Computation，2011，15 （1）：32－54.

［12］ZHAN Teng，ZHANG Yi，ZHU Dalin，et al.Cellular multi－objective genetic algorithm based on multi－strategy differential evolution ［J］.Computer Integrated Manufacturing Systems，2014，20 （6）：1342－1351 （in Chinese）. ［詹騰，張屹，朱大林，等.基于多策略差分進化的元胞多目標遺傳算法［J］. 計算機集成制造系統(tǒng)，2014，20 （6）：1342－1351.］

［13］LI Xueqiang，HAO Zhifeng，HUANG Han.Multi－objective evolutionary algorithm based on direction selection search ［J］.Journal of South China University of Technology （Natural Science Edition），2011，39 （2）：130－135 （in Chinese）.［李學強，郝志峰，黃翰.基于分方向選擇搜索的多目標進化算法 ［J］.華南理工大學學報 （自然科學版），2011，39 （2）：130－135.］

［14］JIANG Yanjun，JIANG Jianguo，ZHANG Yuhua.Objectoriented reconfiguration of shipboard power network using multi－objective grid evolutionary algorithm ［J］.Electric Power Automation Equipment，2013，33 （3）：26－32 （in Chinese）.［蔣燕君，姜建國，張宇華.采用多目標網格進化算法并面向對象的艦船電網重構 ［J］.電力自動化設備，2013，33 （3）：26－32.］