基于統計信息反饋的分步多目標優化

王學武， 謝祖洪， 周 昕， 顧幸生

（華東理工大學能源化工過程智能制造教育部重點實驗室，上海 200237）

一個連續的非約束多目標問題（Multi-Objective Optimization Problem, MOP）擁有多個相互矛盾、相互影響的目標，且這些目標需要同時被優化[1]。多目標優化問題是工業生產和日常生活中經常遇到的問題，它遵循效益最大化和成本最小化等基本原則。效益可能是多種效益，即經濟效益、社會效益等；成本或損失也可能包括生產成本和非生產成本，甚至可能是環境污染這類的其他目標。以焊接路徑規劃為例，焊接目標通常有焊接路徑長度、能耗、變形等。目前多目標優化問題的研究已引起了廣泛的關注，被應用于任務調度、工程設計、系統控制、焊接路徑規劃等眾多領域。

假設x,y∈Ω 是某一多目標優化問題的任意兩個解，當滿足fi(x)fi(y), ?i∈1,2,···,m時，我們定義x支配y，即x?y；其中 Ω ?RD表示決策空間，x=(x1,x2,···,xD) 表示由D個參數組成的決策變量，F:Ω →Rm由m個 目 標 函 數 (fi(x),i=1,2,···,m) 構成， Rm表示目標空間。在目標空間中，如果沒有解可以支配x?，則稱x?為Pareto 最優解，也被稱為非支配解，所有的Pareto 最優解組成的集合稱為Pareto 最優解集。將Pareto 最優解集中的所有Pareto 解映射到目標空間，得到Pareto 前沿(Pareto Front, PF)。多目標進化算法(Multi-Objective Evolutionary Optimization Algorithm，MOEA) 致力于在真實PF 附近獲得均勻分布的Pareto 最優解集[2]。

多目標進化算法一直致力于獲得收斂性和分布性俱佳的非支配解集[2]。根據不同的進化機制，多目標進化算法大致分為3 類[3]：基于分解的MOEAs、基于支配關系的MOEAs、基于指標的MOEAs?；诜纸獾腗OEAs 利用聚集函數將多目標優化問題轉化為多個單目標優化子問題，再根據在超平面上均勻分布的參考向量來選擇優秀個體。Zhang 等[4]基于上述分解思想提出了MOEA/D 算法，引起了廣泛關注。在此基礎上改進的算法還有MOEA/D-DE[5]、MOEA/D-AS[6]、MOEA/D-AAP[7]?；谥潢P系的MOEAs 結合非支配關系和小生境技術選擇后代解集，主要算法有NSGA-Ⅱ[8]、SPEA2[9]、PESA-Ⅱ[10]?；谥笜说腗OEAs 利用性能指標指導算法搜索過程和后代選擇過程，主要算法有IBEA[11]、SMSEMOA[12]、HyPE[13]。

除了傳統的MOEAs 外，還有很多學者提出了綜合性算法來增強收斂性和分布性。Deb 等[14]結合非支配排序和參考點選擇后代解，將算法拓展用以解決高維多目標優化問題。Sato 等[15]通過對傳統給予懲罰的邊界交叉法(Penalty-Based Boundary Intersection Approach，PBI) 和權重向量法(Weighted Sum，WS)進行拓展，提出了一種新的聚合函數，即反轉PBI(Inverted Penalty-Based Boundary Intersection，IPBI)。Trinadh 等[16]提出了一種基于指標(ISDE+) 的多目標進化算法，該指標計算個體之間的歐氏距離用以估計個體在種群中的密度。Sun 等[17]提出了一種新的存活時間指標來指導差分進化重組算子，以此平衡算法中個體的開發性和勘探性。

傳統的多目標進化算法通常同時考慮解的收斂性和分布性，在算法搜索初期會生成大量的支配解，造成計算資源的浪費。因此，本文提出了基于統計信息反饋的分步多目標優化算法（A Stepwise Multi-Objective Evolutionary Optimization Algorithm Based on Statistical Feedback Information，SFI-SMOEA ）。SFI-SMOEA 分為3 個階段，第一階段主要進行單目標最優值探索；第二階段主要進行Pareto 前沿的探索；第三階段進行局部優化，加強分布不均和收斂性不足的部分區域的探索。在算法搜索后期，性質差異過大的兩個親本生成的解極有可能是支配的，也會造成計算資源的浪費；于是SFI-SMOEA 按照目標函數值將性質差異較大的解分為不同群體，分別對不同群體的解進行聚類分析，對優秀個體進行評估；再根據評估信息指導種群親本選擇過程，保證優質解的交配次數；根據上一次迭代信息生成偏好的優質解，并調整解集結構。

1 SFI-SMOEA 算法框架

傳統的多目標進化算法[4,8,10]通常協同考慮全局的收斂性或者多樣性，可能導致算法對于單目標極值探索的不足，而且在搜索初期會生成大量支配解，造成計算資源的浪費。SFI-SMOEA 將整個優化算法分為3 個階段：

（1）單目標探索階段。在此階段，放棄對整個Pareto 前沿的探索，分別對優化問題的多個目標進行相對獨立的探索，使其快速找到每個單目標的最優解。

（2）單目標到多目標的過渡階段。在單目標探索階段結束后，解圍繞在各個目標的最優值附近。此階段的主要任務是加強對整個Pareto 前沿的探索，尤其針對部分未覆蓋區域，這是為了促進算法的分布性。

（3）群體劃分局部優化階段。經過第一、二階段的探索，形成基本的Pareto 前沿，但是局部收斂性不足。因此，第三階段的主要任務是根據目標函數值進行群體劃分，利用反饋信息加強局部Pareto 前沿的開發。在迭代過程中，根據目標函數值將所有解劃分為不同區域；然后反饋各個區域解的分布情況，在稀疏區域生成更多解，進一步增強算法搜索能力。

SFI-SMOEA 的每個階段包含不同的任務，整個框架如算法1 所示。其中，小生境保留技術參照NSGA-III[14]，包括非支配排序、解與參考點的關聯操作、根據關聯操作選擇下一代種群。

算法1 SFI-SMOEA 算法流程

1.1 單目標探索階段

在單目標探索階段，分別對每個目標最優值進行探索，期望盡快找到每個目標的最優值。在此階段，將多目標優化問題轉化成m個單目標優化問題，并利用改進的單目標遺傳算法進行求解。

1.1.1 挑選精英個體 在傳統遺傳算法[18]中，親本的選擇是根據適應度進行的，適應度高的解有更大概率被選為親本。當算法進行了一段時間后，解空間內解的相似度很高，進行交配的領域變小，可能導致算法陷入局部最優。在處理此類問題時，有學者提出采用事件觸發機制[19]增強算法跳出局部最優的能力。對于遺傳算法求解單目標優化問題而言，一方面我們希望優秀個體可以獲得更大的交配機會；另一方面，我們也希望保持種群的多樣性，避免算法陷入局部最優?；谝陨戏治?，將解按照單目標適應度進行排序，挑選出部分優秀個體建立外部檔案（Xg），其中每個目標優秀個體的數目根據種群大小和待優化問題的目標維度確定。通過對部分個體進行評估，確定優秀個體的交配次數，保證優秀個體的基因得以保留；然后刪除種群中多余的重復解，隨機生成新的解，直到滿足種群數目要求。

1.1.2 對優秀個體進行相似性和離散程度的評估由于對整個種群中的每一個個體進行價值評估計算較為復雜，因此只對通過適應度值挑選出的優秀個體進行價值評估。對優秀個體進行相似性和離散程度的統計，采用基于相關性的密度估計指標ICDE，類似于統計學中相關系數的計算[20]，如式(1)所示。

1.1.3 根據評估結果指導親本選擇 設計智能優化算法的關鍵是平衡算法在尋優過程中的開發性和探索性。本文利用ICDE指導親本選擇過程，從而實現開發性和探索性的平衡。由1.1.2 節可知，越大，表示個體i與其他個體的相似度越低，離散度越高。此時，說明個體i具有很高的開發價值，應該給個體i更多的配偶，從而加快算法向個體i收斂。反之，說明算法可能陷入局部最優。此時應該增強算法隨機性和解空間領域的大小，減少優秀個體的交配次數，刪除種群內多余重復解，借此搜索到表現更優的個體，從而增強算法的“爬山”能力。其中優秀個體的交配次數如式(3)所示。

式中：N為種群大??；表示向下取整； α 表示對優秀個體的重視程度， α 越大，優秀個體交配次數越多，本文設定 α =3 。由于親本每次交叉可以獲得兩個后代解，因此將交配次數除以2。

根據評估結果指導親本選擇過程的偽代碼如算法2 所示，即基于優秀個體的親本選擇算子(Parent Selection Operator Based on Excellent Individuals，EIPS)。

算法2 基于優秀個體的親本選擇算子(EIPS)

第一階段單目標探索階段包括挑選優秀個體、對優秀個體進行相似性和離散程度的評估、根據評估信息指導種群親本選擇過程。圖1 所示為部分三維測試案例第一階段解的分布情況，可以看到其中的大部分解都圍繞在各個目標最優值附近。

圖1 部分三維測試案例第一階段解集分布情況Fig.1 Distribution of solution sets in the first stage of some 3-objective test cases

1.2 單目標到多目標的過渡階段

過渡階段的首要任務是使種群初步收斂到Pareto 前沿上，其中包括對個體進行群體劃分，根據劃分結果指導親本選擇過程。但是在單目標探索結束后，種群中個體大多集中在各個目標的最優值周圍，因此需要對種群中的個體進行聚類分析，再根據分析結果合理地分配交配資源，使其快速收斂到Pareto 前沿。

1.2.1 根據目標函數值劃分種群 整個種群的個體差異較大，不便于進行分析，因此根據個體的目標函數值將其劃分成不同群體。同一群體內，個體性質相近，而與其他群體中的個體性質差異較大。劃分群體的個數取決于待優化問題的目標維度。在歐式空間中劃分區域，本質是邊界的確定，本文設置的邊界是過原點的向量。對于M維的優化問題，邊界向量的生成采用的是邊界交叉構造權重向量的方法[21]。在標準超平面上，按照式(4)生成均勻的參考點。每一維目標被均勻地分割成p份，因此邊界向量的個數為 n umw。為了減少復雜度，本文設定p=2 。對于M維優化問題，解被分為(M+1)個群體。

圖2 所示為三維優化問題的種群劃分示意圖。每一維目標被均勻地分為2 份；共有6 個權重向量w1=(0,0,1) 、w2=(0.5,0,0.5) 、w3=(0,0.5,0.5) 、w4=(1,0,0) 、w5=(0.5,0.5,0) 、w6=(0,1,0) 。將 目 標 函數值空間分為4 個區域：w1、w2、w3圍成的空間為1 號區域；w2、w3、w5圍成的空間為2 號區域；w2、w4、w5圍成的空間為3 號區域；w3、w5、w6圍成的空間為4 號區域。

圖2 三維優化問題的種群劃分Fig.2 Population division of for 3-objective optimization problems

1.2.2 根據種群劃分結果指導親本選擇 種群類別劃分的區域是參考權重向量生成方式進行的，理想情況下，每個區域內的個體數由被優化問題的Pareto分布決定。由于在單目標探索階段結束后，解大都分布在各個目標最優值周圍，可能導致部分區域解的個數很少，甚至有些區域沒有解，此時應該加大此區域中解的生成，從而使得解盡快收斂到Pareto 前沿上。對不同類別的個體數進行統計，再根據統計結果確定親本選擇的概率，從而實現對各個區域個體數的控制。其中，在同一區域內進行親本選擇的概率Ps由式（5）計算：

其中：ns為同類別個體的數量；N為種群中個體的數量；A為控制參數，本文中A=0.5。同類別個體的數量越多，即ns越大，選擇同類別個體作為親本的概率越小，后代生成相似性質解的概率越小，從而實現對各個群體個體數量的控制。根據種群劃分結果指導親本選擇過程的偽代碼如算法3 所示，即基于種群劃分的親本選擇(Parent selection operator based on population division，PDPS)。

算法3 基于種群劃分的親本選擇(PDPS)

1.3 群體劃分局部優化階段

經過第一、二階段的優化后，種群基本收斂到Pareto 前沿上，只有少數區域收斂性不足和解分布不均勻。本階段的首要任務是對種群個體進行群體劃分，分別對各個群體的解進行聚類分析，選擇其中表現優異的個體作為領導者；利用領導者對群體進行收斂性和分布性評價，然后根據評價結果指導親本選擇過程，從而實現收斂性的優化及對分布性的控制。

1.3.1 聚類分析 將種群劃分為若干區域后，同一區域內解的性質相似，便于統計分析。分別對每個區域內的解進行線性回歸分析[22]，模擬出近似的Pareto 前沿，計算解到模擬Pareto 前沿的距離，即。如圖3 所示，陰影部分表示通過線性回歸獲得的近似Pareto 前沿。個體的優劣是通過它的收斂性和分布性決定的，對于最小化問題而言，優秀個體在模擬Pareto 前沿的下方，離Pareto 前沿越遠，說明此個體的收斂性越強。反之，如果個體在模擬Pareto 前沿的上方，說明此個體的收斂性較差。按照1.1.2 節所述方法，對同區域內的個體進行相似性和離散程

圖3 三維PF 線性擬合Fig.3 Linear fitting of 3-objective PF

油田配電網變壓器節能改造的研究…………………………………………………………………………………陳亞莉（3.30）

1.3.2 根據聚類分析結果指導親本選擇 經過實驗發現，性質差異較大的兩個解生成的后代很大概率是支配解，造成計算資源浪費，不能達到使Pareto 收斂的要求。為了避免此類情況，在群體劃分局部優化階段，個體只與同區域或者相鄰區域個體交配。以如圖1 所示的三維問題為例，區域1 和區域2 相鄰，區域3 和區域2 相鄰，區域4 和區域2 相鄰，區域2 和區域1、3、4 都相鄰。區域1 中的個體只與區域1、2 中的個體進行交配。通過聚類分析選出各個區域的優秀個體，優先給此類個體分配配偶，然后在同一區域或者相鄰區域隨機分配配偶，直到交配池數量要求。配偶選擇過程如算法4 所示，即基于領導者的親本選擇(Parent selection operator based on leaders，LPS)。

算法4 基于領導者的親本選擇(LPS)

2 仿真實驗與分析

為了驗證本文算法的性能，選取DTLZ(DTLZ1～DTLZ7)[23]和WFG(WFG1～WFG7)[16]系列測試案例進行實驗，共14 個測試問題，每個測試問題分別測試3、5、8、10 個目標，并與NSGA-III[14]、A-NSGAIII[24]、MOEA/D-M2M[25]、ISDE+[16]等多目標進化算法進行對比。對于模擬二進制交叉和多項式變異的參數，本文進行統一設定。交叉概率pc=1 .0，交叉分布指數 ηc=20 ；變異概率pm=1/D(D為變量維度)，變異分布指數 ηm=20 。

圖4 示出了部分測試案例在1 次運行中通過SFI-SMOEA 獲得的解的分布情況。從圖4 中可以看出，這些測試案例的真實PF 復雜而多樣(包括凹凸不一、有多個局部前沿、各個目標比例不一、退化等)。在這些測試問題中，SFI-SMOEA 均能獲得收斂性和分布性俱佳的Pareto 解集。

圖4 SFI-SMOEA 下部分測試案例的解分布Fig.4 Solutions distribution of some test cases by SFI-SMOEA

為了比較各個算法的性能，采用兩個綜合評價指標，即反轉世代距離(Inverted Generational Distance,IGD)和超體積指標(Hypervolume, HV)[25]。IGD 指標通過計算真實Pareto 解集中的個體(x?)到算法所求的非支配解集中的個體(x)的平均距離(d(x?,x) )得到，如式（6）所示：IGD 能綜合反映MOEA 的收斂性和分布性，IGD 值越小，說明算法的綜合性能越好。

表1 DTLZ 測試案例的HV 平均值（標準差）Table1 HV mean values (standard deviation) of DTLZ test cases

續表1

表2 WFG 測試案例的HV 平均值（標準差）Table2 HV mean values (standard deviation) of WFG test cases

續表2

在56 個測試問題(包括DTLZ 系列和WFG 系列)中，本文算法比NSGA-III、A-NSGA-III、MOEADM2M、ISDE+更好或者相似的比例分別為83.04%、82.14%、94.64%、68.75%。綜合來看，本文算法在DTLZ 和WFG 測試問題上顯著優于MOEAD-M2M，與NSGAIII 和A-NSGAIII 相似。

從各個測試案例的收斂情況來看，對于DTLZ4、WFG1、WFG2 等側重分布性的多目標問題，SFISMOEA 性能比NSGA- III 算法差。

分析后發現，SFI-SMOEA 為了算法的收斂性，第一階段只關注各個目標的最優值，相當于只考慮算法的收斂性，從而導致部分基因缺失，最終使得算法分布性性能下降。但是，對于側重收斂性的問題，尤其是高維難收斂的問題，例如DTLZ3、DTLZ6、WFG3 等問題，SFI-SMOEA 的性能明顯優于NSGAIII。針 對d≥8 時 的DTLZ6 和WFG3 問題，NSGAIII 和A-NSGA-III 算法不能收斂到真實Pareto 前沿附近，而改進后的算法能很好地處理這些問題。這得益于將算法分為3 個階段，首先考慮優化問題各個目標的最優值，加強了算法的收斂性。

對SFI-SMOEA 和ISDE+進行對比分析后發現，SFI-SMOEA 和ISDE+算法的收斂性都比較好，針對DTLZ6 和WFG3 等難收斂的問題都能較好地收斂到真實Pareto 前沿附近。但是二者都存在分布性較差的問題，尤其針對WFG1、WFG4 這類問題。這是由于在算法搜索初期，兩者都注重收斂性，導致部分基因缺失，表現為較差的分布性。SFI-SMOEA 在第三階段加入了對優秀個體離散程度的評價，增大離散程度大的個體的交配概率，一定程度上加強了算法的分布性。

對WFG3 進行詳細測試，進一步說明算法的性質。分別采用4 種對比算法(NSGA-Ⅲ、A-NSGA-Ⅲ、MOEA/D-M2M 和ISDE+)和SFI-SMOEA 在不同迭代次數下獨立運行20 次，所測得的WFG3 的IGD平均值如圖5 所示。在三目標情況下，本文算法和ISDE+表現最好，各類算法性能均有上限，在300 代左右達到最優。針對更高維目標，所有算法都在一定迭代次數后性能變差，尤其是MOEA/D-M2M。經過對WFG3 分析后發現，WFG3 的真實PF 通常為一條直線，隨著算法進行迭代，會在遠離真實PF 的地方生成許多非支配解。隨著迭代次數的增加，不在真實PF 附近的非支配解個數增加，進而導致算法性能變差。在一定迭代次數(300 代左右)內，本文算法性能較優。隨著迭代次數的增加，算法性能越來越接近NSGA-Ⅲ，這是因為算法的選擇機制和NSGA-Ⅲ中采用的小生境技術一致。對于高維目標，ANSGA-Ⅲ算法表現優良，進一步說明參考點的自適應調節具有研究價值。

圖5 不同迭代次數下5 種算法的IGD 平均值Fig.5 IGD mean values of five algorithms in different iterations

3 結 論

本文提出了一種基于統計反饋信息指導親本選擇的分布多目標進化算法（SFI-SMOEA）。在算法搜索初期，為了提升算法收斂性，致力于獲得各個目標函數值的最優值。在算法搜索后期，通過對各個區域的解的分布情況進行統計分析，再根據反饋信息指導種群交配和選擇，從而增強種群的分布性。將SFI-SMOEA 與多個多目標進化算法進行對比發現，SFI-SMOEA 能獲得收斂性和分布性俱佳的Pareto 最優解集。尤其針對10 維目標的WFG3 之類的高維難收斂問題，SFI-SMOEA 展現了它的優先性和競爭力。

SFI-SMOEA 側重于后代解的生成，新種群的選擇策略參考原始的NSGA-Ⅲ中所提的小生境保存技術。在新種群的選擇過程中，可能導致高質量的后代解被錯誤地刪除。因此，新種群的選擇策略非常值得深入研究。本文在選擇新種群時，結合了非支配排序和參考點，但是由于參考向量或者參考點的生成都是在超平面上完成，只能保證這些點在超平面上均勻分布。映射到Pareto 前沿后，并不能保證每一個參考點都能找到至少一個解與之關聯，也就是說參考點的分布與Pareto 前沿的分布無關，因此，可以進一步研究在有效的目標函數值空間生成均勻的參考向量或者參考點自適應的方法。