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

胡佳鑫，楊樂平

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

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

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

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

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

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

1 Pareto前沿可視化問題

設Xf為多目標優化問題的可行解集，F(x)=(f1(x),f2(x),…,fm(x))為目標向量，所有Pareto非支配解的集合構成該多目標優化問題的Pareto非支配解集P*，如式(1)所示[1]。

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

(1)

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

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

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

(2)

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

2 徑向軸圖原理

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

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

(3)

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

(4)

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

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

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

(5)

由上式可知，V?可視為V的線性變換，投影點的求解過程可以在線性時間內完成，滿足了交互式決策的實時性要求。

3 交互式Pareto前沿可視化決策方法實現

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

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

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

(6)

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

(7)

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

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

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

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

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

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

4 仿真實驗與結果分析

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

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

圖3 DTLZ1 Pareto前沿平行坐標系可視化展示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可以看出，最優解集的目標向量通過各軸之間的連線表示，決策者能夠指定軸進行排序并通過顏色區分，例如f1的取值范圍為0～0.5，其中淺色部分表示取值在0～0.05范圍內分布密集。但是，淺色連線在其他子目標適應度函數上未呈現明顯聚類特征。由于各連線交叉重疊，實際應用中決策者很難甄別出各方案的優劣。

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

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

圖6為基于徑向軸圖的交互式n維Pareto前沿可視化效果，各徑向軸表示實驗算例的各子目標函數，在圖6中由對應投影點表示，投影點在各軸上的分量表示其子目標估計值。將f2、f5軸調整為相互正交，并拉伸軸向量長度，表示當前決策偏好于f2、f5。其他軸旋轉至其反方向，得到投影點分布情況如圖6(a)所示，獲得的最左下角點代表某方案f1=0.312 1,f2=0.004 3，f3=0.182 2,f4=0.186 3,f5=0.001 7。通過數據校驗，該方案確實為最優解集中滿足f2、f5最小的。將軸f3、f4拉伸并旋轉至相近角度，其他軸縮小長度并旋轉至相對正交的角度，得到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軸方向尋找最低的一點，表示某方案f1=0.251 6,f2=0.206 8,f3=0.006 7,f4=0.001 5,f5=0.139 9。通過數據校驗，該方案確實為最優解集中滿足f3、f4最小的。實驗證明，基于徑向軸圖的交互式n維Pareto前沿可視化決策方法效果直觀有效。

5 結論

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