基于t-SNE加權(quán)和的高維多目標(biāo)優(yōu)化算法

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

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

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

1 問(wèn)題分析

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

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

2 相關(guān)工作

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

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

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

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

3 算法設(shè)計(jì)

3.1 新目標(biāo)的擬合

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

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

圖1中f2(x)和f3(x)比f(wàn)1(x)和f2(x)、f1(x)和f3(x)更為相似，那么通過(guò)t-SNE算法計(jì)算后，f2(x)和f3(x)的相似度更高，是一對(duì)冗余目標(biāo)，丟棄了f3(x)。f1(x)和其它目標(biāo)相似度最低，保留下來(lái)。

經(jīng)過(guò)t-SNE算法丟棄的冗余目標(biāo)，只和非冗余目標(biāo)相似，并不是完全一致。在現(xiàn)實(shí)研究、工程問(wèn)題中，不會(huì)存在完全的冗余關(guān)系，如果丟棄一個(gè)相似的目標(biāo)，對(duì)測(cè)試的結(jié)果會(huì)產(chǎn)生一定的影響。因此，在t-SNESUM-NSGAⅡ算法中，考慮每次經(jīng)過(guò)t-SNE算法中直接丟棄的目標(biāo)，將這些被丟棄的冗余目標(biāo)進(jìn)行加權(quán)和，重新擬合成一個(gè)新的目標(biāo)。因?yàn)槊看蝨-SNE算法丟棄的目標(biāo)與保留下來(lái)的非冗余目標(biāo)具有很高的相似度，所以改進(jìn)后的算法采用平均加權(quán)的方式來(lái)擬合一個(gè)新的目標(biāo)。設(shè)丟棄了n個(gè)目標(biāo)，則擬合后的新目標(biāo)按照向量{1/n,1/n,…,1/n}進(jìn)行加權(quán)求和。

3.2 t-SNESUM-NSGAⅡ算法流程

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

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

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

表1 t-SNESUM-NSGAⅡ算法

4 實(shí)驗(yàn)設(shè)計(jì)與結(jié)果分析

4.1 測(cè)試函數(shù)

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

4.2 測(cè)試指標(biāo)

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

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

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

4.3 實(shí)驗(yàn)參數(shù)設(shè)置

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

表2 實(shí)驗(yàn)設(shè)置參數(shù)

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

采用DTLZ2和DTLZ5測(cè)試函數(shù)，在12維度時(shí)，分別選取目標(biāo)集的個(gè)數(shù)為3、5、10，采用NSGA-Ⅱ算法、t-SNE-NSGAⅡ算法、t-SNESUM-NSGAⅡ算法實(shí)驗(yàn)測(cè)試結(jié)果，通過(guò)實(shí)驗(yàn)結(jié)果對(duì)比驗(yàn)證t-SNESUM-NSGAⅡ算法的收斂性、準(zhǔn)確性。

4.4.1DTLZ2(12,3)實(shí)驗(yàn)結(jié)果與分析采取DTLZ2函數(shù)進(jìn)行對(duì)比實(shí)驗(yàn)，選取3個(gè)目標(biāo)，算法運(yùn)行后的目標(biāo)集與原來(lái)的目標(biāo)集相同，DTLZ2(12,3)的Pareto前沿見(jiàn)圖3。說(shuō)明t-SNESUM-NSGAⅡ算法和t-SNE-NSGAⅡ算法一樣不能對(duì)不存在冗余目標(biāo)的目標(biāo)集進(jìn)行目標(biāo)降維。

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

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

圖 4 DTLZ5(12,3)實(shí)驗(yàn)結(jié)果圖

對(duì)DTLZ5(12,3)函數(shù)分別用NSGA-Ⅱ算法、t-SNE-NSGAⅡ算法、t-SNESUM-NSGAⅡ算法進(jìn)行測(cè)試，獨(dú)立運(yùn)行10次，測(cè)試指標(biāo)取GD和DM，實(shí)驗(yàn)結(jié)果見(jiàn)表3。

表3 DTLZ5(12,3)測(cè)試指標(biāo)性能比較

由表3中的數(shù)據(jù)可知，t-SNESUM-NSGAⅡ算法的 GD 和 DM 兩個(gè)指標(biāo)的分別為：6.1831E-05，0.5699；t-SNE-NSGAⅡ算法的 GD 和 DM 兩個(gè)指標(biāo)的分別為：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Ⅱ算法的解集廣泛程度介于兩個(gè)算法之間。

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

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

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

對(duì)DTLZ5(12,5)函數(shù)分別用NSGA-Ⅱ算法、t-SNE-NSGAⅡ算法、t-SNESUM-NSGAⅡ算法，獨(dú)立運(yùn)行10次，測(cè)試指標(biāo)取GD和DM，實(shí)驗(yàn)結(jié)果見(jiàn)表4。

表4 DTLZ5(12,5)測(cè)試指標(biāo)性能比較

由表4數(shù)據(jù)可知，t-SNESUM-NSGAⅡ算法的 GD 和 DM 兩個(gè)指標(biāo)分別為：1.6389E-03，0.3519；t-SNE-NSGAⅡ算法的 GD 和 DM 兩個(gè)指標(biāo)的分別為：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Ⅱ算法更好，解集分布度相對(duì)NSGA-Ⅱ算法提高了，但是對(duì)于t-SNE-NSGAⅡ算法來(lái)說(shuō)仍然沒(méi)有提升。t-SNESUM-NSGAⅡ算法在收斂速度得到加強(qiáng)，但是在解集的分布來(lái)說(shuō)反而降低了，這說(shuō)明t-SNESUM-NSGAⅡ算法雖然得到的解集具有更好的分布度，但是在目標(biāo)集低的時(shí)候解集分布度還是低于t-SNE-NSGAⅡ算法。

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

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

對(duì)DTLZ5(12,10)函數(shù)分別用NSGA-Ⅱ算法、t-SNE-NSGAⅡ算法、t-SNESUM-NSGAⅡ算法進(jìn)行測(cè)試，獨(dú)立運(yùn)行10次，測(cè)試指標(biāo)取GD和DM，實(shí)驗(yàn)結(jié)果見(jiàn)表5。

表5 DTLZ5(12,10)測(cè)試指標(biāo)性能比較

由表5中的數(shù)據(jù)可知，t-SNESUM-NSGAⅡ算法的 GD 和 DM 兩個(gè)指標(biāo)分別為：7.2521E-06，0.2137；t-SNE-NSGAⅡ算法的 GD 和 DM 兩個(gè)指標(biāo)分別為：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Ⅱ算法無(wú)論是收斂到最優(yōu)邊界能力還是解集分布度都明顯優(yōu)于t-SNE-NSGAⅡ算法，驗(yàn)證了隨著目標(biāo)個(gè)數(shù)的增加，t-SNESUM-NSGAⅡ算法性能比t-SNE-NSGAⅡ算法的更好。

5 結(jié)論

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