基于改善解集分布性的多目標(biāo)優(yōu)化

王學(xué)武 方俊宇 高進(jìn) 顧幸生

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

在實(shí)際生產(chǎn)過(guò)程中，因客觀需求，往往存在2個(gè)或者2個(gè)以上的優(yōu)化目標(biāo)，這類優(yōu)化問(wèn)題統(tǒng)稱為多目標(biāo)優(yōu)化問(wèn)題（Multi-Objective Problem，MOP）。與單目標(biāo)優(yōu)化不同，多目標(biāo)優(yōu)化的最優(yōu)解并不唯一：這些解無(wú)法在所有目標(biāo)函數(shù)值均保持最優(yōu)，且不存在所有目標(biāo)函數(shù)均優(yōu)于自身的解——非支配解，這些解構(gòu)成的解集稱為帕累托解集（Pareto Set，PS），而解集對(duì)應(yīng)的決策空間目標(biāo)函數(shù)的點(diǎn)則構(gòu)成帕累托前沿（Pareto Front，PF）。在過(guò)去的數(shù)十年中，隨著計(jì)算智能的發(fā)展，各種類型的多目標(biāo)優(yōu)化算法（Multi-Objective Algorithm，MOA）被開(kāi)發(fā)出來(lái)解決不同類型的MOP，均取得了較好的效果，在解集充分逼近真實(shí)PF 的同時(shí)保證了解的多樣性，給決策者提供了多樣化的選擇。

多目標(biāo)優(yōu)化算法中，常見(jiàn)的是基于進(jìn)化計(jì)算的多目標(biāo)進(jìn)化優(yōu)化算法（Multi-Objective Evolutionary Algorithm，MOEA）。按進(jìn)化機(jī)制的不同，MOEA可分為以下3類：①基于分解的MOEA 算法，其代表有MOEA/D［1］、MOEA/D-RWV［2］、R-MOEA/D［3］等；②基于非支配排序的MOEA 算法，其代表有NSGAⅢ［4］、ASDNSGA-Ⅱ［5］等；③基于指標(biāo)的MOEA 算法，其代表有IBEA、AR-MOEA［6］等。近年來(lái)，隨著計(jì)算機(jī)算力的提升，除了各種新的環(huán)境選擇策略被提出，多名學(xué)者還將原有不同類型的策略相結(jié)合，甚至將機(jī)器學(xué)習(xí)融入基礎(chǔ)策略提出新的算法，在不同類型的MOP 上提升解集的收斂性和分布性：Tian 等［7］利用兩個(gè)種群分別解決帶約束多目標(biāo)優(yōu)化問(wèn)題（Constrained Multi-Objective Problem，CMOP）和無(wú)約束多目標(biāo)優(yōu)化問(wèn)題，并設(shè)置協(xié)同進(jìn)化框架，有效提升了算法在具有狹小可行域的CMOP上解集的分布性；Panichella［8］設(shè)計(jì)了一種自適應(yīng)的、兼顧收斂性和分布性的指標(biāo)，并將其與非支配排序策略相結(jié)合，提出了AGE-MOEA 算法，大大提升了在不規(guī)則PF 的MOP 獲得解集的分布性；Sonoda 等［9］則采用支持向量機(jī)（Support Vector Machine，SVM）生成代理人模型去適應(yīng)MOEA/D通過(guò)分解策略產(chǎn)生的子問(wèn)題，從而在高維多目標(biāo)優(yōu)化問(wèn)題（Many-Objective Optimization Problem，MaOEA）上獲得了分布性較好的解集。

在基于非支配排序策略的多目標(biāo)優(yōu)化算法中，NSGAⅡ的基本框架（非支配排序+環(huán)境選擇策略）成為該類算法的代表。非支配排序用于尋找當(dāng)前最優(yōu)前沿解集，環(huán)境選擇策略則用于提升分布性。SPEA2則通過(guò)強(qiáng)壯支配指數(shù)［10］搜尋非支配個(gè)體，并將其與基于k-近鄰聚集密度的分布性指數(shù)加權(quán)求得個(gè)體適應(yīng)度值，再通過(guò)設(shè)置適應(yīng)度閾值進(jìn)行篩選的方法同時(shí)保證收斂性和分布性。SPEA2基于個(gè)體適應(yīng)度選拔父代，這使得通過(guò)遺傳算法生成的新個(gè)體有更大概率同時(shí)具有良好的收斂性和分布性，因此其在大多數(shù)MOP上的收斂速度要比NSGAⅡ快。然而，SPEA2 存在如下3 個(gè)缺陷：①在保證收斂速度和全局搜索能力的同時(shí)，局部搜索能力顯得有些不足；②受其檔案截?cái)嗖呗缘挠绊?，種群中非支配個(gè)體快速增多，不同個(gè)體間的適應(yīng)度差異也迅速變小，這使得后期選擇的父代無(wú)法保證基因多樣性，通過(guò)遺傳算法獲得更優(yōu)子代的概率大幅降低，種群進(jìn)化容易過(guò)早陷入停滯；③對(duì)于存在不規(guī)則PF 的MOP（如IMOP7、ZDT3、VNT1等），SPEA2算法獲得的解集分布性有待進(jìn)一步提高。針對(duì)缺陷①，翁理國(guó)等［11］提出了一種通過(guò)額外設(shè)置一個(gè)用于存放局部搜索得到的非支配解的歸檔集的方法，增強(qiáng)了原算法的局部搜索能力。針對(duì)缺陷②和③，文中提出一種改進(jìn)的算法CM-SPEA2（Clustering-Based Modified Strength Pareto Evolutionary Algorithm 2），將層次聚類方法融入到SPEA2的環(huán)境選擇策略中，并引入改進(jìn)雜亂度指數(shù)參與環(huán)境篩選策略。

1 CM-SPEA2的算法原理

1.1 算法總框架

CM-SPEA2 整體沿用SPEA2 的主體框架（即通過(guò)遺傳算法產(chǎn)生子代、通過(guò)強(qiáng)壯支配指數(shù)和表征分布性加權(quán)得到的適應(yīng)度值進(jìn)行環(huán)境篩選），只保留適應(yīng)度“最優(yōu)”的一半子代個(gè)體與原種群合并。

算法的主體框架偽代碼如下：

1.2 CM-SPEA2的適應(yīng)度函數(shù)

與多數(shù)直接將聚類應(yīng)用于環(huán)境選擇的機(jī)制不同，CM-SPEA2 將聚類用于計(jì)算來(lái)改進(jìn)適應(yīng)度函數(shù)，再與基于適應(yīng)度大小的環(huán)境選擇策略結(jié)合起來(lái)，間接依照雜亂度進(jìn)行篩選并得到分布性較好的解集。

SPEA2算法的適應(yīng)度函數(shù)如式（1）所示：

式中，R（i）為支配個(gè)體i的所有個(gè)體強(qiáng)度之和，

其中，S（j）為個(gè)體j的支配強(qiáng)度，表示受該個(gè)體支配的解的數(shù)量，

Pt為第t代的種群，At為第t代產(chǎn)生的歸檔集。

原始適應(yīng)度賦值過(guò)程需引入密度信息來(lái)區(qū)分具有相同原始適應(yīng)度值的個(gè)體。SPEA2采用k-近鄰方式來(lái)計(jì)算個(gè)體密度值D(i)：

式中，為個(gè)體i和第k個(gè)相鄰個(gè)體的距離，其中

N為種群個(gè)體數(shù)，為歸檔集個(gè)體數(shù)。

然而，作為適應(yīng)度函數(shù)中表征種群分布性的算子，D（i）無(wú)法區(qū)分聚集密度相同、分布均勻程度存在差異的個(gè)體；與之相比，雜亂度雖不能表征個(gè)體間的聚集密度，但可以衡量聚集密度及相鄰個(gè)體間距的均勻程度。因此，基于種群的雜亂度分析，CM-SPEA2引入一種新的表征分布性的算子O（i）。

設(shè)算法通過(guò)聚類得到聚集簇C1，內(nèi)部包含N個(gè)個(gè)體；又設(shè)第j個(gè)個(gè)體的雜亂度最低，即Chaos(j)=min{m(i)}，i=1，2，…，N。則聚集簇C1中第i個(gè)個(gè)體與第j個(gè)個(gè)體的Manhattan距離D（i）為

式中，C1_O(i)為第i個(gè)個(gè)體的目標(biāo)函數(shù)向量值。

對(duì)D（i）進(jìn)行升序排序，得Rank（i）。對(duì)Rank（i）進(jìn)行量綱處理，最終得到個(gè)體i的分布性指數(shù)O(i)：

CM-SPEA2 算法的個(gè)體i的適應(yīng)度如式（8）所示：

1.3 聚類方法

對(duì)于不規(guī)則PF的MOP，僅憑單一指標(biāo)（如擁擠度距離、聚集密度等）通常很難反映個(gè)體在種群的真實(shí)分布情況，需要借助參考點(diǎn)，而參考點(diǎn)的選擇很大程度上會(huì)影響環(huán)境選擇策略的優(yōu)劣。聚類是一種有效尋找參考點(diǎn)的方法，能夠適應(yīng)種群最佳前沿的聚集特性，從而結(jié)合相關(guān)指標(biāo)改善分布性。

聚類方法有很多。王學(xué)武等［12］采用DBSCAN密度聚類將種群分為不同簇，并挑選領(lǐng)導(dǎo)粒子作為參考，基于擁擠度距離完成環(huán)境選擇。該方法魯棒性強(qiáng)，受離群點(diǎn)影響較??；然而，相關(guān)參數(shù)的設(shè)定（鄰域半徑、最少鄰域點(diǎn)數(shù)量等）對(duì)聚類效果的影響非常大，且不適合形狀不規(guī)則PF 的多目標(biāo)優(yōu)化問(wèn)題。Hua等［13］在CAMOEA算法中對(duì)種群個(gè)體進(jìn)行非支配排序之后，將最劣解個(gè)體數(shù)作為簇?cái)?shù)量上限進(jìn)行層次聚類（如圖1 所示），再計(jì)算各個(gè)簇的形心，將其作為參考點(diǎn)。該方法充分利用了最劣解集個(gè)體多樣性最好的特點(diǎn)，能夠自適應(yīng)地根據(jù)PF 的形狀設(shè)置參考點(diǎn)的數(shù)量和位置。

圖1 層次聚類效果圖Fig.1 Effect diagram of hierarchical clustering

受文獻(xiàn)［12-13］啟發(fā)，文中提出一種新的聚類方法，其特點(diǎn)如下：①聚類的對(duì)象是種群中的非支配個(gè)體（即強(qiáng)壯支配指數(shù)為零的個(gè)體）；②簇?cái)?shù)量最大不超過(guò)最劣解的個(gè)數(shù)；③聚類方法采用不等權(quán)重算術(shù)平均聚類（Weighted Pair Group Method with Arithmetic Mean，WPGMA）；④個(gè)體間的相似度采用帶權(quán)算術(shù)平均Manhattan 距離來(lái)代替；⑤聚類完成后，計(jì)算個(gè)體在所屬簇的雜亂度值，選擇雜亂度最小的個(gè)體作為參考點(diǎn)。算法效果如圖1 所示（圖中坐標(biāo)軸f1和f2分別代表目標(biāo)值1和目標(biāo)值2）。

1.4 改進(jìn)種群雜亂度分析

對(duì)于非均勻PF 的MOP，傳統(tǒng)的種群維護(hù)方法容易導(dǎo)致解集分布在PF 的某個(gè)集中區(qū)域，從而破壞解集分布性。為更好地表征個(gè)體在解空間分布的差異性，引入個(gè)體雜亂度分析。

對(duì)于種群中個(gè)體的雜亂度m(i)，李密青等［14］給出了如下定義：

式中，d（i）為個(gè)體i在種群生成的一棵歐式最小生成樹(shù)（Euclidean Minimum Spanning Tree，EMST）中的度數(shù)（即與該個(gè)體連接的邊數(shù)），max（l（i））以及min（l（i））分別為EMST 中連接個(gè)體i的最長(zhǎng)邊和最短邊。通過(guò)該定義，可以輕易找到種群內(nèi)部雜亂度最大的個(gè)體。然而，該計(jì)算方法存在以下缺陷：①每次計(jì)算都要預(yù)先生成EMST，計(jì)算消耗大；②只能準(zhǔn)確衡量雜亂度最大的個(gè)體，不能準(zhǔn)確衡量雜亂度最小的個(gè)體，尤其是離群邊緣個(gè)體（如圖2所示），此時(shí)d(i)=1，而max (l(i))=min (l(i))，從而得到該點(diǎn)的雜亂度m(i)=0，雜亂度達(dá)到極小值，這明顯與實(shí)際不符。

圖2 含離群點(diǎn)的EMST示意圖Fig.2 Diagrammatic sketch of EMST containing an outlier

此外，隨著迭代的進(jìn)行，個(gè)體間距越來(lái)越小，使用這種雜亂度計(jì)算方法會(huì)導(dǎo)致后期解集內(nèi)不同個(gè)體之間的差異越來(lái)越小，從而使得環(huán)境選擇策略難以進(jìn)一步提升分布性和收斂性。故對(duì)式（9）進(jìn)行如下改進(jìn)：對(duì)于一個(gè)特定種群P，用個(gè)體i與最近個(gè)體的距離和個(gè)體間平均最短間距的差異來(lái)表征其雜亂度，即

式中，δ（i）為第i個(gè)個(gè)體與種群P內(nèi)其他個(gè)體的最小Manhattan距離（同樣可以通過(guò)EMST計(jì)算）。對(duì)于存在不均勻PF 的MOP，式（10）往往不能很好地表征個(gè)體的雜亂度，需要通過(guò)聚類方法確定若干個(gè)簇，再計(jì)算個(gè)體在簇內(nèi)的雜亂度。設(shè)個(gè)體i通過(guò)之前的聚類方法被分在了簇Cj中（Cj中總共有Nj個(gè)體），則該個(gè)體的雜亂度為

前人的研究已經(jīng)證實(shí)，直接淘汰雜亂度大的個(gè)體并不一定能夠改善種群分布的均勻特性，尤其當(dāng)雜亂度大的個(gè)體離種群邊緣個(gè)體較遠(yuǎn)時(shí)，單獨(dú)刪除雜亂度最大的個(gè)體會(huì)有很大幾率增加種群分布的不均勻程度。圖3（a）所示為原種群分布圖，為方便討論，除E、F間距設(shè)置偏小外，圖中其余相鄰點(diǎn)（個(gè)體）的間距均相同。按照式（9），點(diǎn)F的雜亂度m(F)=LFGLEF-12 ＞0.5，點(diǎn)G的最長(zhǎng)邊、最短邊與點(diǎn)F的相同，故有m(F)=m(G)；而點(diǎn)B、C、D的雜亂度均為0.5，點(diǎn)A、H的雜亂度均為0，故點(diǎn)F、G為雜亂度最大的個(gè)體。為此，鄭金華等［15］提出刪除距雜亂度最大個(gè)體最近的個(gè)體來(lái)改善分布性。圖3（b）-3（e）分別為刪除點(diǎn)F、G及其各自的近鄰個(gè)體E、H后的種群分布。

圖3 不同篩選策略的對(duì)比Fig.3 Comparison of different selecting strategies

可以明顯看出，刪除個(gè)體E或H后的種群分布性優(yōu)于刪除個(gè)體F或G后。然而，該方法存在如下缺陷：①一次只能刪除1個(gè)個(gè)體，否則雜亂度會(huì)增加；②每次刪除操作完成之后需要重新評(píng)估雜亂度再重復(fù)刪除操作，大大增加了計(jì)算消耗。為此，筆者提出一種新的策略：由刪除雜亂度最大個(gè)體的近鄰個(gè)體轉(zhuǎn)化為保留雜亂度最小個(gè)體及其近鄰個(gè)體。該策略在很大程度上減少了計(jì)算消耗，并且由于SPEA2 本身采用的也是設(shè)置閾值保留個(gè)體的策略，沿用原有環(huán)境選擇策略框架便可以實(shí)現(xiàn)改進(jìn)策略（當(dāng)出現(xiàn)2個(gè)及2個(gè)以上的雜亂度最低的個(gè)體時(shí)，則選擇與雜亂度最大個(gè)體間隔最遠(yuǎn)的個(gè)體作為參考點(diǎn)，再保留近鄰個(gè)體）。同樣以圖3 為例，由于點(diǎn)A、B、C、D、E的間距設(shè)置為相等，故此處將點(diǎn)A作為參考點(diǎn)，在保留近鄰7個(gè)個(gè)體后，得到的種群與刪除個(gè)體H后的種群分布相同。

新策略以犧牲邊界個(gè)體為代價(jià)，在一定程度上削弱了種群多樣性；然而，在迭代早期，非支配個(gè)體往往不足以填滿整個(gè)歸檔集，此時(shí)會(huì)接納一定數(shù)量的其他個(gè)體，這將有一定幾率選擇種群或簇的邊緣個(gè)體，解的多樣性在一定程度上得到補(bǔ)償。

CM-SPEA2 的環(huán)境選擇策略步驟如下：①初始化種群Pt（此處Pt由原種群和通過(guò)遺傳算法獲得的較優(yōu)后代合并而來(lái)），設(shè)置歸檔集At（大小為N），初始為空集；②計(jì)算Pt個(gè)體的適應(yīng)度；③篩選Pt中適應(yīng)度小于1 的個(gè)體，將其納入歸檔集；④判斷At是否滿集，如已滿則結(jié)束，否則轉(zhuǎn)至⑤；⑤將其他個(gè)體按照聚集密度（此處用Manhattan距離代替SPEA2的Euclidean 距離）進(jìn)行升序排序；⑥依次序?qū)n外個(gè)體納入At直至滿集。

1.5 時(shí)間復(fù)雜度分析

設(shè)MOP的目標(biāo)數(shù)為M，種群個(gè)數(shù)為N。單次迭代過(guò)程中，適應(yīng)度函數(shù)的計(jì)算可以劃分為以下幾個(gè)步驟：①計(jì)算個(gè)體的強(qiáng)壯支配指數(shù)（記為T1(N)）；②層次聚類（記為T2(N)）；③計(jì)算個(gè)體雜亂度（記為T3(N)）；④計(jì)算分布性指數(shù)（記為T4(N)）。

綜上所述，單次迭代過(guò)程中，計(jì)算所有個(gè)體的適應(yīng)度函數(shù)的時(shí)間復(fù)雜度T(N)=T1(N) +T2(N) +T3(N) +T4(N)=O(N3)，可以看出，CM-SPEA2 的時(shí)間復(fù)雜度與SPEA2的相同。

2 算法仿真及性能對(duì)比

實(shí)驗(yàn)測(cè)試環(huán)境如下：Intel（R）Core（TM）i5-9300H CPU @2.40 GHz 2.40 GHz，內(nèi)存16.0 GB，基于x64 處理器的64 位操作系統(tǒng)Window 10 中文版，軟件版本為Matlab R2021a，平臺(tái)版本為PlatEMO［16］3.4。

為了驗(yàn)證改進(jìn)后算法的性能（尤其是對(duì)不規(guī)則PF 的MOP 性能）提升，選擇IMOP、ZDT 和VNT 類問(wèn)題作為測(cè)試MOP。IMOP 類問(wèn)題的a1參數(shù)設(shè)置為0.4，K參數(shù)設(shè)置為5。參與性能對(duì)比的算法為：原算法SPEA2、基于非支配排序的算法NSGAⅡ、同樣采用聚類生成參考點(diǎn)的算法CAMOEA 及在環(huán)境選擇過(guò)程中自適應(yīng)生成參考向量并致力于改善種群分布性的算法RVEAa［17］。用這些算法求解3類問(wèn)題（IMOP、ZDT 和VNT）并比較其性能?？紤]到RVEAa 算法因基于參考向量的環(huán)境選擇策略對(duì)種群規(guī)模有特殊要求，初始種群大小統(tǒng)一設(shè)置為105；針對(duì)不同類型MOP的收斂速度，將IMOP類問(wèn)題最大函數(shù)評(píng)價(jià)次數(shù)設(shè)置為42 000，其余MOP 設(shè)置為31 500。由于ZDT5 屬于二進(jìn)制類MOP 問(wèn)題，需要采用與其他MOP 不同的方式衡量其性能指標(biāo)，因此其不參與仿真及后續(xù)性能的比較。

為避免解集進(jìn)化過(guò)慢或退化為隨機(jī)搜索，所有算法的遺傳算子將交叉概率統(tǒng)一設(shè)置為0.5，變異概率p=1/D（D為目標(biāo)數(shù)）。

2.1 性能指標(biāo)對(duì)比

用于比較的指標(biāo)有：反向世代距離（Inverse Generation Distance，IGD）指標(biāo)DIGD［18］以及分布均勻程度（Spacing）指標(biāo)S［19］。

IGD 指標(biāo)通過(guò)計(jì)算真實(shí)PF 解集中的個(gè)體和算法最終得到的最佳前沿的個(gè)體的平均Euclidean 距離而獲得，其計(jì)算公式如式（12）所示：

式中，x*為當(dāng)前Pareto 解集中的個(gè)體，x為問(wèn)題實(shí)際的Pareto 前沿個(gè)體，|PS|為Pareto 解集中個(gè)體的個(gè)數(shù)。由式（12）知：IGD 指標(biāo)越小，解集的綜合性能越好。

Spacing 指標(biāo)通過(guò)計(jì)算種群個(gè)體之間的鄰近距離的標(biāo)準(zhǔn)差來(lái)表征解集的分布性（均勻程度），其計(jì)算公式如式（13）所示：

考慮到MOEA的隨機(jī)性，算法在各個(gè)MOP上單獨(dú)運(yùn)行30次，然后計(jì)算各個(gè)算法獲得解集指標(biāo)的均值和標(biāo)準(zhǔn)差。為更直觀對(duì)比各個(gè)算法在不同MOP上的指標(biāo)優(yōu)劣，引入rank-sum 檢驗(yàn)（顯著水平0.05），檢驗(yàn)結(jié)果用“+/-/=”表示（三者對(duì)應(yīng)的數(shù)值分別表示參與比較的算法與CM-SPEA2 算法相比“更好”“更差”及“相當(dāng)”的問(wèn)題的數(shù)量）。算法在不同MOP下的IGD和Spacing指標(biāo)分別見(jiàn)表1和表2。

表1 不同算法在不同MOP下的IGD指標(biāo)對(duì)比1）Table 1 Comparison of IGD of different algorithms in multiple MOPs

由表1 和表2 結(jié)果統(tǒng)計(jì)可知：在所有測(cè)試MOP中，IGD、Spacing指標(biāo)占優(yōu)勢(shì)的MOP分別占總測(cè)試MOP的68.75%、87.5%；與SPEA2相比，CM-SPEA2算法的IGD、Spacing 指標(biāo)提升的MOP 數(shù)量則分別占所有MOP 的68.75%、87.5%。對(duì)于部分測(cè)試問(wèn)題，SPEA2與NSGAⅡ、CAMOEA、RVEAa相比不占優(yōu)勢(shì)的指標(biāo)經(jīng)改進(jìn)后也占優(yōu)勢(shì)（如對(duì)ZDT6的Spacing指標(biāo)）。對(duì)于規(guī)則PF 的MOP（如IMOP1、IMOP2、ZDT1、ZDT2等），在保證和SPEA2的IGD 指標(biāo)相當(dāng)?shù)那闆r下，CM-SPEA2 算法的Spacing 指標(biāo)基本上大幅提升。為方便討論，文中將不規(guī)則PF的MOP分為兩類：不連續(xù)PF、連續(xù)但形狀不規(guī)則PF。對(duì)于不連續(xù)PF 的MOP（如IMOP3、IMOP5、ZDT3 等），CM-SPEA2算法的IGD、Spacing指標(biāo)占優(yōu)勢(shì)的比例分別為75%、100%；對(duì)于連續(xù)但形狀不規(guī)則PF的MOP（如IMOP4、IMOP6、VNT1、VNT2 等），CM-SPEA2的IGD、Spacing 指標(biāo)占優(yōu)勢(shì)的比例分別為83.3%、83.3%。與SPEA2 相比，對(duì)于不連續(xù)PF 的MOP，CM-SPEA2 算法的IGD、Spacing 指標(biāo)有提升的比例分別為75%、100%；對(duì)于連續(xù)但形狀不規(guī)則PF 的MOP，CM-SPEA2 算法的IGD、Spacing 指標(biāo)有提升的比例則分別為100%、83.3%。這充分表明：文中算法對(duì)解集分布均勻程度的改善在一定程度上促進(jìn)了綜合性能的提升，其中，對(duì)Spacing 指標(biāo)的提升最為顯著，最高可達(dá)16.3%，IGD 指標(biāo)的提升也普遍達(dá)到5%以上。

2.2 最優(yōu)前沿分布

為了更加直觀地比較不同算法獲得的最優(yōu)前沿，此處分別選擇CM-SPEA2、SPEA2 和相同采樣聚類方法的CAMOEA 算法來(lái)測(cè)試不連續(xù)PF 的MOP（ZDT3和DTLZ7）以及連續(xù)但形狀不規(guī)則PF 的MOP（IMOP7）。除了IMOP5、IMOP7 的最大函數(shù)評(píng)價(jià)次數(shù)設(shè)置為42 000 外，其余MOP 統(tǒng)一設(shè)置為31 500。最終得到的前沿分布如圖4-6所示，圖中坐標(biāo)軸f1、f2和f3分別代表目標(biāo)值1、2和3。

圖4 CM-SPEA2、SPEA2 和CAMOEA 在ZDT3 問(wèn)題上獲得的最優(yōu)前沿的比較Fig.4 Comparison of the optimal fronts among CM-SPEA2，SPEA2 and CAMOEA in ZDT3

圖5 CM-SPEA2、SPEA2 和CAMOEA 在IMOP7 問(wèn)題上獲得的最優(yōu)前沿的比較Fig.5 Comparison of the optimal fronts among CM-SPEA2，SPEA2 and CAMOEA in IMOP7

圖6 CM-SPEA2、SPEA2 和CAMOEA 在DTLZ7 問(wèn)題上獲得的最優(yōu)前沿的比較Fig.6 Comparison of the optimal fronts among CM-SPEA2，SPEA2 and CAMOEA in DTLZ7

通過(guò)對(duì)比得知：①經(jīng)過(guò)相同次數(shù)的迭代后，CM-SPEA2 的最佳前沿能充分逼近問(wèn)題的實(shí)際PF，絲毫不遜色于SPEA2和CAMOEA；②即便CM-SPEA2在環(huán)境選擇策略中犧牲了種群（簇）的邊緣個(gè)體，最終獲得的解集依然能夠充分覆蓋整個(gè)PF，解集多樣性得到了保證。

2.3 策略可行性驗(yàn)證

為進(jìn)一步探討接納參考點(diǎn)附近個(gè)體的環(huán)境選擇策略的性能優(yōu)劣，分別采用離參考點(diǎn)由近及遠(yuǎn)（簡(jiǎn)稱策略1）和由遠(yuǎn)及近（簡(jiǎn)稱策略2）保留個(gè)體的環(huán)境選擇策略來(lái)解決多個(gè)MOP，得到的IGD 和Spacing指標(biāo)如表3所示。

表3 不同環(huán)境選擇策略的CM-SPEA2在多個(gè)MOP下的IGD和Spacing指標(biāo)對(duì)比Table 3 Comparison of IGD and Spacing in multiple MOPs for CM-SPEA2 using different environment selection strategies

經(jīng)對(duì)比可知：對(duì)不同MOP，采用策略1 時(shí)CM-SPEA2 的IGD 指標(biāo)與采用策略2 時(shí)沒(méi)有顯著優(yōu)劣差別，而Spacing指標(biāo)占優(yōu)勢(shì)的則有9個(gè)。這充分表明，刪除邊遠(yuǎn)個(gè)體策略不僅未明顯削弱種群的綜合性能，還可以保證種群分布足夠均勻，這進(jìn)一步驗(yàn)證了該策略的可行性。

2.4 演化過(guò)程分析

為了體現(xiàn)CM-SPEA2改進(jìn)策略對(duì)算法演化過(guò)程的影響，將前述算法在VNT2 問(wèn)題上進(jìn)行IGD 性能比較，得到的IGD指標(biāo)演化曲線如圖7所示。

圖7 不同MOEA算法在解決VNT2問(wèn)題時(shí)的IGD指標(biāo)演化曲線Fig.7 IGD evolution curves of different MOEAs when solving VNT2

IGD 指標(biāo)演化曲線充分展示了不同算法的性能指標(biāo)提升過(guò)程。由圖7 可以發(fā)現(xiàn)：不改變?cè)璖PEA2算法的環(huán)境選擇策略能夠更好地保證算法的收斂速度，且及時(shí)在迭代后期進(jìn)化較為緩慢的階段；改進(jìn)后的CM-SPEA2 算法的IGD 指標(biāo)波動(dòng)很小，且沒(méi)有出現(xiàn)類似RVEAa算法指標(biāo)明顯變差的情況。

此外，由圖8所示在ZDT3問(wèn)題上的Spacing指標(biāo)演化曲線可以看出：迭代早期CM-SPEA2 比SPEA2的Spacing指標(biāo)下降更快，迭代中后期Spacing指標(biāo)未出現(xiàn)明顯上升趨勢(shì)，這表明解集分布的均勻程度能快速提升并達(dá)到穩(wěn)定。

圖8 不同MOEA算法在解決ZDT3問(wèn)題時(shí)的Spacing指標(biāo)演化曲線Fig.8 Spacing evolution curves of different MOEAs when solving ZDT3

3 結(jié)語(yǔ)

文中提出了改進(jìn)的SPEA2算法——CM-SPEA2。該算法重新定義了雜亂度計(jì)算方法，并將其用于個(gè)體適應(yīng)度計(jì)算，再將改進(jìn)的適應(yīng)度值應(yīng)用于父代選擇和環(huán)境選擇策略。環(huán)境選擇策略通過(guò)改進(jìn)適應(yīng)度函數(shù)被間接調(diào)整：當(dāng)解集分布不均勻時(shí)，通過(guò)WPGMA 聚類的方法將種群歸類為不同的簇，再計(jì)算各個(gè)簇內(nèi)個(gè)體的雜亂度；找到雜亂度最低的個(gè)體，按照就近原則接納該個(gè)體附近的個(gè)體，最終填滿整個(gè)歸檔集；當(dāng)解集分布較為均勻時(shí)，則直接在種群內(nèi)找到雜亂度最低的個(gè)體，再按照聚集密度從小到大的次序依次納入歸檔集。通過(guò)Matlab PlatEMO 平臺(tái)，選擇3 種測(cè)試MOP（IMOP、ZDT 及VNT）與4 種MOEA（SPEA2、NSGAⅡ、CAMOEA 及RVEAa）進(jìn)行比較，發(fā)現(xiàn)CM-SPEA2在IGD和Spacing指標(biāo)上均不同程度地占一定優(yōu)勢(shì)，且在多數(shù)MOP上比SPEA2性能更有提升。后續(xù)研究中，將重點(diǎn)探討動(dòng)態(tài)多目標(biāo)優(yōu)化、多目標(biāo)優(yōu)化的魯棒性［20］等，以期進(jìn)一步改進(jìn)算法，并將其應(yīng)用于機(jī)器人路徑規(guī)劃。