基于統(tǒng)計(jì)信息反饋的分步多目標(biāo)優(yōu)化

王學(xué)武， 謝祖洪， 周 昕， 顧幸生

（華東理工大學(xué)能源化工過(guò)程智能制造教育部重點(diǎn)實(shí)驗(yàn)室，上海 200237）

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

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

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

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

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

1 SFI-SMOEA 算法框架

傳統(tǒng)的多目標(biāo)進(jìn)化算法[4,8,10]通常協(xié)同考慮全局的收斂性或者多樣性，可能導(dǎo)致算法對(duì)于單目標(biāo)極值探索的不足，而且在搜索初期會(huì)生成大量支配解，造成計(jì)算資源的浪費(fèi)。SFI-SMOEA 將整個(gè)優(yōu)化算法分為3 個(gè)階段：

（1）單目標(biāo)探索階段。在此階段，放棄對(duì)整個(gè)Pareto 前沿的探索，分別對(duì)優(yōu)化問(wèn)題的多個(gè)目標(biāo)進(jìn)行相對(duì)獨(dú)立的探索，使其快速找到每個(gè)單目標(biāo)的最優(yōu)解。

（2）單目標(biāo)到多目標(biāo)的過(guò)渡階段。在單目標(biāo)探索階段結(jié)束后，解圍繞在各個(gè)目標(biāo)的最優(yōu)值附近。此階段的主要任務(wù)是加強(qiáng)對(duì)整個(gè)Pareto 前沿的探索，尤其針對(duì)部分未覆蓋區(qū)域，這是為了促進(jìn)算法的分布性。

（3）群體劃分局部?jī)?yōu)化階段。經(jīng)過(guò)第一、二階段的探索，形成基本的Pareto 前沿，但是局部收斂性不足。因此，第三階段的主要任務(wù)是根據(jù)目標(biāo)函數(shù)值進(jìn)行群體劃分，利用反饋信息加強(qiáng)局部Pareto 前沿的開(kāi)發(fā)。在迭代過(guò)程中，根據(jù)目標(biāo)函數(shù)值將所有解劃分為不同區(qū)域；然后反饋各個(gè)區(qū)域解的分布情況，在稀疏區(qū)域生成更多解，進(jìn)一步增強(qiáng)算法搜索能力。

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

算法1 SFI-SMOEA 算法流程

1.1 單目標(biāo)探索階段

在單目標(biāo)探索階段，分別對(duì)每個(gè)目標(biāo)最優(yōu)值進(jìn)行探索，期望盡快找到每個(gè)目標(biāo)的最優(yōu)值。在此階段，將多目標(biāo)優(yōu)化問(wèn)題轉(zhuǎn)化成m個(gè)單目標(biāo)優(yōu)化問(wèn)題，并利用改進(jìn)的單目標(biāo)遺傳算法進(jìn)行求解。

1.1.1 挑選精英個(gè)體 在傳統(tǒng)遺傳算法[18]中，親本的選擇是根據(jù)適應(yīng)度進(jìn)行的，適應(yīng)度高的解有更大概率被選為親本。當(dāng)算法進(jìn)行了一段時(shí)間后，解空間內(nèi)解的相似度很高，進(jìn)行交配的領(lǐng)域變小，可能導(dǎo)致算法陷入局部最優(yōu)。在處理此類問(wèn)題時(shí)，有學(xué)者提出采用事件觸發(fā)機(jī)制[19]增強(qiáng)算法跳出局部最優(yōu)的能力。對(duì)于遺傳算法求解單目標(biāo)優(yōu)化問(wèn)題而言，一方面我們希望優(yōu)秀個(gè)體可以獲得更大的交配機(jī)會(huì)；另一方面，我們也希望保持種群的多樣性，避免算法陷入局部最優(yōu)。基于以上分析，將解按照單目標(biāo)適應(yīng)度進(jìn)行排序，挑選出部分優(yōu)秀個(gè)體建立外部檔案（Xg），其中每個(gè)目標(biāo)優(yōu)秀個(gè)體的數(shù)目根據(jù)種群大小和待優(yōu)化問(wèn)題的目標(biāo)維度確定。通過(guò)對(duì)部分個(gè)體進(jìn)行評(píng)估，確定優(yōu)秀個(gè)體的交配次數(shù)，保證優(yōu)秀個(gè)體的基因得以保留；然后刪除種群中多余的重復(fù)解，隨機(jī)生成新的解，直到滿足種群數(shù)目要求。

1.1.2 對(duì)優(yōu)秀個(gè)體進(jìn)行相似性和離散程度的評(píng)估由于對(duì)整個(gè)種群中的每一個(gè)個(gè)體進(jìn)行價(jià)值評(píng)估計(jì)算較為復(fù)雜，因此只對(duì)通過(guò)適應(yīng)度值挑選出的優(yōu)秀個(gè)體進(jìn)行價(jià)值評(píng)估。對(duì)優(yōu)秀個(gè)體進(jìn)行相似性和離散程度的統(tǒng)計(jì)，采用基于相關(guān)性的密度估計(jì)指標(biāo)ICDE，類似于統(tǒng)計(jì)學(xué)中相關(guān)系數(shù)的計(jì)算[20]，如式(1)所示。

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

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

根據(jù)評(píng)估結(jié)果指導(dǎo)親本選擇過(guò)程的偽代碼如算法2 所示，即基于優(yōu)秀個(gè)體的親本選擇算子(Parent Selection Operator Based on Excellent Individuals，EIPS)。

算法2 基于優(yōu)秀個(gè)體的親本選擇算子(EIPS)

第一階段單目標(biāo)探索階段包括挑選優(yōu)秀個(gè)體、對(duì)優(yōu)秀個(gè)體進(jìn)行相似性和離散程度的評(píng)估、根據(jù)評(píng)估信息指導(dǎo)種群親本選擇過(guò)程。圖1 所示為部分三維測(cè)試案例第一階段解的分布情況，可以看到其中的大部分解都圍繞在各個(gè)目標(biāo)最優(yōu)值附近。

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

1.2 單目標(biāo)到多目標(biāo)的過(guò)渡階段

過(guò)渡階段的首要任務(wù)是使種群初步收斂到Pareto 前沿上，其中包括對(duì)個(gè)體進(jìn)行群體劃分，根據(jù)劃分結(jié)果指導(dǎo)親本選擇過(guò)程。但是在單目標(biāo)探索結(jié)束后，種群中個(gè)體大多集中在各個(gè)目標(biāo)的最優(yōu)值周圍，因此需要對(duì)種群中的個(gè)體進(jìn)行聚類分析，再根據(jù)分析結(jié)果合理地分配交配資源，使其快速收斂到Pareto 前沿。

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

圖2 所示為三維優(yōu)化問(wèn)題的種群劃分示意圖。每一維目標(biāo)被均勻地分為2 份；共有6 個(gè)權(quán)重向量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) 。將 目 標(biāo) 函數(shù)值空間分為4 個(gè)區(qū)域：w1、w2、w3圍成的空間為1 號(hào)區(qū)域；w2、w3、w5圍成的空間為2 號(hào)區(qū)域；w2、w4、w5圍成的空間為3 號(hào)區(qū)域；w3、w5、w6圍成的空間為4 號(hào)區(qū)域。

圖2 三維優(yōu)化問(wèn)題的種群劃分Fig.2 Population division of for 3-objective optimization problems

1.2.2 根據(jù)種群劃分結(jié)果指導(dǎo)親本選擇 種群類別劃分的區(qū)域是參考權(quán)重向量生成方式進(jìn)行的，理想情況下，每個(gè)區(qū)域內(nèi)的個(gè)體數(shù)由被優(yōu)化問(wèn)題的Pareto分布決定。由于在單目標(biāo)探索階段結(jié)束后，解大都分布在各個(gè)目標(biāo)最優(yōu)值周圍，可能導(dǎo)致部分區(qū)域解的個(gè)數(shù)很少，甚至有些區(qū)域沒(méi)有解，此時(shí)應(yīng)該加大此區(qū)域中解的生成，從而使得解盡快收斂到Pareto 前沿上。對(duì)不同類別的個(gè)體數(shù)進(jìn)行統(tǒng)計(jì)，再根據(jù)統(tǒng)計(jì)結(jié)果確定親本選擇的概率，從而實(shí)現(xiàn)對(duì)各個(gè)區(qū)域個(gè)體數(shù)的控制。其中，在同一區(qū)域內(nèi)進(jìn)行親本選擇的概率Ps由式（5）計(jì)算：

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

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

1.3 群體劃分局部?jī)?yōu)化階段

經(jīng)過(guò)第一、二階段的優(yōu)化后，種群基本收斂到Pareto 前沿上，只有少數(shù)區(qū)域收斂性不足和解分布不均勻。本階段的首要任務(wù)是對(duì)種群個(gè)體進(jìn)行群體劃分，分別對(duì)各個(gè)群體的解進(jìn)行聚類分析，選擇其中表現(xiàn)優(yōu)異的個(gè)體作為領(lǐng)導(dǎo)者；利用領(lǐng)導(dǎo)者對(duì)群體進(jìn)行收斂性和分布性評(píng)價(jià)，然后根據(jù)評(píng)價(jià)結(jié)果指導(dǎo)親本選擇過(guò)程，從而實(shí)現(xiàn)收斂性的優(yōu)化及對(duì)分布性的控制。

1.3.1 聚類分析 將種群劃分為若干區(qū)域后，同一區(qū)域內(nèi)解的性質(zhì)相似，便于統(tǒng)計(jì)分析。分別對(duì)每個(gè)區(qū)域內(nèi)的解進(jìn)行線性回歸分析[22]，模擬出近似的Pareto 前沿，計(jì)算解到模擬Pareto 前沿的距離，即。如圖3 所示，陰影部分表示通過(guò)線性回歸獲得的近似Pareto 前沿。個(gè)體的優(yōu)劣是通過(guò)它的收斂性和分布性決定的，對(duì)于最小化問(wèn)題而言，優(yōu)秀個(gè)體在模擬Pareto 前沿的下方，離Pareto 前沿越遠(yuǎn)，說(shuō)明此個(gè)體的收斂性越強(qiáng)。反之，如果個(gè)體在模擬Pareto 前沿的上方，說(shuō)明此個(gè)體的收斂性較差。按照1.1.2 節(jié)所述方法，對(duì)同區(qū)域內(nèi)的個(gè)體進(jìn)行相似性和離散程

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

油田配電網(wǎng)變壓器節(jié)能改造的研究…………………………………………………………………………………陳亞莉（3.30）

1.3.2 根據(jù)聚類分析結(jié)果指導(dǎo)親本選擇 經(jīng)過(guò)實(shí)驗(yàn)發(fā)現(xiàn)，性質(zhì)差異較大的兩個(gè)解生成的后代很大概率是支配解，造成計(jì)算資源浪費(fèi)，不能達(dá)到使Pareto 收斂的要求。為了避免此類情況，在群體劃分局部?jī)?yōu)化階段，個(gè)體只與同區(qū)域或者相鄰區(qū)域個(gè)體交配。以如圖1 所示的三維問(wèn)題為例，區(qū)域1 和區(qū)域2 相鄰，區(qū)域3 和區(qū)域2 相鄰，區(qū)域4 和區(qū)域2 相鄰，區(qū)域2 和區(qū)域1、3、4 都相鄰。區(qū)域1 中的個(gè)體只與區(qū)域1、2 中的個(gè)體進(jìn)行交配。通過(guò)聚類分析選出各個(gè)區(qū)域的優(yōu)秀個(gè)體，優(yōu)先給此類個(gè)體分配配偶，然后在同一區(qū)域或者相鄰區(qū)域隨機(jī)分配配偶，直到交配池?cái)?shù)量要求。配偶選擇過(guò)程如算法4 所示，即基于領(lǐng)導(dǎo)者的親本選擇(Parent selection operator based on leaders，LPS)。

算法4 基于領(lǐng)導(dǎo)者的親本選擇(LPS)

2 仿真實(shí)驗(yàn)與分析

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

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

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

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

表1 DTLZ 測(cè)試案例的HV 平均值（標(biāo)準(zhǔn)差）Table1 HV mean values (standard deviation) of DTLZ test cases

續(xù)表1

表2 WFG 測(cè)試案例的HV 平均值（標(biāo)準(zhǔn)差）Table2 HV mean values (standard deviation) of WFG test cases

續(xù)表2

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

從各個(gè)測(cè)試案例的收斂情況來(lái)看，對(duì)于DTLZ4、WFG1、WFG2 等側(cè)重分布性的多目標(biāo)問(wèn)題，SFISMOEA 性能比NSGA- III 算法差。

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

對(duì)SFI-SMOEA 和ISDE+進(jìn)行對(duì)比分析后發(fā)現(xiàn)，SFI-SMOEA 和ISDE+算法的收斂性都比較好，針對(duì)DTLZ6 和WFG3 等難收斂的問(wèn)題都能較好地收斂到真實(shí)Pareto 前沿附近。但是二者都存在分布性較差的問(wèn)題，尤其針對(duì)WFG1、WFG4 這類問(wèn)題。這是由于在算法搜索初期，兩者都注重收斂性，導(dǎo)致部分基因缺失，表現(xiàn)為較差的分布性。SFI-SMOEA 在第三階段加入了對(duì)優(yōu)秀個(gè)體離散程度的評(píng)價(jià)，增大離散程度大的個(gè)體的交配概率，一定程度上加強(qiáng)了算法的分布性。

對(duì)WFG3 進(jìn)行詳細(xì)測(cè)試，進(jìn)一步說(shuō)明算法的性質(zhì)。分別采用4 種對(duì)比算法(NSGA-Ⅲ、A-NSGA-Ⅲ、MOEA/D-M2M 和ISDE+)和SFI-SMOEA 在不同迭代次數(shù)下獨(dú)立運(yùn)行20 次，所測(cè)得的WFG3 的IGD平均值如圖5 所示。在三目標(biāo)情況下，本文算法和ISDE+表現(xiàn)最好，各類算法性能均有上限，在300 代左右達(dá)到最優(yōu)。針對(duì)更高維目標(biāo)，所有算法都在一定迭代次數(shù)后性能變差，尤其是MOEA/D-M2M。經(jīng)過(guò)對(duì)WFG3 分析后發(fā)現(xiàn)，WFG3 的真實(shí)PF 通常為一條直線，隨著算法進(jìn)行迭代，會(huì)在遠(yuǎn)離真實(shí)PF 的地方生成許多非支配解。隨著迭代次數(shù)的增加，不在真實(shí)PF 附近的非支配解個(gè)數(shù)增加，進(jìn)而導(dǎo)致算法性能變差。在一定迭代次數(shù)(300 代左右)內(nèi)，本文算法性能較優(yōu)。隨著迭代次數(shù)的增加，算法性能越來(lái)越接近NSGA-Ⅲ，這是因?yàn)樗惴ǖ倪x擇機(jī)制和NSGA-Ⅲ中采用的小生境技術(shù)一致。對(duì)于高維目標(biāo)，ANSGA-Ⅲ算法表現(xiàn)優(yōu)良，進(jìn)一步說(shuō)明參考點(diǎn)的自適應(yīng)調(diào)節(jié)具有研究?jī)r(jià)值。

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

3 結(jié) 論

本文提出了一種基于統(tǒng)計(jì)反饋信息指導(dǎo)親本選擇的分布多目標(biāo)進(jìn)化算法（SFI-SMOEA）。在算法搜索初期，為了提升算法收斂性，致力于獲得各個(gè)目標(biāo)函數(shù)值的最優(yōu)值。在算法搜索后期，通過(guò)對(duì)各個(gè)區(qū)域的解的分布情況進(jìn)行統(tǒng)計(jì)分析，再根據(jù)反饋信息指導(dǎo)種群交配和選擇，從而增強(qiáng)種群的分布性。將SFI-SMOEA 與多個(gè)多目標(biāo)進(jìn)化算法進(jìn)行對(duì)比發(fā)現(xiàn)，SFI-SMOEA 能獲得收斂性和分布性俱佳的Pareto 最優(yōu)解集。尤其針對(duì)10 維目標(biāo)的WFG3 之類的高維難收斂問(wèn)題，SFI-SMOEA 展現(xiàn)了它的優(yōu)先性和競(jìng)爭(zhēng)力。

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