金 濤，朱 莉，李 豪，汪小豪，姜成龍

(湖北工業(yè)大學電氣與電子工程學院，湖北 武漢 430068)

高維多目標優(yōu)化問題是使多個目標在一定條件下盡可能同時達到最佳解的問題，廣泛應用于科學研究、金融科技、工程設計的領域，如物資調用、人才分配、工藝設計、生產調度等[1-2]，具有重要的科研和實際價值[3]。隨著目標個數(shù)的增加，傳統(tǒng)的多目標優(yōu)化算法無法很好的處理高維多目標優(yōu)化問題，于是人們在傳統(tǒng)的算法上進行改進和提升。基于t-SNE的高維多目標優(yōu)化算法(t-SNE-NSGAⅡ)對目標集進行分析處理，丟棄冗余目標，減少目標維度，降低計算的復雜度，提高算法的收斂性。但其在處理冗余目標集方面，只作簡單的刪除，使目標集中部分有用的屬性可能被丟棄，導致算法的精確度降低。因此利用加權和來擬合冗余目標集，進一步優(yōu)化初始種群和冗余目標，從而提高算法的準確性。

1 問題分析

雖然t-SNE-NSGAⅡ算法降低了計算的復雜度，提高算法的收斂性，但是t-SNE-NSGAⅡ算法在簡化目標集時，損失目標集中有意義的部分屬性，導致算法準確性降低。因為在執(zhí)行t-SNE算法后，對得到的非冗余目標集都直接進行下一次的重新初始化種群操作，導致上次算法中得到的Pareto解集優(yōu)秀的個體沒有保留。這些被舍棄的冗余目標集中存在能夠反映目標集的部分屬性的優(yōu)秀個體，并且這些優(yōu)秀個體能夠引導初始化種群的方向，加快算法的收斂速度。

針對t-SNE-NSGAⅡ的不足，提出一種基于t-SNE加權和的高維多目標優(yōu)化算法(t-distributed stochastic neighbor embedding-weighted sum-non-dominated sorting genetic algorithm with elite strategy，t-SNESUM-NSGAⅡ)，該算法在每次執(zhí)行t-SNE算法后，不是直接對種群初始化，而是把經過t-SNE算法處理而舍去的所有冗余的目標集擬合成一個新的目標集，再把擬合好的目標集加入t-SNE算法得到的目標集中，最后初始化種群，這樣就保留了種群中部分優(yōu)秀的個體解。因此，t-SNESUM-NSGAⅡ算法既提高了初始種群的質量，也保留了部分種群中目標屬性，提高算法的準確性，加快了算法收斂速度。

2 相關工作

按照問題對象的不同，高維多目標優(yōu)化算法大致可以分為：不含冗余目標問題的算法和含冗余目標問題的算法[4]。第一類算法，是針對不含冗余目標問題的算法，該類算法主要可以從基于松弛Pareto排序方法[5]、基于聚合或分解將多目標整合為單目標問題的方法[6]和基于評價指標的方法[7]三種不同的角度來解決不含冗余目標的問題。第二類算法是針對含冗余目標問題的算法，該類算法主要可以從基于目標間互相關系的目標縮減的方法[8]與基于保持Pareto支配關系的目標縮減[9]的方法兩種不同的角度來解決含冗余目標的問題。

隨著組成問題的目標個數(shù)大幅度增加，高維多目標優(yōu)化問題變得越來越復雜。不含冗余目標問題的算法，在處理多維目標時，算法搜索能力不足、計算復雜度增加，可視化難度變得越發(fā)明顯。含冗余目標問題的算法，能夠充分挖掘目標之間的相關性，簡化目標集的個數(shù)，從而降低目標集的復雜度，獲得了更廣泛的應用。其中,“基于保持Pareto支配關系的目標縮減方法”雖然能夠簡化目標集，但計算目標集中非支配解集之間的支配關系會增加計算復雜度和計算機設備性能負擔。

基于t-SNE的高維多目標優(yōu)化算法主要從基于目標之間關系的目標方法的角度研究，引入t-隨機鄰近嵌入(t-SNE)算法來減少高維多目標中存在的目標冗余問題。先通過仿射變換將數(shù)據(jù)點映射到概率分布上，使高維數(shù)據(jù)空間和低維數(shù)據(jù)空間的條件概率差別最小，讓數(shù)據(jù)點從高維空間嵌入到低維空間中，相似度較高的距離較近，而相似度較低的距離較遠。然后用KL散度函數(shù)作為目標函數(shù)來評估嵌入效果的優(yōu)劣，最后用梯度下降法來最小化目標函數(shù)，最終得到收斂的結果。

然而t-SNE-NSGAⅡ算法處理冗余目標集的方式較為粗糙，直接刪除冗余目標集可能導致部分有用的屬性被丟棄。因此，將冗余目標通過加權和擬合成新的目標集，從而保留目標集中的特征，增強了算法的收斂性，提高了算法的準確性。

3 算法設計

3.1 新目標的擬合

在t-SNE-NSGAⅡ算法中，每次執(zhí)行t-SNE算法后，得到的目標集中剔除了冗余目標(圖1)。

圖 1 f1(x)、f2(x)、f3(x)關系分布

圖1中f2(x)和f3(x)比f1(x)和f2(x)、f1(x)和f3(x)更為相似，那么通過t-SNE算法計算后，f2(x)和f3(x)的相似度更高，是一對冗余目標，丟棄了f3(x)。f1(x)和其它目標相似度最低，保留下來。

經過t-SNE算法丟棄的冗余目標，只和非冗余目標相似，并不是完全一致。在現(xiàn)實研究、工程問題中，不會存在完全的冗余關系，如果丟棄一個相似的目標，對測試的結果會產生一定的影響。因此，在t-SNESUM-NSGAⅡ算法中，考慮每次經過t-SNE算法中直接丟棄的目標，將這些被丟棄的冗余目標進行加權和，重新擬合成一個新的目標。因為每次t-SNE算法丟棄的目標與保留下來的非冗余目標具有很高的相似度，所以改進后的算法采用平均加權的方式來擬合一個新的目標。設丟棄了n個目標，則擬合后的新目標按照向量{1/n,1/n,…,1/n}進行加權求和。

3.2 t-SNESUM-NSGAⅡ算法流程

傳統(tǒng)的t-SNE-NSGAⅡ算法主要的流程為NSGA-Ⅱ→t-SNE→NSGA-Ⅱ→t-SNE這樣的循環(huán)過程，每次進行t-SNE算法后都丟棄了冗余目標。t-SNESUM-NSGAⅡ算法對t-SNE-NSGAⅡ進行改進，每次t-SNE算法丟棄冗余目標時，對冗余目標集進行加權求和，擬合成新的目標集并參與NSGA-Ⅱ的優(yōu)化，具體的算法流程見圖2。

圖 2 t-SNESUM-NSGAⅡ算法流程框圖

首先，選取原始的目標集I0，對目標集初始化種群，然后執(zhí)行NSGA-Ⅱ算法優(yōu)化種群，組成新的父代種群P0；再對P0進行t-SNE算法優(yōu)化，得到冗余目標集和非冗余目標集，對冗余目標集進行加權求和，擬合成新的目標集，與非冗余目標集合并成重組目標集；最后重復上述步驟，直到滿足設置的最大迭代次數(shù)，得到種群P2,P3,…,Pt-2,Pt-1，Pt和目標集I3,…,It，It+1，當It=It+1，求出目標集的 Pareto最優(yōu)解Pt。t-SNESUM-NSGAⅡ算法具體步驟見表1。

表1 t-SNESUM-NSGAⅡ算法

4 實驗設計與結果分析

4.1 測試函數(shù)

目前，通常選用DTLZ系列測試函數(shù)作為高維多目標優(yōu)化算法領域的測試函數(shù)，其中包括DTLZ1-DTLZ7。DTLZ系列測試函數(shù)一般可以分為含冗余目標的測試函數(shù)和不含冗余目標的測試函數(shù)。對于第一種測試函數(shù)，選擇DTLZ2用來測試算法能否降低不含冗余目標集的目標個數(shù)。對于第二種測試函數(shù)，選擇DTLZ5用來測試算法對簡化目標的可行性。

4.2 測試指標

多目標優(yōu)化算法中有多種性能評價指標：1)收斂性：評價解集與真正的Pareto最優(yōu)面的趨近程度，具體的評測指標有世代距離(Generational Distance, GD)；2)分布性：評價解集的多樣性和均勻分布程度，具體的評測指標有空間評價方法(spacing metric，spacing)、空間分布度(diversity metric, DM)、覆蓋率指標(set coverage, CS)；3)綜合性能：綜合考慮解集的收斂性和分布性，具體的評測指標有逆世代距離(Inverted Generational Distance, IGD)、超體積指標(Hyper Volume, HV)。分別選用世代距離(GD)和空間分布度(DM)來測試t-SNESUM-NSGAⅡ算法準確性和收斂性的優(yōu)劣。

世代距離評價GD指的是解集P中的每一個點到參考集P′中的平均最小距離，表示偏離真正最優(yōu)邊界的程度。GD的值越大，偏離真正最優(yōu)邊界越遠，收斂性就越差。

空間分布度DM表示所獲得解集的廣泛程度，DM值越小，說明解集越均勻。

4.3 實驗參數(shù)設置

實驗使用的硬件環(huán)境為Intel Xeon(R)CPU ES-2620 v4 @ 2.10GHz，Nvidia Quadro M4000 GPU，運行內存為32G。實驗在Matlab仿真上實現(xiàn)。為了測試在不同目標個數(shù)下，算法性能的好壞，分別設置測試函數(shù)中目標個數(shù)為3，5，10。DTLZ(I,M)表示目標在I維上的空間分布情況，I為目標維度，M為目標對象個數(shù)。具體參數(shù)如表2所示。

表2 實驗設置參數(shù)

4.4 實驗分析

采用DTLZ2和DTLZ5測試函數(shù)，在12維度時，分別選取目標集的個數(shù)為3、5、10，采用NSGA-Ⅱ算法、t-SNE-NSGAⅡ算法、t-SNESUM-NSGAⅡ算法實驗測試結果，通過實驗結果對比驗證t-SNESUM-NSGAⅡ算法的收斂性、準確性。

4.4.1DTLZ2(12,3)實驗結果與分析采取DTLZ2函數(shù)進行對比實驗，選取3個目標，算法運行后的目標集與原來的目標集相同，DTLZ2(12,3)的Pareto前沿見圖3。說明t-SNESUM-NSGAⅡ算法和t-SNE-NSGAⅡ算法一樣不能對不存在冗余目標的目標集進行目標降維。

圖 3 DTLZ5(12,3)的 Pareto 前沿圖

4.4.2DTLZ5(12,3)實驗結果與分析采取DTLZ5函數(shù)進行對比實驗，選取3個目標，迭代次數(shù)為10000，分別運行NSGA-Ⅱ算法、t-SNE-NSGAⅡ算法和t-SNESUM-NSGAⅡ算法，得到DTLZ5(12,3)實驗結果見圖4。從圖4可以看出 t-SNESUM-NSGAⅡ算法和t-SNE-NSGAⅡ算法都具有將目標降至2維的能力。

圖 4 DTLZ5(12,3)實驗結果圖

對DTLZ5(12,3)函數(shù)分別用NSGA-Ⅱ算法、t-SNE-NSGAⅡ算法、t-SNESUM-NSGAⅡ算法進行測試，獨立運行10次，測試指標取GD和DM，實驗結果見表3。

表3 DTLZ5(12,3)測試指標性能比較

由表3中的數(shù)據(jù)可知，t-SNESUM-NSGAⅡ算法的 GD 和 DM 兩個指標的分別為：6.1831E-05，0.5699；t-SNE-NSGAⅡ算法的 GD 和 DM 兩個指標的分別為：1.3510E-04，0.4013。由于t-SNESUM-NSGAⅡ算法的GD比t-SNE-NSGAⅡ算法和NSGA-Ⅱ算法GD都小，表示t-SNESUM-NSGAⅡ算法偏離真正最優(yōu)邊界最小，收斂性最好；而t-SNESUM-NSGAⅡ算法DM比NSGA-Ⅱ算法小，但是大于t-SNE-NSGAⅡ算法的DM，表示t-SNESUM-NSGAⅡ算法的解集廣泛程度介于兩個算法之間。

綜上所述，t-SNESUM-NSGAⅡ算法收斂度比NSGA-Ⅱ算法和t-SNE-NSGAⅡ算法更好，解集分布度相對NSGA-Ⅱ算法提高了，但是對于t-SNE-NSGAⅡ算法來說卻降低了。t-SNESUM-NSGAⅡ算法收斂速度得到了加強，但是在解集的分布來說反而降低了，這說明t-SNESUM-NSGAⅡ算法雖然得到的解集具有更好的分布度，但是在目標集低的時候解集分布度還是低于t-SNE-NSGAⅡ算法，猜想當目標個數(shù)較低時，t-SNESUM-NSGAⅡ算法優(yōu)勢不夠明顯。

4.4.3DTLZ5(12,5)實驗結果與分析采取DTLZ5函數(shù)進行對比實驗，選取5個目標個數(shù)，分別運行t-SNE-NSGAⅡ算法和t-SNESUM-NSGAⅡ算法，得到的DTLZ5(12,5)收斂速度見圖5。由上面的結論可以知道，t-SNE-NSGAⅡ算法和t-SNESUM-NSGAⅡ算法都可以把目標降至2維，但從圖5可以看出，t-SNE-NSGAⅡ算法大概在迭代次數(shù)為6800代左右時完全收斂，而t-SNESUM-NSGAⅡ算法在6400代左右就可以完全收斂，這說明t-SNESUM-NSGAⅡ算法的收斂速度優(yōu)于t-SNE-NSGAⅡ算法的收斂速度。

圖 5 DTLZ5(12,5)收斂速度圖

對DTLZ5(12,5)函數(shù)分別用NSGA-Ⅱ算法、t-SNE-NSGAⅡ算法、t-SNESUM-NSGAⅡ算法，獨立運行10次，測試指標取GD和DM，實驗結果見表4。

表4 DTLZ5(12,5)測試指標性能比較

由表4數(shù)據(jù)可知，t-SNESUM-NSGAⅡ算法的 GD 和 DM 兩個指標分別為：1.6389E-03，0.3519；t-SNE-NSGAⅡ算法的 GD 和 DM 兩個指標的分別為：2.6509E-05，0.33982。由于t-SNESUM-NSGAⅡ算法的GD比NSGA-Ⅱ算法和t-SNE-NSGAⅡ算法的GD都小，表示t-SNESUM-NSGAⅡ算法偏離真正最優(yōu)邊界最小，收斂性最好；t-SNESUM-NSGAⅡ算法DM比NSGA-Ⅱ算法和t-SNE-NSGAⅡ算法的DM也都小，表示t-SNE-NSGAⅡ算法的解集廣泛程度最小。

因此，t-SNESUM-NSGAⅡ算法收斂度比NSGA-Ⅱ算法和t-SNE-NSGAⅡ算法更好，解集分布度相對NSGA-Ⅱ算法提高了，但是對于t-SNE-NSGAⅡ算法來說仍然沒有提升。t-SNESUM-NSGAⅡ算法在收斂速度得到加強，但是在解集的分布來說反而降低了，這說明t-SNESUM-NSGAⅡ算法雖然得到的解集具有更好的分布度，但是在目標集低的時候解集分布度還是低于t-SNE-NSGAⅡ算法。

4.4.4DTLZ5(12,10)實驗結果與分析采取DTLZ5函數(shù)進行對比實驗，選取10個目標個數(shù)，迭代次數(shù)為10000次，分別運行t-SNE-NSGAⅡ算法和t-SNESUM-NSGAⅡ算法，得到的DTLZ5(12,10)空間分布見圖6，從圖可以看出t-SNESUM-NSGAⅡ算法性能明顯優(yōu)于t-SNE-NSGAⅡ算法。

圖 6 DTLZ5(12,10)空間分布圖

對DTLZ5(12,10)函數(shù)分別用NSGA-Ⅱ算法、t-SNE-NSGAⅡ算法、t-SNESUM-NSGAⅡ算法進行測試，獨立運行10次，測試指標取GD和DM，實驗結果見表5。

表5 DTLZ5(12,10)測試指標性能比較

由表5中的數(shù)據(jù)可知，t-SNESUM-NSGAⅡ算法的 GD 和 DM 兩個指標分別為：7.2521E-06，0.2137；t-SNE-NSGAⅡ算法的 GD 和 DM 兩個指標分別為：1.7509E-04，0.2963。由于t-SNE-NSGAⅡ算法的GD比NSGA-Ⅱ算法和t-SNE-NSGAⅡ算法的GD都小，表示t-SNESUM-NSGAⅡ算法偏離真正最優(yōu)邊界最小，收斂性最好；t-SNESUM-NSGAⅡ算法的DM比NSGA-Ⅱ算法和t-SNE-NSGAⅡ算法的DM也都小，表示t-SNE-NSGAⅡ算法的解集廣泛程度最小。

綜上所述，t-SNESUM-NSGAⅡ算法無論是收斂到最優(yōu)邊界能力還是解集分布度都明顯優(yōu)于t-SNE-NSGAⅡ算法，驗證了隨著目標個數(shù)的增加，t-SNESUM-NSGAⅡ算法性能比t-SNE-NSGAⅡ算法的更好。

5 結論

t-SNESUM-NSGAⅡ算法在t-SNE-NSGAⅡ算法的基礎上進行改進，進一步優(yōu)化初始種群和冗余目標，提高了算法的準確性。該算法重點在t-SNE分析處理得到的冗余目標集進行擬合形成了新的目標集，并加入下一步的運算中；而且在每次初始化種群的時候，保留父代種群的部分個體。雖然t-SNESUM-NSGAⅡ算法中采用對冗余目標集直接加權和，擬合成新的目標，這樣雖然可以保留目標集的部分屬性，但大部分屬性仍舊丟失。因此在面對冗余目標集時候，如何選擇一個好的擬合方法，怎樣分配擬合后各個目標集間的權重，來充分挖掘目標集的特征，降低目標維度，還有待進一步研究。