多任務機制驅動的高維多目標進化算法

劉天宇，曹 磊

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

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

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

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

文中的主要工作如下：

(1) 提出了一種基于多任務框架的高維目標進化算法。在該算法中，個體種群同時優化原始高維任務以及利用降維算法獲得的低維任務。

(2) 采用一種自適應降維算子在算法運行過程中獲取所需的低維任務，該算子對基于相關性分析及基于Pareto支配關系的降維方法進行了有機結合。

(3) 采用任務間交流算子在實現兩任務間信息交流的同時，完成種群的更新以及對種群中個體的任務分配。

1 高維目標優化問題描述

高維目標優化問題(MaOPs)是由多目標優化問題(Multi-objective Optimization Problems，MOPs)擴展而來的，具體是指具有3個以上優化目標的多目標優化問題。對于MOPs和MaOPs，不存在一個解可以同時最優化所有的優化目標。因此多目標優化算法的目的在于可以找到能夠在多個目標間進行平衡的一組解[24]。

以最小化問題為例，一個MaOP問題可抽象為如下形式：

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

(1)

其中，x為n維搜索空間中的一個解(決策向量)；m為目標空間的維數，對于MaOPs，m>3。

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

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

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

不沖突：兩個目標函數fi∈F0和fj∈F0被稱作是不沖突的，當且僅當對 ?u，v∈PF0都滿足如下公式：

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

(2)

2 多任務機制驅動的高維多目標進化算法(MT-MaOEA)設計

2.1 MT-MaOEA框架

圖1為MT-MaOEA基本框架。由圖1可以看出，MT-MaOEA中個體種群同時優化兩個任務：原始的高維優化任務及經過自適應目標降維算子后獲得的低維任務。

兩任務間通過任務間的交流來使算法能夠利用低維任務提高搜索能力的同時，也可以避免降維算法帶來的信息丟失風險。MT-MaOEA具體步驟如下：

步驟1 從原始目標集合中隨機選擇得出目標子集，以此構造低維任務。

步驟2 設定種群中優化兩個任務的個數數目均為n，則種群規模為2×n。

步驟3 初始化種群POP并獲取當前Pareto最優解集REP，從POP中隨機選擇一半個體優化原始高維任務，其余個體優化低維任務。

步驟4 判斷是否滿足終止條件；若滿足，則輸出當前Pareto最優解集；否則，至步驟4。

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

步驟6 若mod(g，G)=0(g為算法當前運行代數，G為設定的參數)，則利用自適應目標降維算子獲取新的目標子集來構造低維任務，并跳轉至步驟3。

綜上所述，MT-MaOEA設計的關鍵在于自適應目標降維算子以及任務間交流算子的設計。

2.2 自適應目標降維算子

對于MaOPs問題，目前現有的目標降維方法主要可以分為兩大類：基于相關性分析及基于Pareto支配關系的目標降維方法[17]。其中，基于相關性分析的降維方法是對整個解種群進行分析，不單獨考慮兩個解個體之間的關系。因此對于算法在運行初期所獲得的不能很好地反映理想PF的Pareto最優解集，基于相關性分析的降維方法具有較強的魯棒性。基于Pareto支配關系的降維方法通過分析每一對解個體之間的Pareto支配關系來對目標空間進行降維。因此該類方法在算法獲得的Pareto最優解集能夠反映理想PF時，可以很好地獲得所需的目標子集。然而在算法運行前期，算法獲得的Pareto最優解集與理想Pareto最優解集相比都會有相對較大的偏差。因此基于Pareto支配關系的降維方法可能無法準確獲得所需的目標子集。

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

(3)

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

(4)

其中，X為當前函數評價次數，Y為最大函數評價次數。

2.3 任務間交流算子

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

xm=x+F(x1-x2) ，

(5)

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

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

步驟1 設置i=1，子代種群CPOP=?；

步驟2 判斷i≤|POP|是否滿足，若滿足則繼續后續步驟，否則結束運行；

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

步驟4 設定交叉概率pc=0.5(1+rand (0，1) )，若在[0，1]區間內的隨機數r小于pc，則轉至步驟5；否則，轉至步驟7；

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

步驟6 對于產生的子代個體C1與C2，隨機分配其task_id，并將C1與C2加入CPOP中；

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

步驟8 令TPOP=POP∪CPOP；

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

步驟10 產生下一代種群POP=POP1∪POP2；

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

2.4 算法時間復雜度分析

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

令MT-MaOEA種群規模為N，目標空間維數為M(M

3 實驗分析

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

筆者選擇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作為降維算子)作為對比算法來驗證所提算法的有效性。對于所有算法，設置其最大函數評價次數為30 000。選擇逆世代距離(Inverted Generational Distance，IGD)[15]及分布指標(SPacing，SP)[29]作為評價算法性能的量化指標。IGD值越小，則表明算法搜到的Pareto前沿面與真實的Pareto前沿面越接近；SP值越小，則說明Pareto前沿面的分布越均勻。表1為算法的具體參數設置。

表1 算法的參數設置

3.1 參數分析

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

表2 MT-MaOEA針對不同G的平均IGD值

3.2 自適應降維算子的有效性分析

算法MT-MaOEA中采用一種自適應降維算子來對目標空間進行降維，從而獲取所需的低維任務。該算子將兩種經典的降維方法LPCA與k-EMOSS進行了有機結合。為了分析自適應降維算子的有效性，本節選擇NSGA-Ⅱ-LPCA、NSGA-Ⅱ-k-EMOSS、MT-MaOEA-LPCA以及MT-MaOEA-k-EMOSS作為對比算法。其中NSGA-Ⅱ-LPCA與NSGA-Ⅱ-k-EMOSS在NSGA-Ⅱ算法基礎上，分別采用了LPCA與k-EMOSS進行目標降維操作。同樣，MT-MaOEA-LPCA與MT-MaOEA-k-EMOSS在MT-MaOEA算法基礎上分別采用了LPCA與k-EMOSS進行目標降維操作。

表3展示了5種算法針對不同測試函數通過30次獨立運行產生的平均IGD值。由表3可知，MT-MaOEA算法在幾乎全部測試函數上都獲得了最優IGD值。實驗結果驗證了所提算法的有效性。根據表3中的統計結果可知，對于算法NSGA-Ⅱ及MT-MaOEA，在大多數測試函數上采用LPCA方法的效果要優于k-EMOSS方法。這是由于k-EMOSS方法對于用來降維的解種群的質量要求較高，在解種群不能較好地覆蓋真實的Pareto前沿面時，k-EMOSS方法所獲得的目標子集與理想目標子集之間會有較大的偏差，進而影響算法性能。

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

3.3 對比實驗結果與分析

表4和表5分別給出了5種算法在3組測試函數上經過30次獨立運行產生的平均結果。其中，括號中的數值為5種算法針對同一測試函數時的表現排序值；排序值越小，則表明算法性能越好。

表4 算法針對不同測試問題的平均IGD值

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

表5 算法針對不同測試問題的平均SP值

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

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

表6 算法平均排序值

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

4 結束語

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