基于分解的高維多目標改進進化算法

喬鋼柱，王瑞，孫超利*

（1.太原科技大學計算機科學與技術學院，太原 030024；2.中北大學大數據學院，太原 030051）

0 引言

自然科學、社會科學和工程技術等許多領域中都存在同時優化多個目標的問題，例如流水車間調度［1］和電力系統規劃［2］，其優化目標之間往往是相互沖突的，這些優化問題統稱為多目標優化問題。由于其多個目標之間的相互沖突，所能找到的往往是一組解集，而不是能同時使得所有目標取得最優的一個解。

多目標優化問題的數學模型如下：

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

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

一般來說，求解高維多目標優化問題的算法大致可分為四類：

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

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

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

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

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

1 RVEA

基于參考向量的進化算法RVEA 的主要實現步驟和普通的基于分解的多目標優化算法一致。在RVEA 中，主要是提出了一種自適應的參考向量設定方法，同時基于參考向量提出了一種角度懲罰距離指標，用于多目標優化中的環境選擇。

1.1 角度懲罰距離

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

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

其中N是參考向量的數目。

1.2 自適應參考向量

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

2 基于分解的高維多目標改進進化算法

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

算法1 IMaOEA/D。

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

2.1 父代選擇

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

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

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

2.2 環境選擇

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

算法3 環境選擇。

3 實驗與結果分析

3.1 實驗設置

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

在角度懲罰距離公式中，參數α控制懲罰函數P（θ）的變化率，參數fr控制參考向量更新的次數。為了驗證這兩個參數對本文算法的影響，先固定一個參數，然后對另一個參數進行分析。固定參數fr為0.5，α的取值范圍為［1，9］的9 個整數，其值越大表示收斂性越在前期占主導地位。分別在10、15 個目標的MaF8 和MaF10 上作了測試，其中MaF8 的目標為線性、退化問題，MaF10 的目標為混合、偏置問題。圖1 給出了不同參數α在這兩個測試問題上的IGD 變化。為了驗證參數fr對算法的影響，固定α=2，然后使fr在［0.1，0.5］取值。在MaF8 和MaF10 問題進行實驗，獨立運行20 次，統計結果如圖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 值的變化相對平穩，表明算法性能對α不是很敏感。但是高維空間中相對較小的α值使收斂性和分布性的重要程度在進化前后期的分配更為合理。因此，本文取α=2。

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

3.2 結果分析

將本文方法在高維目標函數測試集MaF 上進行了測試，并和其他近年來發表的基于分解的、具有較好代表性的4 個算法進行了對比，包括參考向量引導的進化算法（RVEA）［16］、基于參考方向的Pareto 增強進化算法（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］，以及基于支配和分解的進化高維多目標優化算法（MOEA/DD）［22］。為了公平比較，所有算法的種群規模和運行代數均保持一致，對比算法的其他參數設置選擇各自文獻中給出的推薦參數值。所有算法的IGD 指標值均為獨立運行20 次后的平均值，表1 是所有算法獨立運行20 次獲得的IGD 平均值與標準差，其中最好的結果用加粗表示。

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

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

續表

4 結語

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