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

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

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

1 問題分析

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

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

2 相關(guān)工作

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

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

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

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

3 算法設(shè)計

3.1 新目標的擬合

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

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

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

經(jīng)過t-SNE算法丟棄的冗余目標，只和非冗余目標相似，并不是完全一致。在現(xiàn)實研究、工程問題中，不會存在完全的冗余關(guān)系，如果丟棄一個相似的目標，對測試的結(jié)果會產(chǎn)生一定的影響。因此，在t-SNESUM-NSGAⅡ算法中，考慮每次經(jīng)過t-SNE算法中直接丟棄的目標，將這些被丟棄的冗余目標進行加權(quán)和，重新擬合成一個新的目標。因為每次t-SNE算法丟棄的目標與保留下來的非冗余目標具有很高的相似度，所以改進后的算法采用平均加權(quán)的方式來擬合一個新的目標。設(shè)丟棄了n個目標，則擬合后的新目標按照向量{1/n,1/n,…,1/n}進行加權(quá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算法丟棄冗余目標時，對冗余目標集進行加權(quán)求和，擬合成新的目標集并參與NSGA-Ⅱ的優(yōu)化，具體的算法流程見圖2。

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

首先，選取原始的目標集I0，對目標集初始化種群，然后執(zhí)行NSGA-Ⅱ算法優(yōu)化種群，組成新的父代種群P0；再對P0進行t-SNE算法優(yōu)化，得到冗余目標集和非冗余目標集，對冗余目標集進行加權(quán)求和，擬合成新的目標集，與非冗余目標集合并成重組目標集；最后重復上述步驟，直到滿足設(shè)置的最大迭代次數(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 實驗設(shè)計與結(jié)果分析

4.1 測試函數(shù)

目前，通常選用DTLZ系列測試函數(shù)作為高維多目標優(yōu)化算法領(lǐng)域的測試函數(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ù)設(shè)置

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

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

4.4 實驗分析

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

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

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

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

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

對DTLZ5(12,3)函數(shù)分別用NSGA-Ⅱ算法、t-SNE-NSGAⅡ算法、t-SNESUM-NSGAⅡ算法進行測試，獨立運行10次，測試指標取GD和DM，實驗結(jié)果見表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)實驗結(jié)果與分析采取DTLZ5函數(shù)進行對比實驗，選取5個目標個數(shù)，分別運行t-SNE-NSGAⅡ算法和t-SNESUM-NSGAⅡ算法，得到的DTLZ5(12,5)收斂速度見圖5。由上面的結(jié)論可以知道，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，實驗結(jié)果見表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)實驗結(jié)果與分析采取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，實驗結(jié)果見表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 結(jié)論

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