多任務(wù)機(jī)制驅(qū)動(dòng)的高維多目標(biāo)進(jìn)化算法

劉天宇，曹 磊

(上海海事大學(xué) 信息工程學(xué)院，上海 201306)

隨著應(yīng)用需求的不斷升級(jí)，現(xiàn)實(shí)生活中的很多問(wèn)題都被抽象化為具有3個(gè)以上排斥目標(biāo)的高維目標(biāo)優(yōu)化問(wèn)題(Many-obJective Optimization Problems，MaOPs)[1]。如在車(chē)聯(lián)網(wǎng)中車(chē)載控制網(wǎng)絡(luò)所面臨的入侵檢測(cè)問(wèn)題[2]、軟件工程中的軟件產(chǎn)品選擇問(wèn)題[3]、救災(zāi)物資的選擇與分配問(wèn)題[4]以及煤炭行業(yè)中的綠色生產(chǎn)優(yōu)化問(wèn)題[5]均可以被建模為高維目標(biāo)優(yōu)化問(wèn)題。因此，近些年來(lái)如何利用多目標(biāo)進(jìn)化算法去求解高維目標(biāo)優(yōu)化問(wèn)題越來(lái)越受到大家的廣泛關(guān)注。然而目前大多數(shù)經(jīng)典的多目標(biāo)進(jìn)化算法在處理高維目標(biāo)優(yōu)化問(wèn)題時(shí)表現(xiàn)出了很大的局限性，其中一個(gè)非常重要的原因在于隨著優(yōu)化問(wèn)題目標(biāo)維數(shù)的增加，進(jìn)化過(guò)程中的選擇壓力會(huì)顯著減小。具體來(lái)講，隨著目標(biāo)維數(shù)的增加，種群中非支配解所占比例會(huì)急劇增大，從而導(dǎo)致算法的搜索能力急劇下降[6-7]。對(duì)于多目標(biāo)進(jìn)化算法，如何在高維目標(biāo)環(huán)境下保持種群的多樣性也是算法設(shè)計(jì)的難點(diǎn)之一[8]。

針對(duì)上述問(wèn)題，目前已經(jīng)出現(xiàn)了多種有效的高維多目標(biāo)進(jìn)化算法(Many-Objective Evolutionary Algorithms，MaOEAs)。一些MaOEAs選擇采用更為寬松的Pareto支配標(biāo)準(zhǔn)[9-10]，或者同時(shí)采用Pareto支配標(biāo)準(zhǔn)與收斂性標(biāo)準(zhǔn)[11]來(lái)緩解算法的選擇壓力。這類(lèi)算法雖然能較好地保證所獲得的Pareto最優(yōu)解集的收斂性，但是很可能獲得分布性較差的Pareto前沿面。一些MaOEAs在傳統(tǒng)多目標(biāo)進(jìn)化算法的基礎(chǔ)上，引入了額外的參考信息來(lái)提高算法在優(yōu)化高維目標(biāo)優(yōu)化問(wèn)題時(shí)的有效性[12-13]。參考信息包括參考向量、參考點(diǎn)以及權(quán)值向量等。由于采用了預(yù)設(shè)的參考信息，這類(lèi)算法可以很好地保證種群多樣性。然而該類(lèi)算法在處理具有不規(guī)則Pareto前沿面的優(yōu)化問(wèn)題時(shí)，仍然具有一定的劣勢(shì)。另有一些MaOEAs通過(guò)平衡優(yōu)化過(guò)程中的收斂性和多樣性來(lái)提升算法的性能，如引入新的評(píng)價(jià)指標(biāo)[14-15]或采用多個(gè)外部種群[16]。然而有時(shí)在高維目標(biāo)環(huán)境下計(jì)算評(píng)價(jià)指標(biāo)可能會(huì)帶來(lái)很大的時(shí)間代價(jià)。

近十年間，以目標(biāo)降維為核心的MaOEAs開(kāi)始不斷涌現(xiàn)[17-18]，這類(lèi)算法不僅可以緩解優(yōu)化過(guò)程中的選擇壓力，同時(shí)在降低問(wèn)題復(fù)雜度以及結(jié)果可視化方面也有其特有的優(yōu)勢(shì)。目前常用的降維方法主要分為：① 是基于相關(guān)性分析的降維方法，其中典型方法有LPCA[19]及NL-MVU-PCA[19]。② 是基于Pareto支配關(guān)系的降維方法，其中典型方法主要有δ-MOSS[20]和k-EMOSS[20]。此外，文獻(xiàn)[17]提出了一種降維新思路，該算法中將目標(biāo)降維問(wèn)題看成一個(gè)新的多目標(biāo)優(yōu)化問(wèn)題來(lái)求解。對(duì)于以目標(biāo)降維為核心的MaOEAs，目標(biāo)子集的質(zhì)量會(huì)直接影響算法的性能。此外，直接基于目標(biāo)子集進(jìn)行優(yōu)化很有可能導(dǎo)致算法在優(yōu)化過(guò)程中有用信息的丟失。因此，筆者提出了一種多任務(wù)機(jī)制[22-23]驅(qū)動(dòng)的高維多目標(biāo)進(jìn)化算法(Many-Objective Evolutionary Algorithm based on MulTitasking mechanism，MT-MaOEA)。該算法同時(shí)優(yōu)化目標(biāo)降維后的低維任務(wù)及原始的高維優(yōu)化任務(wù)，利用兩任務(wù)之間的信息交流，使得算法在利用低維任務(wù)提高搜索能力的同時(shí)避免降維所引起的有用信息丟失。

文中的主要工作如下：

(1) 提出了一種基于多任務(wù)框架的高維目標(biāo)進(jìn)化算法。在該算法中，個(gè)體種群同時(shí)優(yōu)化原始高維任務(wù)以及利用降維算法獲得的低維任務(wù)。

(2) 采用一種自適應(yīng)降維算子在算法運(yùn)行過(guò)程中獲取所需的低維任務(wù)，該算子對(duì)基于相關(guān)性分析及基于Pareto支配關(guān)系的降維方法進(jìn)行了有機(jī)結(jié)合。

(3) 采用任務(wù)間交流算子在實(shí)現(xiàn)兩任務(wù)間信息交流的同時(shí)，完成種群的更新以及對(duì)種群中個(gè)體的任務(wù)分配。

1 高維目標(biāo)優(yōu)化問(wèn)題描述

高維目標(biāo)優(yōu)化問(wèn)題(MaOPs)是由多目標(biāo)優(yōu)化問(wèn)題(Multi-objective Optimization Problems，MOPs)擴(kuò)展而來(lái)的，具體是指具有3個(gè)以上優(yōu)化目標(biāo)的多目標(biāo)優(yōu)化問(wèn)題。對(duì)于MOPs和MaOPs，不存在一個(gè)解可以同時(shí)最優(yōu)化所有的優(yōu)化目標(biāo)。因此多目標(biāo)優(yōu)化算法的目的在于可以找到能夠在多個(gè)目標(biāo)間進(jìn)行平衡的一組解[24]。

以最小化問(wèn)題為例，一個(gè)MaOP問(wèn)題可抽象為如下形式：

minF(x)=(f1(x)，f2(x)，…，fm(x))T，

(1)

其中，x為n維搜索空間中的一個(gè)解(決策向量)；m為目標(biāo)空間的維數(shù)，對(duì)于MaOPs，m>3。

對(duì)于式(1)中定義的高維優(yōu)化問(wèn)題，解x=(x1，x2，…，xn)被稱(chēng)作Pareto弱支配解y=(y1，y2，…，yn)，當(dāng)且僅當(dāng)對(duì)于?j∈{1，2，…，m}，fj(x)≤fj(y)。x被稱(chēng)作Pareto支配y，當(dāng)且僅當(dāng)對(duì)于?j∈{1，2，…，m}，fj(x)≤fj(y)，并且?j∈{1，2，…，M}，fj(x)

由于目標(biāo)空間維數(shù)的增加給現(xiàn)有的多目標(biāo)優(yōu)化算法帶來(lái)了很大的挑戰(zhàn)，因此對(duì)目標(biāo)空間進(jìn)行降維逐漸成為人們?cè)谔幚鞰aOPs時(shí)的一個(gè)重要手段。尤其是對(duì)于很多目標(biāo)函數(shù)間相互冗余的MaOPs問(wèn)題，通過(guò)降維算法來(lái)刪除冗余目標(biāo)在獲得與原始問(wèn)題相同的PF同時(shí)，也可以極大地提高算法的計(jì)算效率。在實(shí)際應(yīng)用中，分析高維目標(biāo)間的冗余性同樣具有重要意義。以工程應(yīng)用中的雷達(dá)波形優(yōu)化問(wèn)題[20]為例，該問(wèn)題可以被建模為一個(gè)具有9個(gè)目標(biāo)的優(yōu)化問(wèn)題。然而有研究者通過(guò)對(duì)目標(biāo)空間進(jìn)行分析發(fā)現(xiàn)，不同目標(biāo)之間存在一定程度的冗余性。對(duì)于該問(wèn)題的仿真結(jié)果同樣表明，通過(guò)分析目標(biāo)之間的冗余性進(jìn)行目標(biāo)降維，可以在提高算法計(jì)算效率的同時(shí)幫助決策者更好地進(jìn)行決策[21]。因此對(duì)于實(shí)際應(yīng)用中的高維目標(biāo)優(yōu)化問(wèn)題，冗余目標(biāo)的分析及處理具有非常重要的現(xiàn)實(shí)意義?，F(xiàn)將降維過(guò)程中的基本概念[17]定義如下，設(shè)定F0= {f1，f2，…，fm}為原始目標(biāo)集，PF0為針對(duì)原始目標(biāo)集的Pareto最優(yōu)前沿面，F(xiàn)?F0為某一目標(biāo)子集，u(F)為對(duì)應(yīng)于F的目標(biāo)向量。

冗余：目標(biāo)子集F被稱(chēng)作是冗余的，當(dāng)且僅當(dāng)F′：=F0/F的Pareto最優(yōu)前沿面為PF′= {u(F′)|u∈PF0}。

不沖突：兩個(gè)目標(biāo)函數(shù)fi∈F0和fj∈F0被稱(chēng)作是不沖突的，當(dāng)且僅當(dāng)對(duì) ?u，v∈PF0都滿(mǎn)足如下公式：

u(fi)≤v(fi)?u(fj)≤v(fj)。

(2)

2 多任務(wù)機(jī)制驅(qū)動(dòng)的高維多目標(biāo)進(jìn)化算法(MT-MaOEA)設(shè)計(jì)

2.1 MT-MaOEA框架

圖1為MT-MaOEA基本框架。由圖1可以看出，MT-MaOEA中個(gè)體種群同時(shí)優(yōu)化兩個(gè)任務(wù)：原始的高維優(yōu)化任務(wù)及經(jīng)過(guò)自適應(yīng)目標(biāo)降維算子后獲得的低維任務(wù)。

兩任務(wù)間通過(guò)任務(wù)間的交流來(lái)使算法能夠利用低維任務(wù)提高搜索能力的同時(shí)，也可以避免降維算法帶來(lái)的信息丟失風(fēng)險(xiǎn)。MT-MaOEA具體步驟如下：

步驟1 從原始目標(biāo)集合中隨機(jī)選擇得出目標(biāo)子集，以此構(gòu)造低維任務(wù)。

步驟2 設(shè)定種群中優(yōu)化兩個(gè)任務(wù)的個(gè)數(shù)數(shù)目均為n，則種群規(guī)模為2×n。

步驟3 初始化種群POP并獲取當(dāng)前Pareto最優(yōu)解集REP，從POP中隨機(jī)選擇一半個(gè)體優(yōu)化原始高維任務(wù)，其余個(gè)體優(yōu)化低維任務(wù)。

步驟4 判斷是否滿(mǎn)足終止條件；若滿(mǎn)足，則輸出當(dāng)前Pareto最優(yōu)解集；否則，至步驟4。

步驟5 利用任務(wù)間交流算子完成對(duì)個(gè)體任務(wù)的重新分配，并獲取下一代的POP及REP。

步驟6 若mod(g，G)=0(g為算法當(dāng)前運(yùn)行代數(shù)，G為設(shè)定的參數(shù))，則利用自適應(yīng)目標(biāo)降維算子獲取新的目標(biāo)子集來(lái)構(gòu)造低維任務(wù)，并跳轉(zhuǎn)至步驟3。

綜上所述，MT-MaOEA設(shè)計(jì)的關(guān)鍵在于自適應(yīng)目標(biāo)降維算子以及任務(wù)間交流算子的設(shè)計(jì)。

2.2 自適應(yīng)目標(biāo)降維算子

對(duì)于MaOPs問(wèn)題，目前現(xiàn)有的目標(biāo)降維方法主要可以分為兩大類(lèi)：基于相關(guān)性分析及基于Pareto支配關(guān)系的目標(biāo)降維方法[17]。其中，基于相關(guān)性分析的降維方法是對(duì)整個(gè)解種群進(jìn)行分析，不單獨(dú)考慮兩個(gè)解個(gè)體之間的關(guān)系。因此對(duì)于算法在運(yùn)行初期所獲得的不能很好地反映理想PF的Pareto最優(yōu)解集，基于相關(guān)性分析的降維方法具有較強(qiáng)的魯棒性?；赑areto支配關(guān)系的降維方法通過(guò)分析每一對(duì)解個(gè)體之間的Pareto支配關(guān)系來(lái)對(duì)目標(biāo)空間進(jìn)行降維。因此該類(lèi)方法在算法獲得的Pareto最優(yōu)解集能夠反映理想PF時(shí)，可以很好地獲得所需的目標(biāo)子集。然而在算法運(yùn)行前期，算法獲得的Pareto最優(yōu)解集與理想Pareto最優(yōu)解集相比都會(huì)有相對(duì)較大的偏差。因此基于Pareto支配關(guān)系的降維方法可能無(wú)法準(zhǔn)確獲得所需的目標(biāo)子集。

基于以上分析，筆者采用一種自適應(yīng)的目標(biāo)降維算子，該算子將兩種經(jīng)典降維技術(shù)LPCA[19](基于相關(guān)性分析的降維方法)及k-EMOSS[20](基于Pareto支配關(guān)系的降維方法)進(jìn)行了有機(jī)結(jié)合。在算法運(yùn)行初期，首先通過(guò)隨機(jī)選擇方式選擇得出一組目標(biāo)子集。隨后算法每運(yùn)行G次，則在當(dāng)前獲得的非支配解集的基礎(chǔ)上，利用自適應(yīng)目標(biāo)降維算子從LPCA與k-EMOSS中選擇合適的方法獲取降維后的目標(biāo)子集。在自適應(yīng)目標(biāo)降維算子中，當(dāng)前目標(biāo)子集的θ指標(biāo)可表示為

(3)

其中，ND={u∈N|?v∈N：v(F)Pareto支配u(F)}，N表示算法當(dāng)前所獲得Pareto最優(yōu)解集，ND則表示在當(dāng)前目標(biāo)子集下N中的被支配個(gè)體集合。因此，θ∈[0，1]，并且θ值越大，則意味著當(dāng)前選擇出的目標(biāo)子集與原始目標(biāo)子集相比Pareto支配關(guān)系保持越差。在這種情況下，自適應(yīng)目標(biāo)降維算子更傾向于選擇基于Pareto支配關(guān)系的k-EMOSS方法來(lái)獲取下一步的目標(biāo)子集。由于k-EMOSS方法的性能非常容易受到算法當(dāng)前所獲得的Pareto最優(yōu)解集質(zhì)量的影響，可在θ指標(biāo)的基礎(chǔ)上進(jìn)一步計(jì)算得出η指標(biāo)。若隨機(jī)數(shù)r小于η，則選擇LPCA方法；否則，選擇k-EMOSS方法進(jìn)行目標(biāo)降維。η指標(biāo)可表示為

(4)

其中，X為當(dāng)前函數(shù)評(píng)價(jià)次數(shù)，Y為最大函數(shù)評(píng)價(jià)次數(shù)。

2.3 任務(wù)間交流算子

MT-MaOEA中通過(guò)任務(wù)間交流算子來(lái)實(shí)現(xiàn)種群的更新以及種群中個(gè)體任務(wù)的分配。算法對(duì)POP中的個(gè)體分別設(shè)置task_id屬性值及rank屬性值。其中，rank屬性表示該個(gè)體在其優(yōu)化的任務(wù)中的表現(xiàn)排序值。排序結(jié)果借助經(jīng)典的非支配排序及擁擠度距離[25]來(lái)實(shí)現(xiàn)，rank值越小，則表示個(gè)體在對(duì)應(yīng)任務(wù)中的表現(xiàn)越好。task_id∈{1，2}用來(lái)指明個(gè)體當(dāng)前優(yōu)化的任務(wù)。task_id=1，表明個(gè)體優(yōu)化的是原始高維任務(wù)；task_id=2，表明個(gè)體優(yōu)化的是經(jīng)過(guò)目標(biāo)降維后的低維任務(wù)。此外，MT-MaOEA算法中對(duì)REP中的非支配個(gè)體分別設(shè)置rank值及aging值。其中rank值表示個(gè)體針對(duì)原始高維任務(wù)的排序結(jié)果，aging值用來(lái)表示個(gè)體出現(xiàn)的代數(shù)。由于進(jìn)化算法在處理MaOPs時(shí)容易出現(xiàn)早熟現(xiàn)象，任務(wù)間交流算子對(duì)REP中排序靠后且出現(xiàn)次數(shù)過(guò)多的個(gè)體進(jìn)行變異來(lái)保持種群的多樣性。筆者采用一種差分變異算子，如下所示：

xm=x+F(x1-x2) ，

(5)

其中，xm為變異后的個(gè)體；x為待變異的個(gè)體；x1為在REP中隨機(jī)選擇出的個(gè)體；x2為在搜索空間中產(chǎn)生的新個(gè)體；參數(shù)F為縮放因子，取值為[0.3，0.9]之間的隨機(jī)數(shù)[26]。

任務(wù)間交流算子的具體操作步驟如下，其中POP(i)表示種群中的第i個(gè)個(gè)體，n為優(yōu)化每個(gè)任務(wù)的個(gè)體數(shù)目。

步驟1 設(shè)置i=1，子代種群CPOP=?；

步驟2 判斷i≤|POP|是否滿(mǎn)足，若滿(mǎn)足則繼續(xù)后續(xù)步驟，否則結(jié)束運(yùn)行；

步驟3 從{1，2，…，|POP|}隨機(jī)選擇得出j，且令j≠i；

步驟4 設(shè)定交叉概率pc=0.5(1+rand (0，1) )，若在[0，1]區(qū)間內(nèi)的隨機(jī)數(shù)r小于pc，則轉(zhuǎn)至步驟5；否則，轉(zhuǎn)至步驟7；

步驟5 對(duì)于父代個(gè)體POP(i)與POP(j)，利用SBX交叉算子[27]產(chǎn)生兩個(gè)子代個(gè)體C1與C2；

步驟6 對(duì)于產(chǎn)生的子代個(gè)體C1與C2，隨機(jī)分配其task_id，并將C1與C2加入CPOP中；

步驟7 分別對(duì)POP(i)與POP(j)進(jìn)行變異操作產(chǎn)生C1與C2，其中C1繼承POP(i)的task_id，C2繼承POP(j)的task_id，并將C1與C2加入CPOP中；

步驟8 令TPOP=POP∪CPOP；

步驟9 從POP中選擇task_id=1的個(gè)體計(jì)算其rank值，并選擇排序前n位的個(gè)體作為POP1；同樣，對(duì)剩余個(gè)體計(jì)算rank屬性值，并選擇排序前n位的個(gè)體作為POP2；

步驟10 產(chǎn)生下一代種群POP=POP1∪POP2；

步驟11 從POP與REP中選擇非支配個(gè)體作為新的REP，并統(tǒng)計(jì)REP中每個(gè)個(gè)體的rank值及aging值。若排序后20%的個(gè)體中存在aging值大于10的情況，則對(duì)該個(gè)體進(jìn)行變異操作，進(jìn)而得出下一代的REP。

2.4 算法時(shí)間復(fù)雜度分析

由MT-MaOEA框架可知，MT-MaOEA在一次迭代中包含如下步驟：任務(wù)間交流算子(用于種群更新)及自適應(yīng)目標(biāo)降維算子(用于構(gòu)造低維任務(wù))。

令MT-MaOEA種群規(guī)模為N，目標(biāo)空間維數(shù)為M(M

3 實(shí)驗(yàn)分析

為了評(píng)估算法性能，選擇5組常用的測(cè)試問(wèn)題：DTLZ5(I，M)、WFG3(M)、WFG7(M)、DTLZ2(M)及DTLZ3(M)。其中DTLZ5(I，M)、WFG3(M)及WFG7(M)為冗余問(wèn)題。對(duì)于DTLZ5(I，M)，M為原始目標(biāo)空間的維數(shù)，I表示降維后理想目標(biāo)子集中的目標(biāo)個(gè)數(shù)。對(duì)DTLZ5(I，M)，前M-I+1個(gè)目標(biāo)函數(shù)之間是互不排斥的。對(duì)于該組問(wèn)題，文中選擇DTLZ5(3，5)、DTLZ5(3，10)、DTLZ5(5，10)、DTLZ5(7，10)、DTLZ5(3，15)、DTLZ5(6，15)及DTLZ5(9，15)作為測(cè)試函數(shù)。對(duì)于WFG3(M)，其理想目標(biāo)子集中目標(biāo)函數(shù)個(gè)數(shù)為2，文中選擇WFG3(3)、WFG3 (5)、WFG3(10)及WFG3(15)作為測(cè)試函數(shù)。對(duì)于WFG7(M)，文中選擇WFG7(3)、WFG7(5)、WFG7(10)及WFG7(15)作為測(cè)試函數(shù)。DTLZ2(M)與DTLZ3(M)是不冗余問(wèn)題，M個(gè)目標(biāo)函數(shù)之間都是互相排斥的。對(duì)該類(lèi)問(wèn)題，文中選擇DTLZ2(3)、DTLZ2(5)、DTLZ2(10)、DTLZ2(15) 、DTLZ3(3)、DTLZ3(5)、DTLZ3(10)及DTLZ3(15)作為測(cè)試函數(shù)。

筆者選擇NSGA-Ⅲ[8]、MaOEA-IGD[15]、NSGA-Ⅱ-LPCA(NSGA-Ⅱ中采用LPCA作為降維算子)、NSGA-Ⅱ-k-EMOSS(NSGA-Ⅱ中采用k-EMOSS作為降維算子)、MT-MaOEA-LPCA(MT-MaOEA中采用LPCA作為降維算子)、MT-MaOEA-k-EMOSS(MT-MaOEA中采用k-EMOSS作為降維算子)作為對(duì)比算法來(lái)驗(yàn)證所提算法的有效性。對(duì)于所有算法，設(shè)置其最大函數(shù)評(píng)價(jià)次數(shù)為30 000。選擇逆世代距離(Inverted Generational Distance，IGD)[15]及分布指標(biāo)(SPacing，SP)[29]作為評(píng)價(jià)算法性能的量化指標(biāo)。IGD值越小，則表明算法搜到的Pareto前沿面與真實(shí)的Pareto前沿面越接近；SP值越小，則說(shuō)明Pareto前沿面的分布越均勻。表1為算法的具體參數(shù)設(shè)置。

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

3.1 參數(shù)分析

算法MT-MaOEA中參數(shù)G用來(lái)調(diào)節(jié)采用自適應(yīng)目標(biāo)降維算子來(lái)構(gòu)造低維任務(wù)的頻率。以適當(dāng)?shù)念l率來(lái)更換低維任務(wù)，一方面可以保證算法的多樣性，同時(shí)也可以避免算法由于長(zhǎng)時(shí)間優(yōu)化同一個(gè)低維任務(wù)引起的計(jì)算量的浪費(fèi)。若G取值過(guò)小，則算法在進(jìn)化過(guò)程中會(huì)頻繁更換所優(yōu)化的低維任務(wù)，進(jìn)而可能引起搜索的退化；若G取值過(guò)大，則算法會(huì)花費(fèi)較多的計(jì)算量來(lái)優(yōu)化同一個(gè)低維任務(wù)，從而造成計(jì)算量的浪費(fèi)。因此，以DTLZ5(3，5)、DTLZ5(5，10)、DTLZ5(6，15)、DTLZ2(5)、DTLZ2(10)以及WFG3(15)為例，借助IGD指標(biāo)來(lái)分析不同G值對(duì)算法性能的影響。表2給出了算法在采用不同G值時(shí)獨(dú)立運(yùn)行30次的平均IGD結(jié)果。由表2可知，隨著G取值的增加，IGD指標(biāo)值總體呈現(xiàn)出逐漸變優(yōu)又進(jìn)而變差的趨勢(shì)。其中，當(dāng)G取值為60時(shí)，算法在大多數(shù)測(cè)試函數(shù)上取得了最優(yōu)的IGD結(jié)果。因此，在文中，參數(shù)G設(shè)置為60。

表2 MT-MaOEA針對(duì)不同G的平均IGD值

3.2 自適應(yīng)降維算子的有效性分析

算法MT-MaOEA中采用一種自適應(yīng)降維算子來(lái)對(duì)目標(biāo)空間進(jìn)行降維，從而獲取所需的低維任務(wù)。該算子將兩種經(jīng)典的降維方法LPCA與k-EMOSS進(jìn)行了有機(jī)結(jié)合。為了分析自適應(yīng)降維算子的有效性，本節(jié)選擇NSGA-Ⅱ-LPCA、NSGA-Ⅱ-k-EMOSS、MT-MaOEA-LPCA以及MT-MaOEA-k-EMOSS作為對(duì)比算法。其中NSGA-Ⅱ-LPCA與NSGA-Ⅱ-k-EMOSS在NSGA-Ⅱ算法基礎(chǔ)上，分別采用了LPCA與k-EMOSS進(jìn)行目標(biāo)降維操作。同樣，MT-MaOEA-LPCA與MT-MaOEA-k-EMOSS在MT-MaOEA算法基礎(chǔ)上分別采用了LPCA與k-EMOSS進(jìn)行目標(biāo)降維操作。

表3展示了5種算法針對(duì)不同測(cè)試函數(shù)通過(guò)30次獨(dú)立運(yùn)行產(chǎn)生的平均IGD值。由表3可知，MT-MaOEA算法在幾乎全部測(cè)試函數(shù)上都獲得了最優(yōu)IGD值。實(shí)驗(yàn)結(jié)果驗(yàn)證了所提算法的有效性。根據(jù)表3中的統(tǒng)計(jì)結(jié)果可知，對(duì)于算法NSGA-Ⅱ及MT-MaOEA，在大多數(shù)測(cè)試函數(shù)上采用LPCA方法的效果要優(yōu)于k-EMOSS方法。這是由于k-EMOSS方法對(duì)于用來(lái)降維的解種群的質(zhì)量要求較高，在解種群不能較好地覆蓋真實(shí)的Pareto前沿面時(shí)，k-EMOSS方法所獲得的目標(biāo)子集與理想目標(biāo)子集之間會(huì)有較大的偏差，進(jìn)而影響算法性能。

表3 NSGA-Ⅱ算法及MT-MaOEA算法采用不同降維算子的平均IGD值

3.3 對(duì)比實(shí)驗(yàn)結(jié)果與分析

表4和表5分別給出了5種算法在3組測(cè)試函數(shù)上經(jīng)過(guò)30次獨(dú)立運(yùn)行產(chǎn)生的平均結(jié)果。其中，括號(hào)中的數(shù)值為5種算法針對(duì)同一測(cè)試函數(shù)時(shí)的表現(xiàn)排序值；排序值越小，則表明算法性能越好。

表4 算法針對(duì)不同測(cè)試問(wèn)題的平均IGD值

根據(jù)表4可知，針對(duì)每組測(cè)試函數(shù)，當(dāng)目標(biāo)空間維數(shù)增大時(shí)，所有算法的IGD性能均呈現(xiàn)遞減趨勢(shì)。對(duì)于DTLZ5(I，M)類(lèi)、WFG3(M)及WFG7(M)類(lèi)測(cè)試問(wèn)題，MT-MaOEA在絕大多數(shù)測(cè)試函數(shù)上均取得了最優(yōu)IGD結(jié)果，這驗(yàn)證了筆者所提算法在處理冗余問(wèn)題時(shí)的有效性。對(duì)于DTLZ2(M)類(lèi)測(cè)試問(wèn)題，MT-MaOEA在DTLZ2(3)、DTLZ2(10)以及DTLZ2(15)上均取得了次優(yōu)的IGD結(jié)果，其表現(xiàn)差于NSGA-Ⅲ及MaOEA-IGD。對(duì)于DTLZ3(M)類(lèi)測(cè)試問(wèn)題，MT-MaOEA在DTLZ3(5)上的表現(xiàn)差于NSGA-Ⅲ。對(duì)于DTLZ3(10)及DTLZ3(15)的表現(xiàn)均差于MaOEA-IGD。這是由于DTLZ2(M)及DTLZ3(M)系列問(wèn)題本身為非冗余的測(cè)試問(wèn)題，而筆者所提算法MT-MaOEA的核心設(shè)計(jì)思想是通過(guò)刪除冗余目標(biāo)來(lái)獲取低維任務(wù)，從而提高算法的搜索能力。根據(jù)表4中的統(tǒng)計(jì)結(jié)果，MT-MaOEA算法對(duì)于DTLZ2(M)系列測(cè)試問(wèn)題的性能均要優(yōu)于MT-MaOEA-LPCA，這說(shuō)明了多任務(wù)框架對(duì)于此類(lèi)問(wèn)題依然具有提升算法性能的能力。然而MT-MaOEA算法的核心設(shè)計(jì)思想導(dǎo)致其在處理非冗余問(wèn)題時(shí)的性能要差于某些對(duì)比算法。

表5 算法針對(duì)不同測(cè)試問(wèn)題的平均SP值

根據(jù)表5可知，MT-MaOEA對(duì)于23個(gè)測(cè)試函數(shù)中的13個(gè)函數(shù)取得了最優(yōu)的SP結(jié)果。然而，從表5中的統(tǒng)計(jì)結(jié)果中可以發(fā)現(xiàn)，MT-MaOEA對(duì)每組測(cè)試函數(shù)中的低維測(cè)試問(wèn)題可以取得較好的結(jié)果，對(duì)高維測(cè)試問(wèn)題所獲取到的SP值要差于某些對(duì)比算法。如對(duì)于函數(shù)DTLZ5(7，10)、DTLZ5(6，15)以及DTLZ2(15)，MT-MaOEA的SP性能均要差于NSGA-Ⅲ及MaOEA-IGD。對(duì)于函數(shù)DTLZ3(10)、DTLZ3(15)以及WFG7(10)，MT-MaOEA的SP性能要差于NSGA-Ⅲ。對(duì)于函數(shù)WFG7(15)，MT-MaOEA的SP性能要差于MaOEA-IGD。在NSGA-Ⅲ算法中，算法通過(guò)采取一組預(yù)設(shè)的在目標(biāo)空間均勻分布的參考點(diǎn)來(lái)增加算法優(yōu)化高維問(wèn)題時(shí)的多樣性保持能力。在MaOEA-IGD算法中，通過(guò)采用一種支配比較機(jī)制與鄰近距離分配相結(jié)合的選擇策略來(lái)達(dá)到算法在優(yōu)化高維問(wèn)題時(shí)收斂性與多樣性之間的平衡。在所提算法MT-MaOEA中，算法通過(guò)兩任務(wù)之間的信息交流以及在REP中設(shè)置aging屬性進(jìn)行變異來(lái)增加種群的多樣性。在目標(biāo)空間維數(shù)較高時(shí)，所提策略的有效性會(huì)有所降低。因此導(dǎo)致算法在處理某些高維問(wèn)題時(shí)的SP性能差于一些對(duì)比算法。

表6中給出了算法分別對(duì)于IGD指標(biāo)以及SP指標(biāo)的平均排序結(jié)果。由表6可知，筆者所提MT-MaOEA算法在IGD指標(biāo)及SP指標(biāo)上均取得了最優(yōu)排序結(jié)果。根據(jù)Friedman檢驗(yàn)可計(jì)算出5類(lèi)算法在23組測(cè)試函數(shù)上針對(duì)IGD指標(biāo)及SP指標(biāo)的統(tǒng)計(jì)值(FF)分別為28.27及13.50。根據(jù)F分布表，F(xiàn)0.1(5-1，(5-1)×(23-1))=2.01。由于5類(lèi)算法在23組測(cè)試函數(shù)上針對(duì)IGD指標(biāo)及SP指標(biāo)的統(tǒng)計(jì)值均大于F0.1(5-1，(5-1)×(23-1))，因此可以認(rèn)為5類(lèi)算法在90%置信度上具有明顯差異。由表6可知，筆者所提MT-MaOEA算法在IGD指標(biāo)及SP指標(biāo)上均取得了最優(yōu)排序結(jié)果。Friedman檢驗(yàn)的結(jié)果說(shuō)明了所提算法的有效性。為了進(jìn)一步對(duì)5類(lèi)算法進(jìn)行兩兩比較，采用了雙邊Nemenyi檢驗(yàn)方法。根據(jù)雙邊Nemenyi檢驗(yàn)可計(jì)算得出90%置信度上的臨界值為1.15。根據(jù)表6可知，針對(duì)IGD指標(biāo)及SP指標(biāo)所提算法與MaOEA-IGD、NSGA-Ⅱ-LPCA 及MT-MaOEA-LPCA之間的排序值之差均明顯大于1.15。因此可以認(rèn)為所提算法在IGD指標(biāo)及SP指標(biāo)上的表現(xiàn)明顯優(yōu)于MaOEA-IGD、NSGA-Ⅱ-LPCA 及MT-MaOEA-LPCA。

表6 算法平均排序值

圖2展示了MT-MaOEA對(duì)于函數(shù)DTLZ5(3，5)及DTLZ5(6，15)隨算法運(yùn)行的IGD結(jié)果。由圖2可以看出，MT-MaOEA所采用的多任務(wù)框架使得算法可以借助低維任務(wù)來(lái)提高其搜索能力。此外，任務(wù)間交流算子可以避免算法在優(yōu)化單一任務(wù)時(shí)陷入局部最優(yōu)，同時(shí)增加種群的多樣性。

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

針對(duì)傳統(tǒng)進(jìn)化算法在優(yōu)化高維多目標(biāo)問(wèn)題時(shí)搜索能力驟降的問(wèn)題，筆者提出了一種多任務(wù)機(jī)制驅(qū)動(dòng)的高維多目標(biāo)進(jìn)化算法(MT-MaOEA)。該算法采用多任務(wù)框架，同時(shí)優(yōu)化原始高維任務(wù)及所構(gòu)造出的低維任務(wù)，以達(dá)到利用低維任務(wù)提高算法搜索能力，同時(shí)避免降維過(guò)程中有用信息丟失的目的。對(duì)比實(shí)驗(yàn)結(jié)果表明，所采用的多任務(wù)機(jī)制確實(shí)可以提高算法在處理高維問(wèn)題時(shí)的優(yōu)化能力。并且MT-MaOEA與其他對(duì)比算法相比也展現(xiàn)出了較強(qiáng)的競(jìng)爭(zhēng)性。但通過(guò)對(duì)實(shí)驗(yàn)結(jié)果進(jìn)行分析發(fā)現(xiàn)，MT-MaOEA在如下兩方面仍存在一些不足：一方面，MT-MaOEA的核心設(shè)計(jì)思想是通過(guò)刪除冗余目標(biāo)來(lái)獲取低維任務(wù)，從而提高算法的搜索能力。這就導(dǎo)致算法在處理一些不包含冗余目標(biāo)的高維優(yōu)化問(wèn)題時(shí)具有一定的局限性；另一方面，MT-MaOEA中，算法通過(guò)兩任務(wù)之間的信息交流以及在REP中設(shè)置aging屬性進(jìn)行變異來(lái)增加種群的多樣性。所提策略在目標(biāo)空間維數(shù)相對(duì)較低時(shí)，可以很好地保持種群多樣性。但隨著目標(biāo)維數(shù)的增加，該策略的多樣性保持能力有所降低。因此，如何在多任務(wù)框架中利用一些參考信息(如參考點(diǎn)、參考向量等)提高算法在高維優(yōu)化環(huán)境中的多樣性保持能力是未來(lái)的一個(gè)研究方向。