面向復雜仿真元建模的序貫近鄰探索實驗設計方法

雷永林, 王 言, 于芹章, 朱 智, 董 微, 朱一凡

(1. 國防科技大學系統工程學院, 湖南 長沙 410073; 2. 復雜系統仿真總體重點實驗室, 北京 100010)

0 引 言

復雜仿真影響因素多,影響關系非線性,實驗空間巨大。為了避免維數災難問題,基于復雜仿真進行系統方案評估與優化一般要借助仿真元模型。仿真元模型是仿真系統的一種代理模型,基于實驗建模的方法建立,能夠代替仿真系統快速回答關于仿真對象系統的問題。建立仿真元模型的過程稱作仿真元建模。仿真元建模一般包括6個基本步驟:基準想定準備、因素篩選、仿真實驗設計、仿真實驗運行與數據采集、元模型訓練與元模型驗證。其中實驗設計方法的選取是進行仿真元建模的關鍵步驟,直接關系到仿真實驗的計算量與元模型的有效性。

仿真實驗設計方法可以按照是否執行目標仿真系統分為兩大類:非序貫仿真實驗設計方法和序貫仿真實驗設計方法。非序貫仿真實驗設計方法是單方向、一次性的設計,不考慮所仿真的對象系統本身的特性,設計過程不需要執行目標系統。傳統實驗設計方法,如析因設計、正交設計、拉丁超立方抽樣(Latin hypercube sampling, LHS)設計、中心復合設計、隨機采樣等都屬于非序貫方法。非序貫仿真實驗設計方法屬于通用方法,可以應用于任意仿真系統,且不以仿真元建模為目標。

序貫仿真實驗設計方法則將實驗設計看成一個多次迭代的過程,每次迭代都要運行目標系統得到實驗數據,通過分析數據得出下一輪迭代需要重點采樣的區域,據此進行下一輪迭代。序貫實驗設計方法可以分為面向優化的方法和面向元建模的方法兩大類。二者都盡可能減少實驗次數,前者的目標是全局最優點;后者的目標是得到對目標系統的全局近似,也就是本文關注的提高仿真元建模采樣效率的實驗設計方法。

傳統面向仿真元建模的序貫實驗設計方法與采用的回歸模型類型密切相關,并且依賴于人工干預和有關目標系統的先驗知識,不易自動化開展。為此,研究能夠自適應不同回歸模型和目標系統的序貫實驗設計方法對于復雜仿真元建模具有重要意義,屬于近年來該領域的熱點研究問題。相關研究包括:文獻[1-4]綜述了面向仿真或計算機實驗的現代實驗設計與分析方法。文獻[5-6]討論了基于非序貫方法的仿真元建模實驗設計以及領域知識的引入問題。文獻[7-8]討論了基于序貫實驗設計方法的仿真元建模實驗設計問題。文獻[9]研究了面向元建模的全局式序貫實驗設計方法,每次迭代均需進行支持向量回歸并基于擬合效果進行下一輪迭代。文獻[10]討論了基于梯度進行序貫采樣的問題。文獻[11-15]討論了基于分布式或超級計算機進行自動或半自動序貫實驗設計、分析與元建模的問題。文獻[16]等采用序貫仿真實驗方法解決作戰體系能力的分析優化問題。文獻[17]討論了序貫實驗的理論和應用。文獻[18]將序貫仿真用于健康管理。文獻[19]提出了一種新的尋找近鄰點的架構。文獻[20-21]將序貫采樣方法用于作戰仿真、復雜系統實驗設計等多種領域。文獻[22-24]對近鄰分類方法進行了研究,并根據抽樣方法特點與數學原理對抽樣方法使用范圍進行劃分。文獻[25]利用序貫設計方法解決樣本大及驗證周期長的問題。文獻[26]基于空間填充設計方法和神經網絡模型進行作戰仿真元建模工作,用于復雜體系架構仿真評估。文獻[27]使用并行方法提高序貫仿真實驗速度。

本文結合復雜仿真的元建模需求,提出一種序貫近鄰探索實驗設計(sequential neighbor exploration experiment design，SNEED)方法。該方法綜合應用了梯度采樣、隨機近鄰探索采樣以及多項式回歸元模型采樣。其中梯度采樣用于探索領域知識,隨機近鄰探索采樣用于歸納結果,對于存在較弱非線性特征的區域,多項式回歸采樣可以避免全局元建模過擬合問題。與傳統方法相比,本方法通過近鄰探索的方式自動分析搜索復雜系統輸入輸出映射關系呈強非線性的區域,合理分配實驗點,準確反映系統敏感區域的輸入輸出映射關系;無需多次訓練仿真元模型,提高了實驗效率;不依賴于領域知識和人的主觀判斷,有更好的泛化能力,可以支持自動化開展復雜仿真元建模實驗。

1 SNEED方法

面向復雜仿真元建模的SNEED方法的基本思想是:對復雜仿真系統進行自適應非均勻采樣,對非線性強的區域安排更多的樣本點,對線性區域進行多項式回歸再采樣以避免仿真元模型的過擬合問題。面向復雜仿真元建模的SNEED方法流程如圖1所示。圖1中左側為前述仿真元建模的6個基本步驟,其中第3、4步一般需要經歷多次迭代。SNEED則是對這兩步的多輪迭代過程進行了細化設計,如圖1中右側所示,由5個包含迭代的步驟組成。

圖1 仿真元建模過程與SNEED方法流程

1.1 初始實驗稀疏設計

初始實驗設計的目的是為仿真元模型的訓練提供初始的樣本輸入,以便啟動整個迭代過程。該步驟的目標是通過少量點對系統進行初步探測。考慮到方法的通用性,可假定在實驗初始時刻仿真對象系統對于實驗人員是完全未知的,傳統非序貫實驗設計方法即可滿足要求,可以選擇全面設計或LHS設計。實驗發現全面設計是比較穩健的選擇,LHS則需要較多的實驗點以確保系統的敏感區更容易被找到。初始實驗點一般設計100～200個。

1.2 仿真實驗運行

本步驟基于前一步的初始實驗方案進行仿真實驗并收集實驗數據。輸入輸出數據通常是帶有量綱的,為了實驗評估效果更好,將實驗點處理為均勻分布的無量綱值。同時為了確保SNEED方法的通用性,需要對得到的實驗結果數據進行必要的處理,如對某些輸入輸出進行對數化或歸一化處理。

1.3 序貫停止條件判斷

本步驟用于終止序貫迭代過程。傳統序貫方法的結束標志是元模型的擬合誤差達到允許值,因此每一輪迭代都涉及到元模型訓練,是影響算法計算性能的瓶頸環節[28]。SNEED方法通過近鄰遍歷、梯度計算和隨機采樣技術來避免這一問題,其停止條件包括下面兩個,任意一個滿足即可停止迭代。

條件1單次迭代生成實驗點數量小于已生成點數量的一定比例。下一步將要生成新的實驗樣本點,隨著多輪迭代樣本點的增多,實驗探測到的仿真系統的信息將會越來越多,后續每輪產生的實驗點數量將會越來越少,當這個數量所占總實驗點的比例小于某一閾值時,即可認為已經完成運行的實驗點中包含了足夠多的仿真系統信息,可以停止迭代。

條件2生成樣本點個數達到最大數量限制或者迭代次數達到最大次數。這一條件主要是在技術層面避免算法的不穩定性。如果該條件導致迭代停止,則生成的實驗點可能不足以反映仿真系統的信息,得到的元模型對仿真系統的擬合可能達不到要求,需要放寬該條件或檢查仿真模型的正確性。

1.4 新實驗點生成

基本思路是基于實驗點與其近鄰點之間的梯度值來確定其間是否生成新的實驗點。首先計算當前實驗點與其每個近鄰點之間的輸入歐氏距離和輸出差值,據此計算兩點間的梯度,由梯度再計算新實驗點的生成概率,然后采樣確定是否生成新實驗點(見第2.2節)。確定生成新實驗點后,新實驗點的位置確定將引入隨機性以支持對敏感區域的探索(見第2.3節)。

1.5 稀疏區域多項式回歸采樣

完成實驗點采樣迭代后,所有實驗點在輸入空間中的分布取決于仿真對象系統本身的特征,即在系統的輸入敏感區域分布著更多的實驗點,而在系統的輸入不敏感區域實驗點相對稀疏。稀疏區域對于元模型的訓練是不利的,這些區域容易出現過擬合現象[29]。稀疏區域可利用多項式回歸進行采樣以完善實驗數據,實現在不運行仿真系統的情況下增加實驗點密度,較好地解決過擬合問題。

2 新實驗點生成算法

新實驗點的生成是SNEED方法的關鍵步驟。

2.1 基于k-d樹的近鄰遍歷

生成新實驗點需遍歷所有實驗點并查找近鄰實驗點。對于已得的n個實驗點,逐個遍歷采樣的時間復雜度為O(n2),對于復雜系統將消耗更多時間。本文使用k-d樹來優化查找過程,可將時間復雜度降低為O(nlogn),有效提升算法效率。k-d樹是一種分割k維數據空間的平衡二叉樹,主要應用于多維空間關鍵數據的搜索[30]。k-d樹將整個空間劃分為特定的幾個部分,在特定空間的部分內進行搜索操作。

2.2 新實驗點的生成概率計算

設當前(第i個)實驗點為pi0,其臨近點集合Pi={pij},i=1,2,…,n;j=1,2,…,mi,n表示本次迭代時總實驗點個數,mi表示第i個實驗點的近鄰點個數,pij表示第i個實驗點pi0的第j個近鄰點。新實驗點的生成概率計算基于梯度概念,將梯度具體定義為

(1)

式中,ξij為實驗點pij與pi0之間的梯度;Dij為pij與pi0的輸入歐式距離;δij為pij與pi0的輸出差值。ξij∈[-1,1],δij∈[-1,1],Dij∈[-1,1]。

新實驗點生成概率由當前遍歷點與近鄰點的距離D和結果差值δ共同決定。不同的生成概率函數對實驗結果有一定影響,這里給出一種實驗效果較好的生成概率算法:

(2)

式中,Gij為在pij與pi0間生成新點的概率,該算法的函數圖像如圖2所示。

圖2 生成概率算法函數圖像

2.3 新樣本點的空間位置計算

采用隨機采樣策略計算pij與pi0間產生新樣本點的空間位置。引入隨機性不僅提高了算法對不同類型仿真系統的適應性,而且有助于挖掘出未被探索的系統敏感區域[30]。以二維空間為例,基于正態分布確定新實驗點位置如圖3所示。假定輸入空間的每個維度都各自滿足正態分布,其均值為pij與pi0在該維度取值的平均值,標準差為pij與pi0在該維度取值的差的1/6(滿足三Sigma原則),則新實驗點出現在顏色更深的區域的概率更大。

圖3 新實驗點位置概率正態分布

3 案例研究

選取peaks函數中一個經典非線性系統進行實驗和元建模,分別應用LHS、傳統序貫方法和本文提出的SNEED方法進行實驗設計,依據達到同樣預測精度所需的實驗點數量以及有關的模型評價準則來對實驗結果進行比較。

3.1 peaks函數

實驗選用具有兩輸入一輸出的peaks函數作為目標系統:

peaks(x,y)=5(1-x)2e-x2-(y+1)2-

(3)

兩個輸入的取值范圍分別為x∈[-10,5],y∈[-5,10],函數值的熱力圖見圖4。由圖4可見,該系統的敏感區域位于x∈[-3,2],y∈[-3,3],屬于典型的非線性系統。實驗目標是對該系統進行實驗采樣,基于得到的實驗點樣本進行元建模,并采用支持向量回歸(support vector regression,SVR)作為元模型的結構。下面基于SNEED、LHS和傳統序貫方法對該系統進行實驗,并對實驗結果進行對比。

圖4 peaks函數熱力圖

3.2 實驗設計與數據獲取

3.2.1 基于SNEED方法進行實驗

采用LHS方法在實驗空間中生成100個初始實驗點,按照前面介紹的SNEED方法進行3次迭代,其中第1次迭代產生了89個樣本點,第2次迭代產生200個樣本點,第3次迭代產生41個樣本點,41小于已有的樣本點之和的10%(43個),滿足迭代停止條件。此時,總共430次實驗就得到了430個點,各次迭代之后實驗點在輸入空間中的分布如圖5所示,對照圖4可以發現,每一次迭代產生的新實驗點都分布在系統的敏感區域內。

圖5 各次迭代后實驗點的分布

3.2.2 基于LHS和傳統序貫方法

對同一系統分別使用LHS采樣和傳統序貫方法產生實驗點,實驗結果數據分布如圖6和圖7所示。從圖6和圖7的對比可以看出,傳統序貫方法所得實驗點(444個)與SNEED所獲實驗點(430個)都聚集在起伏區域,但SNEED所得實驗點反映起伏區域的邊界更為精確,且SNEED中稀疏區域的抽樣不需要再做實驗,可基于430個實驗點來產生額外的3 000多個訓練點。

圖6 實驗點的分布(LHS)

圖7 實驗點的分布(傳統序貫方法)

3.3 元建模與對比

基于上述3種方法所獲得的實驗數據來進行SVR元建模,選用高斯核函數,gamma取1。圖8～圖10列出了基于3個實驗訓練集上擬合出的SVR元模型的高度熱力圖。

圖8 LHS方法的SVR元模型熱力圖

圖9 傳統序貫方法的SVR元模型熱力圖

圖10 SNEED的SVR元模型熱力圖

由圖8可見,LHS方法的SVR元模型熱力圖中的波峰和波谷與初始系統有較大偏差,由圖9和圖10可見，兩種序貫方法的SVR元模型的偏差較小,原因在于LHS并不能完全提取系統中的所有特征,樣本不足以反映系統的全面信息。與傳統序貫方法的結果相比,SNEED方法通過在非線性區域采取更多特征點實現了對目標系統的更好表示。

基于LHS方法采集了1 000個實驗點作為測試集,選擇平均絕對誤差、均方誤差、R2值等3個模型評價準則對上述3個SVR元模型進行對比,結果如表1所示。

表1 3種方法得到的SVR元模型的性能比較

可以看出,在4個模型評價指標中,基于序貫方法的SVR元模型要比LHS明顯更好;SNEED方法具有更少的點和更小的誤差,還原目標系統的效果要好于傳統序貫方法。

3.4 多個非線性區域peaks函數實驗

前面目標系統中只有一塊主要的非線性區域。為了展示SNEED方法在復雜系統中的有效性,選擇具有多個非線性區域的peaks函數進行實驗,具體公式如下:

peaks(x,y)=10(x+3)2e-(x+5)2-(y-5)2-

(4)

該peaks函數的熱力圖如圖11所示,其中的波峰和波谷所分布的空間明顯較式(3)的系統更大。3種方法各自的實驗過程同前,基于各自實驗結果得到的SVR元模型熱力圖如圖12～圖14所示。

圖11 peaks函數的熱力圖

圖12 LHS方法的SVR元模型熱力圖

圖13 傳統序貫方法的SVR元模型熱力圖

圖14 SNEED的SVR元模型熱力圖

建立類似的測試集對3個SVR元模型進行測試,得到了類似的評價結果,如表2所示。序貫方法明顯優于LHS方法。SNEED和傳統序貫方法相比,SNEED方法得到了670個點,傳統序貫方法得到了676個點,誤差也要比后者小。

表2 3種方法的比較

4 結 論

針對復雜仿真的計算復雜性和因果關系非線性對仿真元建模造成的挑戰,提出一種序貫近SNEED方法。該方法利用梯度信息和隨機采樣技術來自動挖掘系統的非線性信息,在減少實驗次數的基礎上,有效提高了元建模的擬合精度。與傳統序貫方法相比,SNEED方法具有以下優點:① 無需關于系統的先驗知識,可以支持自動化實驗,具備更好的通用性和適應性;② 迭代過程無需多次回歸訓練,所需計算資源少;③對于稀疏系統,在節約實驗點數量的條件下可以大幅度提高訓練數據數量。因此,SNEED方法可以應用于各類復雜仿真系統的實驗設計與元建模,對于同時具備非線性和稀疏性的系統也具有更好的效能。下一步將結合武器裝備作戰效能仿真系統(weapon experiment simulation system, WESS)的評估分析需要,開發自動化的序貫仿真實驗引擎,以支持WESS系統序貫仿真實驗與仿真元建模的自動化開展。