喬鋼柱，王瑞，孫超利*

（1.太原科技大學(xué)計算機(jī)科學(xué)與技術(shù)學(xué)院，太原 030024；2.中北大學(xué)大數(shù)據(jù)學(xué)院，太原 030051）

0 引言

自然科學(xué)、社會科學(xué)和工程技術(shù)等許多領(lǐng)域中都存在同時優(yōu)化多個目標(biāo)的問題，例如流水車間調(diào)度［1］和電力系統(tǒng)規(guī)劃［2］，其優(yōu)化目標(biāo)之間往往是相互沖突的，這些優(yōu)化問題統(tǒng)稱為多目標(biāo)優(yōu)化問題。由于其多個目標(biāo)之間的相互沖突，所能找到的往往是一組解集，而不是能同時使得所有目標(biāo)取得最優(yōu)的一個解。

多目標(biāo)優(yōu)化問題的數(shù)學(xué)模型如下：

式中：x=(x1，x2，…，xn)為n維決策變量，S為x的可行域；fi（x）表示x的第i(i=1，2，…，m)個目標(biāo)函數(shù)，m為目標(biāo)函數(shù)個數(shù)。通常當(dāng)優(yōu)化目標(biāo)個數(shù)超過3 個時，稱之為高維多目標(biāo)優(yōu)化問題（Many-objective Optimization Problems，MaOPs）［3］。

進(jìn)化多目標(biāo)算法［4-5］由于其具有較好的全局搜索能力，且能夠同時提供多個候選解，從而被越來越多地用于求解多目標(biāo)優(yōu)化問題。到目前為止，學(xué)者們針對多目標(biāo)優(yōu)化問題已提出了很多進(jìn)化優(yōu)化算法，如快速排序算法II（Non-dominated Sorting Genetic Algorithm II，NSGA-II）［4］、基于分解的多目標(biāo)進(jìn)化算法（MultiObjective Evolutionary Algorithm based on Decomposition，MOEA/D）［6］，以及基于指標(biāo)的進(jìn)化算法（Indicator-Based Evolutionary Algorithm，IBEA）［7］。然而，隨著優(yōu)化目標(biāo)函數(shù)個數(shù)的增加，互不支配的個體數(shù)量急劇增加，導(dǎo)致傳統(tǒng)的基于Pareto 支配關(guān)系的選擇策略失效，很難找到新的Pareto 占優(yōu)關(guān)系；同時，目標(biāo)空間維度的增大增加了獲得均勻分布解的難度。為此，學(xué)者們提出了不同的求解高維多目標(biāo)問題的優(yōu)化算法以期獲得較好的最優(yōu)解集。

一般來說，求解高維多目標(biāo)優(yōu)化問題的算法大致可分為四類：

1）第一類是基于Pareto 支配關(guān)系的高維多目標(biāo)優(yōu)化方法。如：Zhang 等［8］提出了基于拐點的進(jìn)化算法（Knee pointdriven Evolutionary Algorithm，KnEA），利用拐點選擇策略替代NSGA-II 中基于擁擠度的選擇策略。Li 等［9］利用偏移密度估計（Shift-based Density Estimation，SDE）機(jī)制改變解在空間中的位置，使得支配關(guān)系發(fā)生變化，從而加速收斂。Qasim等［10］提出了基于排序支配的對抗差分進(jìn)化算法（Rankingdominance-based algorithm with Opposition-based Differential Evolution，RODE）算法，在該算法中采用AR（Average Rank）方法選擇個體。肖婧等［11］提出了一種基于全局排序的高維多目標(biāo)優(yōu)化（Global Ranking based Many-Objective Differential Evolution，GR-MODE）算法，首先采用全局排序提高選擇壓力，然后采用Harmonic 平均擁擠距離對個體進(jìn)行全局密度估計，提高現(xiàn)有局部密度估計方法的精確性。譚陽等［12］提出了一種以超球型支配關(guān)系降低種群中非支配解數(shù)量的粒子群優(yōu)化（Particle Swarm Optimization，PSO）算法，該算法采用模糊支配策略維持選擇壓力，另外通過全局極值的選擇和外部檔案的維護(hù)保持種群個體在目標(biāo)空間的分布。然而，隨著目標(biāo)數(shù)量的增多，大部分個體之間都為互不支配關(guān)系，導(dǎo)致選擇壓力降低，因此增加了這類算法在尋找高維多目標(biāo)非支配最優(yōu)解集的困難。

2）第二類是基于分解的高維多目標(biāo)優(yōu)化方法。Zhang等［6］提出的MOEA/D 將多目標(biāo)優(yōu)化問題通過參考向量轉(zhuǎn)換成若干個單目標(biāo)優(yōu)化問題，并對其同時進(jìn)行優(yōu)化。然后，學(xué)者們基于MOEA/D 提出了很多求解高維多目標(biāo)優(yōu)化問題的改進(jìn)算法，如基于分解、自適應(yīng)繁殖選擇機(jī)制輔助的多目標(biāo)進(jìn)化算法（MultiObjective Evolutionary Algorithm based on Decomposition with an Adaptive Mating Selection mechanism，MOEA/DAMS）［13］和將一個多目標(biāo)分解成多個簡單多目標(biāo)子問題進(jìn)行求解的多目標(biāo)進(jìn)化算法（Multiobjective Optimization Evolutionary Algorithm based on Decomposition of a Multiobjective optimization problem into a number of simple Multiobjective subproblems，MOEA/D-M2M）［14］。He 等［15］提出了一種基于動態(tài)分解排序（Dynamical-Decomposition-based Ranking，DDR）方法的進(jìn)化高維多目標(biāo)優(yōu)化算法，該算法提出動態(tài)分解策略，將解本身作為參考向量，另外子空間的劃分由種群的解和原來的子空間決定。Cheng 等［16］提出了參考向量引導(dǎo)的進(jìn)化算法（Reference Vector guided Evolutionary Algorithm，RVEA），基于角度和到理想點的距離提出了一種新的環(huán)境選擇策略。Qin 等［17］提出了基于分解框架的改進(jìn)粒子群優(yōu)化（Modified Particle Swarm Optimization based on Decomposition with Different ideal points，MPSO/DD）算法，利用多個理想點引導(dǎo)個體，一方面保證了種群的均勻性，另一方面能夠加速引導(dǎo)個體的收斂。鞏敦衛(wèi)等［18］提出了一種基于目標(biāo)分解的高維多目標(biāo)并行進(jìn)化優(yōu)化方法，通過目標(biāo)函數(shù)分組與聚合，將一個高維多目標(biāo)優(yōu)化問題分解為若干子問題，從而降低了問題求解的難度。在基于分解的這類算法中，如何選擇參考向量以及如何基于參考向量進(jìn)行環(huán)境選擇是找到好的Pareto非支配最優(yōu)解集的難點。

3）第三類是基于指標(biāo)的高維多目標(biāo)優(yōu)化方法。IBEA 是第一個基于指標(biāo)的多目標(biāo)進(jìn)化算法。雖然它在高維多目標(biāo)問題收斂方面表現(xiàn)良好，但由于其指標(biāo)缺乏多樣性維護(hù)，它的多樣性很差。While 等［19］提出的基于超體積（HyperVolume，HV）的進(jìn)化算法利用蒙特卡羅模擬近似精確超體積值，超體積是評估收斂性和多樣性的度量?；诜词来嚯x（Inverted Generation Distance，IGD）的多目標(biāo)進(jìn)化算法（IGD indicatorbased Multi-Objective Evolutionary Algorithm，MOEA-IGD）［20］是將反世代距離指標(biāo)作為個體適應(yīng)值的評價標(biāo)準(zhǔn)，它被認(rèn)為是一種可靠的性能指標(biāo)，可以量化多目標(biāo)進(jìn)化算法的收斂性和多樣性。Liu 等［21］提出了一種基于一個接一個選擇策略的進(jìn)化算法（Evolutionary Algorithm using a one-by-one selection strategy，1by1EA），該算法根據(jù)一個收斂指標(biāo)和一個分布指標(biāo)選擇個體，前者測量解與帕累托最優(yōu)前沿之間的距離，后者測量其彼此之間的距離?；谥笜?biāo)的方法能夠生成符合期望性能的結(jié)果，但是算法的計算成本較高，很難達(dá)到快速驗證的結(jié)果。

4）最后一類是不能完全歸到以上某一類的高維多目標(biāo)優(yōu)化算法。例如，Li等［22］將基于分解和基于占優(yōu)的方法結(jié)合，充分利用兩種方法的優(yōu)勢，權(quán)衡算法的收斂性和多樣性，提出了基于支配和分解的進(jìn)化高維多目標(biāo)優(yōu)化算法（highdimensional Many-Objective optimization Evolutionary Algorithm based on Dominance and Decomposition，MOEA/DD）。Deb等［23］結(jié)合NSGA?II 的支配關(guān)系以及分解方法中參考點的使用方法，提出了NSGA?III 算法。Li 等［24］提出了收斂性指標(biāo)和多樣性指標(biāo)，基于該兩種指標(biāo)進(jìn)行非支配排序?qū)崿F(xiàn)環(huán)境選擇，將在高維多目標(biāo)空間的搜索轉(zhuǎn)換為在兩個目標(biāo)空間的搜索，提高了高維多目標(biāo)優(yōu)化的非支配解集的搜索能力。朱占磊等［25］基于線性權(quán)重聚合函數(shù)和支配關(guān)系提出了一種線性權(quán)重最優(yōu)支配關(guān)系，將此支配關(guān)系代替Pareto支配關(guān)系。

基于參考向量的進(jìn)化算法RVEA 是Cheng 等［16］提出的用于求解高維多目標(biāo)優(yōu)化問題的方法，該方法不僅提供了自適應(yīng)的參考向量產(chǎn)生方法，同時提出了基于角度和到理想點距離的新的環(huán)境選擇標(biāo)準(zhǔn)，稱為角度懲罰距離（Angle?Penalized Distance，APD），在進(jìn)化過程中綜合考慮了收斂性和分布性，以期能夠獲得穩(wěn)定的具有較好收斂性能的高維多目標(biāo)進(jìn)化算法。然而，由于RVEA 采用隨機(jī)選擇父代，導(dǎo)致在高維目標(biāo)空間距離遠(yuǎn)的父代差異性大，可能無法生成優(yōu)秀的子代。另外，僅考慮關(guān)聯(lián)個體的子空間，減小了種群的搜索區(qū)域，不能很好地保證種群的多樣性。因此，本文基于RVEA 框架提出了一種基于分解的高維多目標(biāo)改進(jìn)進(jìn)化算法（Improved highdimensional Many-Objective Evolutionary Algorithm based on Decomposition，IMaOEA/D）。在IMaOEA/D 中，針對分配不同數(shù)量個體的子空間，引入精英父代選擇策略，該策略利用個體在目標(biāo)空間距離理想點的距離d1來選擇父代，以期產(chǎn)生較好后代來加快算法的收斂。在環(huán)境選擇中，RVEA 不考慮未分配個體的子空間，導(dǎo)致種群的多樣性變差，故為了保持多樣性，本文首先基于角度懲罰距離（APD）值選擇下一代，隨后對于未分配個體的子空間采用角度指標(biāo)選擇距離該參考向量近的個體作為下一代中個體。實驗結(jié)果表明，本文算法在求解高維多目標(biāo)優(yōu)化問題，特別是針對退化優(yōu)化問題上能夠獲得較好的優(yōu)化性能。

1 RVEA

基于參考向量的進(jìn)化算法RVEA 的主要實現(xiàn)步驟和普通的基于分解的多目標(biāo)優(yōu)化算法一致。在RVEA 中，主要是提出了一種自適應(yīng)的參考向量設(shè)定方法，同時基于參考向量提出了一種角度懲罰距離指標(biāo)，用于多目標(biāo)優(yōu)化中的環(huán)境選擇。

1.1 角度懲罰距離

RVEA 提出使用角度懲罰距離值進(jìn)行環(huán)境選擇，其既考慮了個體的收斂性，同時也根據(jù)個體目標(biāo)函數(shù)值和其相關(guān)參考向量之間的夾角考慮種群的多樣性，其計算式如下：

式中：M表示目標(biāo)的數(shù)目；t和tmax分別為種群當(dāng)代進(jìn)化的代數(shù)和種群進(jìn)化的最大代數(shù)；α是一個預(yù)先設(shè)置的可變參數(shù)，可以控制P(θt，i，j)的變化率；γvt，j是當(dāng)代種群中參考向量vt，j與其他向量之間角度最小值。γvt，j計算式如下：

其中N是參考向量的數(shù)目。

1.2 自適應(yīng)參考向量

通常情況下，參考向量是在目標(biāo)空間均勻產(chǎn)生的。然而，在各類優(yōu)化問題中，由于最優(yōu)解集在目標(biāo)空間中并不一定能夠均勻劃分，因此均勻產(chǎn)生的參考向量可能會阻礙最優(yōu)解集的獲得。為此，在RVEA 中，Cheng 等［16］提出了一種自適應(yīng)的參考向量產(chǎn)生方法，其更新方式如下：

2 基于分解的高維多目標(biāo)改進(jìn)進(jìn)化算法

在進(jìn)化算法中，子代產(chǎn)生的位置會影響算法的尋優(yōu)速度，而在基于參考向量的進(jìn)化算法RVEA 中，子代是通過隨機(jī)選擇兩個父代得到的，隨著目標(biāo)個數(shù)的增加，個體在目標(biāo)空間的分布更加稀疏，隨機(jī)選擇父代不利于算法的收斂性。另外，在RVEA 中，其每個參考向量不一定能夠分配上個體，因此隨著迭代的增加，算法不一定能夠很好地保持種群多樣性。為此，針對這兩個問題，本文提出了一種基于分解的高維多目標(biāo)改進(jìn)優(yōu)化算法（IMaOEA/D）。IMaOEA/D 的偽代碼如算法1所示。

算法1 IMaOEA/D。

從算法1 中可以看到，同其他基于分解的求解高維多目標(biāo)優(yōu)化問題的進(jìn)化算法一樣，IMaOEA/D首先均勻產(chǎn)生若干單位參考向量，并產(chǎn)生一個規(guī)模為N的種群。當(dāng)評價次數(shù)未達(dá)到最大評價次數(shù)時，通過對每個個體根據(jù)本文提出的算法來選擇父代個體（具體見2.1節(jié)中算法2），對其交叉變異產(chǎn)生新個體。隨后，對當(dāng)前父子代基于本文提出的環(huán)境選擇策略（具體見2.2 節(jié)中算法3）實現(xiàn)下一個父代的選擇。算法中，子代的產(chǎn)生采用廣泛使用的二進(jìn)制交叉（Simulated Binary Crossover，SBX）［26］和多項式變異（Polynomial Mutation）［27］。

2.1 父代選擇

選擇什么樣的父代來產(chǎn)生下一代對于算法的最優(yōu)解集搜索具有重要的影響。在本文中，主要考慮通過父代選擇來加快子空間的搜索。故在IMaOEA/D 中，根據(jù)參考向量來尋找父代并產(chǎn)生子代。對任何一個參考向量，從分配給該參考向量的個體集中，根據(jù)沿該參考方向到理想點的距離d1的大小選擇兩個父代個體。d1的計算方法如下：

其中：f(xj)為個體xj的目標(biāo)函數(shù)向量值；vi代表的是第i個參考向量。需要注意的并不是所有參考向量都有分配個體，故對于未能分配至少2 個個體的參考向量，選擇距離理想點最近的一個或者兩個個體作為子代的父代個體。算法2 給出了具體的選擇方法。

算法2 父代個體的選擇方法。

2.2 環(huán)境選擇

在本文方法中，仍舊使用RVEA 中提出的角度懲罰距離指標(biāo)來進(jìn)行環(huán)境選擇。然而，并不是所有的參考向量都一定能有個體和其關(guān)聯(lián)，有可能導(dǎo)致下一父代的種群多樣性缺失。為此，在IMaOEA/D 中，對于沒有個體和其關(guān)聯(lián)的參考向量，尋找在當(dāng)前種群中和其夾角最小的個體，并將其分配給該參考向量，從而保證每個參考向量至少有一個個體是和其相關(guān)聯(lián)的。算法3 給出了本文方法中的環(huán)境選擇策略。從算法3中可以看到，對于任意一個參考向量vi，若分配給其的個體數(shù)至少1個，則選擇APD值最小的個體和該參考向量關(guān)聯(lián)（第5）行）；否則選擇父子代種群個體中和該參考向量夾角最小的個體和該參考向量關(guān)聯(lián)（第7）行）。

算法3 環(huán)境選擇。

3 實驗與結(jié)果分析

3.1 實驗設(shè)置

為驗證本文算法的有效性，在具有10個目標(biāo)和15個目標(biāo)的MaF［28］問題上進(jìn)行了測試。所有實驗均在處理器是Intel Core i7-2670QM CPU @2.2.0 GHz 2.19 GHz、內(nèi)存為8 GB 的PC 上通過Matlab 2016 實現(xiàn)。以下為實驗的一些基本設(shè)置：1）算法在每個測試問題獨(dú)立運(yùn)行20 次；2）最大代數(shù)為1000；3）種群大小和參考向量數(shù)量一樣，10個和15個目標(biāo)的種群大小分別設(shè)為275和135；4）本文算法及其對比算法均采用傳統(tǒng)的二進(jìn)制交叉和多項式變異操作，交叉和變異概率分別為1和1/D，D是決策變量的維度，交叉和變異的分布指標(biāo)都是20。

在角度懲罰距離公式中，參數(shù)α控制懲罰函數(shù)P（θ）的變化率，參數(shù)fr控制參考向量更新的次數(shù)。為了驗證這兩個參數(shù)對本文算法的影響，先固定一個參數(shù)，然后對另一個參數(shù)進(jìn)行分析。固定參數(shù)fr為0.5，α的取值范圍為［1，9］的9 個整數(shù)，其值越大表示收斂性越在前期占主導(dǎo)地位。分別在10、15 個目標(biāo)的MaF8 和MaF10 上作了測試，其中MaF8 的目標(biāo)為線性、退化問題，MaF10 的目標(biāo)為混合、偏置問題。圖1 給出了不同參數(shù)α在這兩個測試問題上的IGD 變化。為了驗證參數(shù)fr對算法的影響，固定α=2，然后使fr在［0.1，0.5］取值。在MaF8 和MaF10 問題進(jìn)行實驗，獨(dú)立運(yùn)行20 次，統(tǒng)計結(jié)果如圖2所示。

圖1 不同α值下不同測試問題的IGD平均值Fig.1 IGD mean values of different test problems with different α values

圖2 不同fr值下不同測試問題的IGD平均值Fig.2 IGD mean values of different test problems with different frvalues

從圖1 中可以看到，給定fr值時，不同的α值對于不同的測試問題，其IGD 值的變化相對平穩(wěn)，表明算法性能對α不是很敏感。但是高維空間中相對較小的α值使收斂性和分布性的重要程度在進(jìn)化前后期的分配更為合理。因此，本文取α=2。

從圖2 中可以看到，在兩個測試問題中，隨著fr值不斷增大，IGD值變化平穩(wěn)。對于線性、退化的15目標(biāo)的MaF8問題，其IGD值隨著fr值的增大而減小。對于解決如MaF8和MaF10等真實Pareto 面復(fù)雜的問題，太頻繁地更新參考向量不利于算法的穩(wěn)定性。本文取更新參考向量的參數(shù)fr=0.5。

3.2 結(jié)果分析

將本文方法在高維目標(biāo)函數(shù)測試集MaF 上進(jìn)行了測試，并和其他近年來發(fā)表的基于分解的、具有較好代表性的4 個算法進(jìn)行了對比，包括參考向量引導(dǎo)的進(jìn)化算法（RVEA）［16］、基于參考方向的Pareto 增強(qiáng)進(jìn)化算法（Strength Pareto Evolutionary Algorithm based on Reference direction，SPEA/R）［29］、基于參考點支配的非支配排序遺傳算法II（Reference Point-based Dominance in Nondominated Sorting Genetic Algorithm-II，RPDNSGA-II）［30］，以及基于支配和分解的進(jìn)化高維多目標(biāo)優(yōu)化算法（MOEA/DD）［22］。為了公平比較，所有算法的種群規(guī)模和運(yùn)行代數(shù)均保持一致，對比算法的其他參數(shù)設(shè)置選擇各自文獻(xiàn)中給出的推薦參數(shù)值。所有算法的IGD 指標(biāo)值均為獨(dú)立運(yùn)行20 次后的平均值，表1 是所有算法獨(dú)立運(yùn)行20 次獲得的IGD 平均值與標(biāo)準(zhǔn)差，其中最好的結(jié)果用加粗表示。

另外，為了比較本文所提算法與另外4 種算法獲得的平均IGD 值之間差異的顯著性，本文采用Wilcoxon 秩和檢驗進(jìn)行兩兩比較，顯著性水平取0.05，表中“+”“-”“≈”分別表示IMaOEA/D 顯著優(yōu)于、顯著劣于和無差別于其他算法。從表1的數(shù)據(jù)可以看出，算法IMaOEA/D 整體的性能優(yōu)于其他對比算法。從秩和檢驗結(jié)果分析，在30 個MaF 測試問題上，算法IMaOEA/D 在其中的14 個上顯著優(yōu)于RVEA，18 個上顯著優(yōu)于SPEA/R，16 個上顯著優(yōu)于RPDNSGA-II，以及在22 個上顯著優(yōu)于MOEA/DD。尤其在測試問題MaF6、MaF8 和MaF9 上，本文算法IMaOEA/D 取得了明顯的優(yōu)勢，表明該算法能較好地處理退化問題。

表1 不同算法在不同目標(biāo)維數(shù)的MaF測試問題上獲得的IGD平均值與標(biāo)準(zhǔn)差Tab.1 IGD mean values and standard deviations obtained by different algorithms on MaF test problems with different dimensions of objectives

續(xù)表

4 結(jié)語

本文提出了一種基于分解的高維多目標(biāo)改進(jìn)優(yōu)化算法（IMaOEA/D），通過引入父代選擇機(jī)制加快收斂，通過在環(huán)境選擇中確保每個參考向量都有一個個體和其對應(yīng)來提高種群的多樣性，從而平衡算法的收斂能力和種群多樣性。在具有10個和15個目標(biāo)的MaF優(yōu)化問題上進(jìn)行了測試，并將本文算法和其他4 個基于分解的優(yōu)化算法進(jìn)行了對比。實驗結(jié)果表明，本文算法在大部分高維多目標(biāo)MaF 優(yōu)化問題上具有較好的尋優(yōu)能力，且在退化問題上具有一定的尋優(yōu)優(yōu)勢。然而，從實驗結(jié)果可以看出，本文算法在Pareto 面為凸面的問題，如MaF3、MaF5 和MaF15 等問題上，其性能表現(xiàn)較差。因此，今后我們將針對這類問題做進(jìn)一步的研究，以期能夠獲得這類問題的較優(yōu)非支配解集。