采用放松支配關(guān)系的高維多目標(biāo)微分進(jìn)化算法

申曉寧，孫 毅，薛云勇

南京信息工程大學(xué) 信息控制學(xué)院，南京 210044

1 引言

近年來(lái)，多目標(biāo)進(jìn)化算法[1]（Multi-Objective Evolutionary Algorithms，MOEA）已經(jīng)取得了飛速的發(fā)展，在許多方面都已有廣泛的應(yīng)用。但現(xiàn)有的多目標(biāo)進(jìn)化算法一般是針對(duì)2到3個(gè)目標(biāo)問(wèn)題而設(shè)計(jì)。在現(xiàn)實(shí)生活中，隨著研究問(wèn)題的復(fù)雜度越來(lái)越高，優(yōu)化目標(biāo)的個(gè)數(shù)也不僅僅局限于2到3個(gè)，有時(shí)往往會(huì)達(dá)到4個(gè)甚至更多。當(dāng)優(yōu)化問(wèn)題的目標(biāo)個(gè)數(shù)達(dá)到4個(gè)及以上時(shí)，稱這類優(yōu)化問(wèn)題為高維多目標(biāo)優(yōu)化問(wèn)題[2]（Many-Objective Optimization Problems，MaOPs）。隨著目標(biāo)維數(shù)的增加，傳統(tǒng)多目標(biāo)進(jìn)化算法（MOEAs）的優(yōu)化效果大大降低。主要原因有：（1）隨著目標(biāo)維數(shù)的增加，傳統(tǒng)的Pareto支配關(guān)系難以區(qū)分出不同解之間的優(yōu)劣，導(dǎo)致基于Pareto支配關(guān)系的多目標(biāo)進(jìn)化算法收斂性能下降；（2）隨著目標(biāo)維數(shù)的增加，傳統(tǒng)多目標(biāo)進(jìn)化算法為了保證算法所得解集的多樣性，采用的多樣性保持機(jī)制通常偏好極端個(gè)體，這將進(jìn)一步影響算法在高維多目標(biāo)優(yōu)化問(wèn)題上的搜索能力。因此，如何針對(duì)高維多目標(biāo)優(yōu)化問(wèn)題，設(shè)計(jì)出一種在收斂性能和多樣性之間達(dá)到較好平衡的進(jìn)化算法，成為進(jìn)化計(jì)算領(lǐng)域的一個(gè)難點(diǎn)和熱點(diǎn)問(wèn)題。

目前所提出的高維多目標(biāo)進(jìn)化算法主要分為如下幾類：（1）采用基于Pareto支配的方法，在該方法基礎(chǔ)上結(jié)合其他有效方法以縮小搜索空間或降低目標(biāo)維數(shù)。如在搜索過(guò)程中加入決策者的偏好信息以縮小Pareto前沿區(qū)域[3]，Deb等人提出了基于主成分分析的目標(biāo)縮減方法[4]，并將其結(jié)合到NSGA_II[5]算法中。然而，該類方法只適用于能夠預(yù)知偏好信息或目標(biāo)主次的問(wèn)題。與該方法類似，學(xué)者袁家偉提出了一種基于Simplex支配的方法[6]。該方法相比于Pareto支配的方法，其優(yōu)點(diǎn)是遠(yuǎn)遠(yuǎn)提高了解的選擇壓力，缺點(diǎn)是缺少高效的機(jī)制用于維持群體的多樣性。（2）采用放松的Pareto支配方法，使得原先無(wú)法兩兩比較優(yōu)劣的非支配個(gè)體之間能夠進(jìn)行比較與選擇。如優(yōu)勝關(guān)系[7]，改進(jìn)的α-支配[8]等，該方法在一定程度上放寬了非支配個(gè)體之間的比較準(zhǔn)則，增加了解的選擇壓力，但同時(shí)也降低了支配結(jié)果的合理性與可信性。（3）采用非Pareto的支配方法，該類方法采用新的評(píng)價(jià)準(zhǔn)則對(duì)個(gè)體進(jìn)行比較。目前該方法主要有兩類，一類是基于聚合函數(shù)的方法，該方法使用聚合函數(shù)，將一個(gè)高維多目標(biāo)優(yōu)化問(wèn)題分解成一系列單目標(biāo)優(yōu)化問(wèn)題，典型的算法是MOEA/D[9]。另一類是基于評(píng)價(jià)指標(biāo)的方法，該方法采用一個(gè)指標(biāo)作為個(gè)體的適應(yīng)度來(lái)評(píng)價(jià)個(gè)體，典型的算法是IBEA[10]。該方法能夠解決基于Pareto支配所帶來(lái)的問(wèn)題，然而其合理性有待進(jìn)一步驗(yàn)證，且在實(shí)際應(yīng)用中還存在著計(jì)算復(fù)雜度高等問(wèn)題。

微分進(jìn)化算法是一種簡(jiǎn)單、高效和快速的演化算法，具有結(jié)構(gòu)簡(jiǎn)單，易實(shí)現(xiàn)，精確度高、收斂速度快、魯棒性強(qiáng)等優(yōu)點(diǎn)[11]。它的控制參數(shù)少、便于學(xué)習(xí)、空間復(fù)雜度低、便于擴(kuò)展，可以處理更大范圍、更加重要的優(yōu)化問(wèn)題。因此，現(xiàn)在越來(lái)越多的學(xué)者開(kāi)始將微分進(jìn)化算法運(yùn)用到高維優(yōu)化問(wèn)題中。王旭提出了一種解決高維優(yōu)化問(wèn)題的差分進(jìn)化算法[12]，將協(xié)同進(jìn)化思想引入到差分進(jìn)化領(lǐng)域，采用一種由狀態(tài)觀測(cè)器和隨機(jī)分組策略組成的協(xié)同進(jìn)化方案。該方案有效地增強(qiáng)了算法解決高維優(yōu)化問(wèn)題的搜索速度和能力。

為了進(jìn)一步提高進(jìn)化算法在求解MaOPs時(shí)的收斂性能和多樣性，本文提出采用放松支配關(guān)系的高維多目標(biāo)微分進(jìn)化算法，簡(jiǎn)稱RDMODE（differential evolution algorithm for many-objective using relaxed dominance relation）。在12組標(biāo)準(zhǔn)測(cè)試函數(shù)中的仿真對(duì)比結(jié)果表明了所提算法的有效性。

2 高維多目標(biāo)優(yōu)化問(wèn)題的難點(diǎn)

假設(shè)求解具有m個(gè)目標(biāo)的最小化問(wèn)題，則多目標(biāo)優(yōu)化問(wèn)題的數(shù)學(xué)模型可以描述如下：

其中，x為決策向量，y為目標(biāo)向量，X為決策向量x形成的決策空間，Y為目標(biāo)向量y形成的目標(biāo)空間。gi(x)≤0,i=1,2,…,h為 x需滿足的h個(gè)約束條件。當(dāng)目標(biāo)維數(shù)m≥4時(shí)，即為高維多目標(biāo)優(yōu)化問(wèn)題MaOPs。

求解多目標(biāo)優(yōu)化問(wèn)題時(shí)，最常采用的是基于Pareto支配關(guān)系的比較方法。設(shè)Xf為多目標(biāo)優(yōu)化的可行解集，F(xiàn)(x)=(f1(x),f2(x),…,fm(x))為目標(biāo)向量，x1∈Xf，x2∈Xf。稱 x1Pareto支配 x2（簡(jiǎn)稱支配，記作 x1?x2）當(dāng)且僅當(dāng)

在MaOPs的求解中存在如下難點(diǎn)：（1）隨著目標(biāo)維數(shù)的增加，如果仍采用常規(guī)的Pareto支配關(guān)系，將導(dǎo)致群體中非支配個(gè)體所占的比例迅速上升，個(gè)體間難以區(qū)分優(yōu)劣，算法的選擇壓力過(guò)小，進(jìn)化選擇近似為隨機(jī)選擇而失去優(yōu)勝劣汰的作用。（2）當(dāng)優(yōu)化目標(biāo)大于3個(gè)時(shí)，算法得到的解集無(wú)法在傳統(tǒng)的直角坐標(biāo)系中表示出來(lái)，因而增加了可視化的難度，為決策者的最終選擇制造了障礙。（3）目標(biāo)維數(shù)的增加使得近似Pareto最優(yōu)前沿解的個(gè)數(shù)劇增，不利于決策者在如此龐大的集合中，找出滿足其需要的解。（4）當(dāng)使用大規(guī)模的進(jìn)化種群時(shí)，能夠在一定程度上緩解因目標(biāo)維數(shù)增加而導(dǎo)致的進(jìn)化算法收斂性能的下降，也可能得到近似分布在整個(gè)最優(yōu)前沿的解集，但隨之而來(lái)的是空間復(fù)雜度和時(shí)間復(fù)雜度的劇增。

3 基于放松支配關(guān)系的高維多目標(biāo)微分進(jìn)化算法

3.1 rel-支配的放松Pareto支配關(guān)系

本文提出一種稱為rel-支配的放松Pareto支配關(guān)系。假設(shè)求解高維多目標(biāo)最小化問(wèn)題，設(shè)x1和x2為MaOPs可行解集 Xf上兩個(gè)不同的解，F(xiàn)(x)=(f1(x),f2(x),…,fm(x))為目標(biāo)向量，稱x1rel-支配x2當(dāng)且僅當(dāng)

其中，m為MaOPs中的目標(biāo)個(gè)數(shù)。如果一個(gè)解x∈Xf不受Xf中任何其他解rel-支配，則稱x為該問(wèn)題中的rel非支配解。

由于目標(biāo)維數(shù)越高，解之間越難進(jìn)行比較，因此，所提rel-支配關(guān)系對(duì)Pareto支配關(guān)系的放松程度依據(jù)目標(biāo)維數(shù)m的不同取值而作自適應(yīng)調(diào)整，具體見(jiàn)圖1所示。圖1的縱坐標(biāo)表示放松程度，該取值越小，說(shuō)明rel-支配關(guān)系對(duì)Pareto支配關(guān)系的放松程度越大。當(dāng)給定問(wèn)題的目標(biāo)維數(shù)m≤4時(shí)，此時(shí)兩兩解之間容易比較優(yōu)劣，故縱坐標(biāo)的取值接近于1，即rel-支配關(guān)系的放松程度很??；當(dāng)m＞4時(shí)，此時(shí)比較出兩兩解之間優(yōu)劣的難度逐漸加大，故rel-支配關(guān)系的放松程度隨m的增大而逐漸增大。由式（3）也可以看出，隨著m的增大，(1-e-20/m)取值減小，即rel-Pareto的放松尺度增大。此外，式（3）未引入額外的參數(shù)，避免了ε-支配關(guān)系[13]中，參數(shù)ε需要事先手工確定的不足。

圖1 rel-支配關(guān)系中解的放松程度隨著目標(biāo)個(gè)數(shù)變化的曲線

圖2 給出了基于rel-支配關(guān)系比較兩個(gè)解x1和x2的示意圖。由圖可見(jiàn)，如果基于Pareto支配關(guān)系，x1和x2互不支配，但如果采用放松后的rel-支配關(guān)系，使得解x1相對(duì)于解x2在目標(biāo) f1上的值由原來(lái)的大于關(guān)系變成小于，在目標(biāo) f2的值比原來(lái)更小，即經(jīng)過(guò)rel-支配關(guān)系后，解x1由圖中所看到的位置變成了解x′1在圖中的位置，則此時(shí)解x1顯然能夠rel-支配解x2。

圖2 基于rel-支配關(guān)系比較兩個(gè)解x1和x2

綜上所述，本文采用rel-支配關(guān)系能夠更加有效地區(qū)分出個(gè)體之間的優(yōu)劣，增加選擇壓力，以改進(jìn)常規(guī)Pareto支配關(guān)系帶來(lái)的群體中非支配解過(guò)多的不足，將其運(yùn)用到高維多目標(biāo)微分進(jìn)化算法中，能夠更加有效地引導(dǎo)算法的搜索方向，從而提高算法的搜索效率。

3.2 群體與外部存儲(chǔ)器的協(xié)同進(jìn)化

所提算法RDMODE采用一個(gè)群體POP和一個(gè)外部存儲(chǔ)器Archive協(xié)同進(jìn)化的策略。Archive中保存由歷代群體搜索到的rel非支配解。在Archive中精英個(gè)體染色體信息的指導(dǎo)下，對(duì)POP分別采用兩種變異方式，生成子代群體。利用生成的子代群體，采用基于指標(biāo)的方法更新POP使得POP能夠較快地向問(wèn)題真實(shí)的Pareto前沿收斂；將子代群體搜索到的rel非支配解對(duì)Archive更新，并采用基于Lp-范數(shù)距離的多樣性維護(hù)策略裁剪Archive，使得Archive的規(guī)模不超過(guò)預(yù)先設(shè)定的大小，并保持良好的多樣性。POP和Archive相互輔助、相互促進(jìn)，共同推動(dòng)算法在收斂性和多樣性之間維持平衡。

在子代群體生成的過(guò)程中，首先對(duì)POP采用DE/rand/2變異策略和二項(xiàng)式交叉策略，生成子代群體NPOP1。因?yàn)樵摬呗圆捎秒S機(jī)搜索方式，有利于算法探索到更多的解，提高算法的多樣性。DE/rand/2變異策略和二項(xiàng)式交叉策略的表達(dá)式分別如式（4）和式（5）所示：

其中，變異策略DE/rand/2中的3個(gè)隨機(jī)個(gè)體 xr1、xr3、xr5取自POP，另兩個(gè) xr4、xr2取自Archive，，以充分利用Archive中個(gè)體的優(yōu)良遺傳特性，并且增強(qiáng)所生成子代個(gè)體的多樣性。變異因子F是區(qū)間[0.8，0.9]內(nèi)均勻產(chǎn)生的隨機(jī)數(shù)，Vi是經(jīng)過(guò)變異后得到的中間個(gè)體，randj[ ]0,1 為[0，1]之間滿足均勻分布的隨機(jī)數(shù)。當(dāng)randj[ ]0,1小于等于給定的交叉概率CR或 j=jrand（Vi,j為中間個(gè)體Vi的第 j維，j=1,2,…,n,n為決策變量的維數(shù)，jrand為從{ }1,2,…,n中均勻隨機(jī)產(chǎn)生的整數(shù)）時(shí)，將變異得到的中間個(gè)體Vi的第 j維作為子代個(gè)體Ui的第 j維，否則，將原來(lái)的父代個(gè)體xi第 j維作為子代個(gè)體Ui的第 j維。

對(duì)POP再采用DE/current-to-best/1變異策略和二項(xiàng)式交叉策略，生成子代群體NPOP2。該策略將群體POP中的當(dāng)前個(gè)體作為初始個(gè)體，將外部存儲(chǔ)器中的精英個(gè)體作為指導(dǎo)個(gè)體進(jìn)行變異操作，有利于增加算法的收斂速度，避免陷入局部最優(yōu)。式（6）給出了DE/current-to-best/1變異策略的表達(dá)式，二項(xiàng)式交叉策略表達(dá)式同式（5）。

其中，變異策略DE/current-to-best/1中的兩個(gè)隨機(jī)個(gè)體xr2、xr3和當(dāng)前個(gè)體xi取自POP，xbest個(gè)體隨機(jī)取自Archive，，變異因子 F1、F2是區(qū)間[0.8，0.9]內(nèi)均勻產(chǎn)生的隨機(jī)數(shù)，該策略生成子代群體的方式同上。

為了加強(qiáng)算法的收斂性能，采用基于指標(biāo)的方法計(jì)算POP∪NPOP(NPOP=NPOP1∪NPOP2)中每個(gè)個(gè)體的適應(yīng)度，并對(duì)群體進(jìn)行更新，生成新一代群體POP。令I(lǐng)ε+表示一個(gè)指標(biāo)，該指標(biāo)描述了在目標(biāo)空間中，一個(gè)解支配另一個(gè)解所需要的最小距離[10]。

根據(jù)這個(gè)指標(biāo)為個(gè)體分配相應(yīng)的適應(yīng)值，式（8）給出了個(gè)體x1的適應(yīng)值計(jì)算方法[14]：

對(duì)群體進(jìn)行更新時(shí)，將適應(yīng)值小的個(gè)體依次從群體中移除，直到滿足規(guī)定的群體規(guī)模為止。

在生成新的外部存儲(chǔ)器的過(guò)程中，采用了基于Lp-范數(shù)（0

其中，d表示數(shù)據(jù)空間的維數(shù)，Lp(x,y)表示在d維數(shù)據(jù)空間中，向量(x1,x2,…,xd)與向量(y1,y2,…,yd)之間的Lp-范數(shù)距離。

當(dāng)Archive中的個(gè)體數(shù)量超出規(guī)定的容量時(shí)，首先將Archive中在每個(gè)目標(biāo)上具有最大/最小目標(biāo)值的個(gè)體加入一個(gè)空的外部存儲(chǔ)器Archive′中，然后每次從Archive中，選擇距離Archive′中現(xiàn)有個(gè)體最短Lp-范數(shù)距離值最大的個(gè)體加入Archive′，如此反復(fù)直到Archive′中解的個(gè)數(shù)滿足規(guī)定的容量為止。該策略能夠有效地維護(hù)外部存儲(chǔ)器中個(gè)體的多樣性。

3.3 算法步驟

所提算法RDMODE詳細(xì)步驟如下：

步驟1初始化。設(shè)置算法的最大目標(biāo)評(píng)價(jià)次數(shù)為nmb_obj_max。隨機(jī)產(chǎn)生一個(gè)規(guī)模為N的初始群體POP并計(jì)算其目標(biāo)值，令目標(biāo)評(píng)價(jià)次數(shù)計(jì)數(shù)器nmb_obj=N，規(guī)定nArchive為外部存儲(chǔ)器最大保留個(gè)數(shù)，求出POP中的rel非支配解并將其存于Archive中。

步驟2繁殖操作。分別對(duì)POP利用不同的變異、交叉策略生成子代群體NPOP1和NPOP2。累計(jì)目標(biāo)評(píng)價(jià)次數(shù)為表示集合中元素個(gè)數(shù)）。

步驟3求出子代中的rel非支配解。令NPOP=NPOP1∪NPOP2，求出NPOP中的rel非支配解。

步驟4更新與裁減POP和Archive。令POP=，若，則采用基于指標(biāo) Iε+的方式更新POP。確定出中的rel非支配解，并賦給Archive，若，則采用基于Lp-范數(shù)距離的多樣性維護(hù)策略對(duì)Archive進(jìn)行更新。

步驟5終止準(zhǔn)則判斷。如果目標(biāo)評(píng)價(jià)次數(shù)nmb_obj達(dá)到對(duì)應(yīng)問(wèn)題的nmb_obj_max，則終止算法，把當(dāng)前外部存儲(chǔ)器Archive作為最終的滿意解集輸出，否則轉(zhuǎn)到步驟2。

3.4 算法的計(jì)算復(fù)雜度

在MaOPs中，隨著目標(biāo)個(gè)數(shù)的不斷增多，算法的計(jì)算復(fù)雜度也越來(lái)越大。采用一個(gè)含有m個(gè)目標(biāo)，群體規(guī)模為N的多目標(biāo)優(yōu)化問(wèn)題作為例子。所提算法RDMODE的計(jì)算復(fù)雜度主要包括以下幾個(gè)方面：（1）從生成的子代群體中確定rel非支配解其復(fù)雜度為O(mN2)；（2）采用基于指標(biāo)的方式更新POP，它的復(fù)雜度為O(N2)；（3）采用rel支配關(guān)系更新Archive，它在比較個(gè)體間支配關(guān)系時(shí)的復(fù)雜度為O(Nlg(m-2)N)，在計(jì)算個(gè)體間的Lp-范數(shù)距離以維護(hù)多樣性時(shí)的復(fù)雜度為O(mN2)。綜上，該算法總的復(fù)雜度為max{O(Nlg(m-2)N),O(mN2)}。

4 仿真實(shí)驗(yàn)

4.1 優(yōu)化問(wèn)題描述

為了驗(yàn)證所提算法RDMODE的有效性，將其用于DTLZ1和DTLZ2這兩類目標(biāo)可擴(kuò)展的測(cè)試問(wèn)題上[16]。本實(shí)驗(yàn)在DTLZ1和DTLZ2中，將目標(biāo)個(gè)數(shù)m分別取為m=3，5，8，10，15，20。因此，實(shí)驗(yàn)中一共包括了12個(gè)不同的高維多目標(biāo)測(cè)試函數(shù)。

4.2 參數(shù)設(shè)置

Two_Arch2[14]是近年來(lái)涌現(xiàn)出的一種具有代表性的高維多目標(biāo)進(jìn)化算法。文獻(xiàn)[14]將Two_Arch2與其他已有的高維多目標(biāo)進(jìn)化算法Two_Arch[17]、IBEA、NSGA_III[18]、MOEA/D進(jìn)行比較，以測(cè)度IGD[19]作為評(píng)判標(biāo)準(zhǔn)，實(shí)驗(yàn)結(jié)果表明Two_Arch2在收斂性和分布性能方面均優(yōu)于上述對(duì)比算法。NSGA_II[5]是一種經(jīng)典的快速非支配排序多目標(biāo)精英遺傳算法，已成功應(yīng)用于多種實(shí)際多目標(biāo)優(yōu)化問(wèn)題中。將所提算法RDMODE與Two_Arch2、NSGA_II在4.1節(jié)中的測(cè)試函數(shù)上進(jìn)行對(duì)比實(shí)驗(yàn)。所提算法的參數(shù)設(shè)置依據(jù)實(shí)驗(yàn)結(jié)果調(diào)試得到，算法Two_Arch2的參數(shù)設(shè)置參照文獻(xiàn)[14]，算法NSGA_II的參數(shù)設(shè)置參照文獻(xiàn)[16]，各算法參數(shù)具體設(shè)置見(jiàn)表1。

表1 3種算法的參數(shù)設(shè)置

為了體現(xiàn)算法比較的公平性，3種算法的終止準(zhǔn)則均采用目標(biāo)向量評(píng)價(jià)次數(shù)達(dá)到給定的最大值，最大目標(biāo)向量評(píng)價(jià)次數(shù)對(duì)不同的測(cè)試問(wèn)題，以及不同的目標(biāo)個(gè)數(shù)m，取不同的值，參數(shù)具體設(shè)置見(jiàn)表2。

4.3 實(shí)驗(yàn)比較

使用測(cè)度IGD、測(cè)度C_Metric[20]以及作圖法，將RDMODE與Two_Arch2、NSGA_II進(jìn)行比較。測(cè)度IGD描述了問(wèn)題真實(shí)Pareto前沿中的個(gè)體到算法搜索到的解集中個(gè)體的平均最短距離，它的值越小，說(shuō)明算法獲得的解集收斂性和分布性越好，即越接近于真實(shí)的Pareto前沿。測(cè)度C_Metric度量?jī)煞N算法搜索到的近似Pareto非支配解集間相互支配的程度，C(X1,X2)＞C(X2,X1)表明集合X1在C測(cè)度上的性能優(yōu)于X2。

表2 3種算法在測(cè)試函數(shù)上取不同目標(biāo)時(shí)的最大目標(biāo)評(píng)價(jià)次數(shù)設(shè)置

圖3、圖4分別給出了各算法在DTLZ1和DTLZ2，取m=3時(shí)，由100個(gè)解構(gòu)成的Pareto前沿。由圖4可以看出RDMODE和Two_Arch2均能收斂到真實(shí)的Pareto前沿，但所提算法RDMODE得到的解的分布性更好。從圖5中可以看出，RDMODE和Two_Arch2算法無(wú)論是在收斂性上還是在分布性上效果都遠(yuǎn)比NSGA_II好。由此可見(jiàn)，在MaOPs中，僅靠Pareto支配排序已不能區(qū)分出個(gè)體的優(yōu)劣。同時(shí)，個(gè)體選擇壓力的丟失也會(huì)導(dǎo)致分布性選擇策略的失效。Li等人[21]的實(shí)驗(yàn)結(jié)果表明，NSGA_II中的擁擠距離策略甚至?xí)贛aOPs上對(duì)群體的進(jìn)化起到反作用。

將3種算法分別在12個(gè)測(cè)試函數(shù)上獨(dú)立運(yùn)行10次。表3給出了3種算法在測(cè)度C_Metric上的平均值和標(biāo)準(zhǔn)差。

從表3可以看出，所提算法RDMODE在12組測(cè)試函數(shù)中得到的C_Metric值，總體上顯著優(yōu)于其他兩種算法得到的C_Metric值。在DTLZ1上，除了在目標(biāo)個(gè)數(shù)為5時(shí)，算法Two_Arch2得到的C_Metric值較大外，其余情況下所提算法RDMODE均具有更大的C_Metric值，即有更高的支配比例；在DTLZ2中，當(dāng)目標(biāo)維數(shù)m取3或5時(shí)，Two_Arch2的C_Metric值更優(yōu)于其余兩種算法，隨著目標(biāo)維數(shù)的不斷增加，所提算法RDMODE有最好的C_Metric值，尤其當(dāng)目標(biāo)維數(shù)m≥10時(shí)，所提算法得到的解集，能夠支配Two_Arch2解集中解的比例較大，而Two_Arch2支配所提算法解集的比例為0；由于較差的收斂性，算法NSGA_II在所有測(cè)試函數(shù)中的C_Metric值最差。這也驗(yàn)證了在高維多目標(biāo)優(yōu)化問(wèn)題中，所提算法RDMODE的收斂性總體上較其余兩種算法的收斂性要好。

表4給出了3種算法在測(cè)度IGD上的平均值和標(biāo)準(zhǔn)差。

從表4可見(jiàn)，在DTLZ1中，當(dāng)目標(biāo)維數(shù)m取3、5、8時(shí)，所提算法RDMODE較Two_Arch2有更好的IGD平均值，其余情況下算法Two_Arch2的IGD平均值更好；在 DTLZ2中，當(dāng)目標(biāo)維數(shù) m 取 3、5、8、10時(shí)，算法Two_Arch2優(yōu)于RDMODE，有相對(duì)不錯(cuò)的IGD平均值，當(dāng)目標(biāo)維數(shù)m＞10時(shí)，所提算法RDMODE得到的IGD平均值最好；由此可見(jiàn)，所提算法對(duì)于DTLZ1中目標(biāo)個(gè)數(shù)相對(duì)較小的函數(shù)，能夠取得較好的IGD性能，而對(duì)于DTLZ2卻在目標(biāo)個(gè)數(shù)較大時(shí)獲得更優(yōu)的IGD性能。由于NSGA_II的進(jìn)化機(jī)制不能適應(yīng)MaOPs的高維環(huán)境，它得到的IGD平均值在12個(gè)測(cè)試函數(shù)上依然最差。此外，所提算法RDMODE在絕大部分測(cè)試函數(shù)上得到的標(biāo)準(zhǔn)差均最小，表明了所提算法具有較穩(wěn)定的搜索性能，在不同運(yùn)行次數(shù)中得到數(shù)據(jù)集的IGD值變化幅度較小。

圖3 3目標(biāo)DTLZ1問(wèn)題中Pareto前沿的比較

圖4 3目標(biāo)DTLZ2問(wèn)題中Pareto前沿的比較

表3 兩兩算法在DTLZ1、DTLZ2上的C_Metric值

表4 各算法在DTLZ1、DTLZ2上的IGD值

由上述結(jié)果可見(jiàn)，所提算法RDMOEA是一種高效的高維多目標(biāo)進(jìn)化算法。在大部分測(cè)試函數(shù)，尤其在目標(biāo)維數(shù)較高的函數(shù)上，得到的解集較已有的代表性高維算法Two_Arch2具有更好的收斂性和多樣性。這主要?dú)w因于所提算法RDMOEA采用了一種新的放松支配關(guān)系，有效地增加了群體的選擇壓力，提高了算法的收斂速度；同時(shí)，所提算法RDMOEA采用群體和外部存儲(chǔ)器協(xié)同進(jìn)化的方式，由于外部存儲(chǔ)器能夠給群體的進(jìn)化方向提供指導(dǎo)信息，而生成的子代群體采用基于指標(biāo)的適應(yīng)度評(píng)價(jià)機(jī)制更新進(jìn)化群體和采用Lp-范數(shù)距離的多樣性維護(hù)策略更新外部存儲(chǔ)器，兩者相互合作，共同促進(jìn)，使得所提算法RDMOEA能夠在收斂性和多樣性之間維持較好的平衡。

5 結(jié)束語(yǔ)

本文提出了采用放松支配的高維多目標(biāo)微分進(jìn)化算法RDMOEA，該算法設(shè)計(jì)了一種rel支配關(guān)系放寬解的比較準(zhǔn)則，該關(guān)系能夠依據(jù)目標(biāo)個(gè)數(shù)自適應(yīng)地調(diào)整對(duì)Pareto支配的放松程度，且未引入額外的參數(shù)；采用群體和外部存儲(chǔ)器協(xié)同進(jìn)化的方案增加了算法的搜索速度和搜索效率，并使用混合微分進(jìn)化算子搜索解空間。將所提算法RDMOEA和其余兩種優(yōu)秀的多目標(biāo)進(jìn)化算法在目標(biāo)可擴(kuò)展的標(biāo)準(zhǔn)測(cè)試函數(shù)集DTLZ1和DTLZ2上進(jìn)行了對(duì)比，實(shí)驗(yàn)結(jié)果表明所提算法RDMOEA在求解MaOPs時(shí)，能夠產(chǎn)生一組收斂性能和分布性能均較優(yōu)的非支配解，從而表明算法所設(shè)計(jì)的策略是可行而有效的。今后的工作將進(jìn)一步研究所提算法RDMOEA中參數(shù)的自適應(yīng)控制方法，并將它應(yīng)用于實(shí)際優(yōu)化問(wèn)題。