交互式Pareto前沿可視化決策*

胡佳鑫，楊樂平

(國防科技大學(xué) 空天科學(xué)學(xué)院， 湖南 長沙 410073)

在高維多目標(biāo)優(yōu)化問題中，目標(biāo)向量構(gòu)成了多目標(biāo)優(yōu)化問題的非劣最優(yōu)目標(biāo)域，稱為Pareto前沿。一般地，各子目標(biāo)之間存在復(fù)雜的沖突性，決策者需要深度發(fā)掘Pareto前沿特性并結(jié)合實際需求作出最終選擇。高維多目標(biāo)可視化技術(shù)將Pareto前沿投影至低維觀測空間，提供用戶直觀有效的決策輔助，廣泛應(yīng)用于數(shù)據(jù)挖掘、決策分析、任務(wù)規(guī)劃以及多學(xué)科優(yōu)化設(shè)計等領(lǐng)域，成為高維多目標(biāo)優(yōu)化問題的研究熱點之一[1]。

為輔助決策者正確分析多維目標(biāo)信息，多目標(biāo)可視化技術(shù)應(yīng)滿足直觀、有效以及簡單等特點。目前，高維多目標(biāo)可視化問題的研究成果主要分兩類：

一類是完好無損地表現(xiàn)目標(biāo)各維度信息，保證信息的不缺失。平行坐標(biāo)系[2]與熱圖[3]是目前廣泛應(yīng)用的多目標(biāo)可視化方法，其特點是將所有目標(biāo)信息通過單一的視圖呈現(xiàn)，雖然效果直觀，但高維度空間勢必會引起視覺混亂。散點圖[4-5]通過將目標(biāo)的各維度信息兩兩組合成圖表進(jìn)行對比分析，圖表的數(shù)量隨維度增長呈指數(shù)級增加，對于決策者在實際應(yīng)用中十分不便。n維圖表[6]是基于決策偏好的Pareto前沿可視化方法，該方法提出一種目標(biāo)全局信息的共享機(jī)制，采用多圖表分別繪制權(quán)重分配下各維度信息與全局信息的對比結(jié)果，能夠有效地反映目標(biāo)信息與決策偏好。但是，該方法的權(quán)重分配對于同時多個目標(biāo)偏好的分層效果不佳。

另一類是對原始數(shù)據(jù)進(jìn)行壓縮降維，然后投影至低維觀測空間進(jìn)行可視化分析，如主成分圖(Principal Component Biplots， PCB)[7]、星圖[8]、基于分形的降維方法以及旋轉(zhuǎn)其可視化方法[9]等。PCB是目前國外對于高維數(shù)據(jù)可視化非常有效的方法，該方法通過對原始數(shù)據(jù)矩陣進(jìn)行奇異值分解，提取高維數(shù)據(jù)聚類特征后降維映射至低維觀測空間完成可視化，具有較高的數(shù)據(jù)壓縮質(zhì)量。但是，該方法得到靜態(tài)的軸向量與投影點，不能滿足實際應(yīng)用場景中決策者根據(jù)偏好調(diào)整參數(shù)的交互需求。

文獻(xiàn)[11]提出了一種增強(qiáng)高維數(shù)據(jù)可視化效果的自適應(yīng)徑向軸圖方法，根據(jù)交互更新的軸向量矩陣建立降維映射模型，對模型求解獲得低維投影點，可視化效果直觀有效。鑒于此思想，本文利用徑向軸圖的交互優(yōu)勢，提出一種基于徑向軸圖的交互式Pareto前沿可視化決策方法。首先，介紹了徑向軸圖的基本原理，徑向軸圖較好地降低了數(shù)據(jù)降維映射帶來的信息損失。然后，闡述了如何基于徑向軸圖實現(xiàn)Pareto前沿可視化決策，根據(jù)用戶交互即時更新視圖，輔助決策者正確把握目標(biāo)性能趨勢。最后，通過仿真實驗以及與傳統(tǒng)可視化技術(shù)的對比，證明了本文方法能夠?qū)Q策偏好信息與Pareto前沿分布有效地結(jié)合顯示，輔助決策者正確把握目標(biāo)性能趨勢，篩選出滿足實際需求的可行方案。

1 Pareto前沿可視化問題

設(shè)Xf為多目標(biāo)優(yōu)化問題的可行解集，F(xiàn)(x)=(f1(x),f2(x),…,fm(x))為目標(biāo)向量，所有Pareto非支配解的集合構(gòu)成該多目標(biāo)優(yōu)化問題的Pareto非支配解集P*，如式(1)所示[1]。

P*={x∈Xf|?x′∈Xf:x′?x}

(1)

其中，x′?x表示x′Pareto支配x，簡稱支配。

P*的目標(biāo)向量構(gòu)成了多目標(biāo)優(yōu)化問題的非劣最優(yōu)目標(biāo)域，即Pareto最優(yōu)前沿，如式(2)所示。

PF={f1(x),f2(x),…,fm(x)|x∈P*}

(2)

Pareto前沿可視化問題主要解決將m維Pareto最優(yōu)前沿PF降維投影至觀測空間。本文僅考慮Pareto前沿在二維平面上的投影問題。

2 徑向軸圖原理

徑向軸圖方法通過將高維數(shù)據(jù)空間向低維觀測空間投影變換來提供可視化決策功能。為方便討論，本文考慮n維數(shù)據(jù)樣本投影至m維觀測空間，n≥3≥m，m=2。數(shù)據(jù)樣本點表示為xd∈Rn，N個xd組成N×n數(shù)據(jù)樣本矩陣Xd。每一個數(shù)據(jù)樣本對應(yīng)一個投影點p∈Rm，N×m投影點矩陣P。Xd由p與n個m維軸向量vi∈Rm,i=1,…,n表示，n個Vi組成n×m徑向軸矩陣V。

對于降維投影方式的高維數(shù)據(jù)可視化問題，重點在于解決如何減小數(shù)據(jù)降維映射帶來的信息損失。高維數(shù)據(jù)可視化的降維映射問題可描述為：

(3)

其中，F(xiàn)表示Frobenius范數(shù)，本文考慮通過歐幾里得距離評估數(shù)據(jù)降維的損失。F-范數(shù)是由所有奇異值組成的向量2-范數(shù)，數(shù)值等于全部元素平方和的平方根。由于N×n數(shù)據(jù)矩陣各行數(shù)據(jù)樣本xd是相互獨立的，因此問題可轉(zhuǎn)化為：

(4)

對于上式，徑向軸圖方法首先考慮提供決策者旋轉(zhuǎn)、縮放徑向軸功能，即軸向量的方向和模是任意的。該問題就轉(zhuǎn)換成如何根據(jù)特定的軸向量矩陣V求解投影點p，使得pVT到xd的歐式距離比到子空間span{x1,x2,…,xn}中其他向量的歐式距離都短，即高維最小二乘問題。

一般情況下，n×m軸向量矩陣V是列滿秩的，采用Moore-Penrose廣義逆矩陣方法求解該問題，其解的形式如式(5)所示。

p=V?xd=(VTV)-1VT

(5)

由上式可知，V?可視為V的線性變換，投影點的求解過程可以在線性時間內(nèi)完成，滿足了交互式?jīng)Q策的實時性要求。

3 交互式Pareto前沿可視化決策方法實現(xiàn)

基于徑向軸圖的交互式n維Pareto前沿可視化實現(xiàn)需要考慮響應(yīng)用戶交互以及視圖刷新問題?，F(xiàn)階段主流編程平臺均能滿足要求，例如C++、Java、C#等。由于篇幅有限，本文不贅述詳細(xì)實現(xiàn)代碼，主要給出交互式n維Pareto前沿可視化方法的具體實現(xiàn)步驟，方法流程如圖1所示。

圖1 方法流程圖Fig.1 Method flow diagram

1)針對Pareto非支配解集P*中可行解各目標(biāo)之間可能存在較大的數(shù)值差距，首先需要對各目標(biāo)向量fi(x)(i∈{1,…,r})進(jìn)行歸一化處理，得到ki(x)，如式(6)所示。

(6)

2)初始化軸向量矩陣V，均勻分布各軸向量初始朝向，初始長度統(tǒng)一設(shè)為單位長度，如式(7)所示。

(7)

3)設(shè)由ki(x)=(k1(x),k2(x),…,kn(x))，i=1,2,…,N組成了數(shù)據(jù)矩陣Xk。獲得數(shù)據(jù)矩陣Xk與軸向量矩陣V后，根據(jù)徑向軸圖原理，采用廣義逆矩陣方法求解投影點p，即二維平面投影點坐標(biāo)。

4)基于通用軟件編程平臺，根據(jù)投影點坐標(biāo)繪制n維Pareto前沿信息。

5)根據(jù)決策者對可視化視圖中各軸向量的交互操作，即對特定軸向量進(jìn)行旋轉(zhuǎn)、縮放，從而獲得新的軸向量矩陣V。返回步驟3重新計算投影點矩陣。

基于徑向軸圖的交互式n維Pareto前沿可視化效果如圖2所示。

圖2 基于徑向軸圖的交互式Pareto前沿可視化效果Fig.2 Interactive visualization of pareto front based on radial axes plots

圖2表示規(guī)模為50的Pareto前沿分布。其中，P點在各軸上的分量表示ki(x)子目標(biāo)估計值。該目標(biāo)域降維后的總離差等于1.17，估計值較為準(zhǔn)確，滿足決策分析可行性要求。通過旋轉(zhuǎn)、拉伸或者縮短任一軸向量，視圖動態(tài)更新投影點分布，直觀反映決策偏好。同時，該方法支持決策者點擊查看關(guān)注目標(biāo)的各維度信息，準(zhǔn)確把握各目標(biāo)性能趨勢，輔助決策者篩選出符合實際需求的最終方案。

4 仿真實驗與結(jié)果分析

為驗證基于徑向軸圖的交互式高維Pareto前沿可視化方法能夠滿足實際問題中的多目標(biāo)決策需求。本文采用DTLZ1函數(shù)進(jìn)行實驗，并與目前主流應(yīng)用的平行坐標(biāo)系、散點圖以及基于偏好的n維圖表可視化技術(shù)進(jìn)行對比分析，進(jìn)一步驗證本文方法的有效性以及優(yōu)越性。DTLZ1函數(shù)為國際通用的無約束多目標(biāo)優(yōu)化標(biāo)準(zhǔn)測試函數(shù)。最小化目標(biāo)函數(shù)如下：

式中，n=9,xi∈[0,1]。假設(shè)通過優(yōu)化算法得到了Pareto非支配解集，種群為300。現(xiàn)采用主流的可視化方法對Pareto前沿進(jìn)行繪制。其中，平行坐標(biāo)系顯示結(jié)果如圖3所示，散點圖顯示結(jié)果如圖4所示，考慮權(quán)值為ω1=0.1,ω2=0.1,ω3=0.8,ω4=0.8,ω5=0.1 的1-w-norm基準(zhǔn)n維圖表顯示結(jié)果如圖5所示。

圖3 DTLZ1 Pareto前沿平行坐標(biāo)系可視化展示Fig.3 DTLZ1 Pareto front parallel coordinates plot visualization

圖4 DTLZ1 Pareto前沿散點圖可視化展示Fig.4 DTLZ1 Pareto front scatter diagram visualization

圖5 DTLZ1 Pareto前沿1-w-norm圖表可視化展示Fig.5 DTLZ1 Pareto front 1-w-norm diagram visualization

由圖3可以看出，最優(yōu)解集的目標(biāo)向量通過各軸之間的連線表示，決策者能夠指定軸進(jìn)行排序并通過顏色區(qū)分，例如f1的取值范圍為0～0.5，其中淺色部分表示取值在0～0.05范圍內(nèi)分布密集。但是，淺色連線在其他子目標(biāo)適應(yīng)度函數(shù)上未呈現(xiàn)明顯聚類特征。由于各連線交叉重疊，實際應(yīng)用中決策者很難甄別出各方案的優(yōu)劣。

圖4將目標(biāo)向量的各維度信息兩兩組合，繪制出20個二維圖表。決策者需要分析目標(biāo)向量在所有散點圖表中的性能趨勢。由于圖表數(shù)量過多，勢必會引起視覺混亂，無法有效輔助決策者進(jìn)行分析決策。

圖5通過目標(biāo)函數(shù)的共享機(jī)制集成了基于權(quán)重的決策偏好信息，在某一權(quán)重明顯大于其他權(quán)重時分層效果較為明顯。本實驗考慮分配權(quán)重ω1=0.1,ω2=0.1,ω3=0.8,ω4=0.8,ω5=0.1，以測試兩類決策偏好共同作用的效果。由圖5可以看出，f3、f4的取值雖然整體隨縱軸遞增而增大，但未形成明顯的分層效果，無法繼續(xù)篩選出合適方案。

圖6為基于徑向軸圖的交互式n維Pareto前沿可視化效果，各徑向軸表示實驗算例的各子目標(biāo)函數(shù)，在圖6中由對應(yīng)投影點表示，投影點在各軸上的分量表示其子目標(biāo)估計值。將f2、f5軸調(diào)整為相互正交，并拉伸軸向量長度，表示當(dāng)前決策偏好于f2、f5。其他軸旋轉(zhuǎn)至其反方向，得到投影點分布情況如圖6(a)所示，獲得的最左下角點代表某方案f1=0.312 1,f2=0.004 3，f3=0.182 2,f4=0.186 3,f5=0.001 7。通過數(shù)據(jù)校驗，該方案確實為最優(yōu)解集中滿足f2、f5最小的。將軸f3、f4拉伸并旋轉(zhuǎn)至相近角度，其他軸縮小長度并旋轉(zhuǎn)至相對正交的角度，得到Pareto前沿投影點集如圖6(b)所示，表示偏好于f3、f4的最小化取值方

(a) 決策偏好于f2與f5軸的投影點分布(a) Projection point distribution of decision preference in f2 and f5 axises

(b) 拉伸f3、f4軸后的投影點分布(b) Projection point distribution after stretching of f3 and f4 axises

(c)圖縮放后的投影點分布(c) Projection point distribution after scaling ofFigure(b)圖6 基于徑向軸圖的交互式n維 Pareto前沿可視化效果展示Fig.6 Interactive visualization of n-dimensional Pareto front based on radial axes plots

案。由于投影點集分布情況比較密集，通過對整體視圖的縮放和平移操作，得到投影點集分布情況如圖6(c)所示。沿f3、f4軸方向?qū)ふ易畹偷囊稽c，表示某方案f1=0.251 6,f2=0.206 8,f3=0.006 7,f4=0.001 5,f5=0.139 9。通過數(shù)據(jù)校驗，該方案確實為最優(yōu)解集中滿足f3、f4最小的。實驗證明，基于徑向軸圖的交互式n維Pareto前沿可視化決策方法效果直觀有效。

5 結(jié)論

本文提出了一種基于徑向軸圖的交互式n維Pareto前沿可視化決策方法，解決了集成決策偏好的高維多目標(biāo)可視化問題。通過實驗與平行坐標(biāo)系、散點圖以及基于權(quán)重的n維圖表等主流多目標(biāo)可視化方法進(jìn)行對比分析，證明了該方法能夠以形象直觀的方式呈現(xiàn)Pareto前沿各維度信息?；趶较蜉S圖的交互式n維Pareto前沿可視化決策方法不僅有效集成了決策偏好信息，并且能夠根據(jù)用戶交互即時更新視圖，輔助決策者正確把握目標(biāo)性能趨勢。并且，該方法易于實現(xiàn)，在數(shù)據(jù)挖掘、決策分析、任務(wù)規(guī)劃以及多學(xué)科優(yōu)化設(shè)計等領(lǐng)域都具有重要的應(yīng)用價值。