約束空間近似正交的空間填充試驗設計方法

尤 楊, 金 光, 潘正強, 郭 芮

(1. 國防科技大學系統工程學院, 湖南 長沙 410073; 2. 軍事科學院系統工程研究院, 北京 102300)

0 引 言

試驗設計已經成為實物試驗和仿真試驗中重要的研究內容。通過良好的試驗點設計方案,可以較少的試驗代價得到較高精度的試驗數據和試驗分析結果。目前學者們已經提出了大量的試驗設計方法,在仿真試驗設計中,空間填充設計是重要的一類試驗設計方法,其試驗點均勻充滿整個設計空間,均勻設計、拉丁超立方設計(Latin hypercube design,LHD)等是重要的空間填充設計方法。在這些方法中,一般假設各試驗因子是相互獨立的,即改變某個因子的水平并不影響其他因子的取值。然而,實際工程中有很多試驗因子之間存在約束的情況,沒有任何限制、完全符合因子獨立性條件的試驗設計問題是較少的。這種情況下,試驗區域不是標準的超立方體,而是某種不規則形狀的區域。

有約束情況的試驗設計問題是目前試驗設計研究的一個熱點。Montgomery等人考慮兩個因子情形,引入D -最優和A -最優設計來實現約束區域的混合試驗設計[1]。Auffray等人提出了有界凸區域上的極大極小設計,該設計基于模擬退火(simulated annealing,SA)和特定的Gibbs算法[2]。基于迭代聚類的方法也可以得到關于有界凸區域上的試驗方案,比如Lekivetz和Jones提出了快速靈活空間填充(fast flexible space-filling,FFF)設計[3],并將其推廣到含定性因子的不規則設計空間[4],該設計利用層次聚類來生成空間填充設計,然而缺乏對設計空間邊界的探索。Mak和Joseph提出了一種粒子群優化與聚類相結合的混合算法,優化了原有極小極大設計的性能,并且開發了相應的R包[5]。但是基于聚類的方法需要初始生成遠大于試驗設計數量n個點,特別是在高維不規則約束空間,會大大降低計算效率。Perrin和Cannamela提出了一種基于排斥的方法來生成任意有界凸輸入空間中的初始空間填充設計[6],該方法還可以向初始試驗設計添加新元素,相對于以上聚類方法,具有更好的低維投影均勻性。除凸約束外,非凸空間在現實問題中更為常見,在這種情況下,Fuerle和Sienz針對任意約束的試驗區域引入Audze-Eglais最優拉丁超方設計[7],并將該方法應用于結構優化問題,但優化的嵌套限制了其在高維情況下的應用。Beal等人改進WSP(Wootton Sergent Phan-Tan-Luu)算法構造空間填充設計,可以應用于具有特定試驗約束的設計,并且可以增加特定感興趣區域的觀測密度[8],但不適用于試驗設計次數確定的情形。Kang提供了一種在任意規則或不規則約束空間下構造單準則下最優試驗方案的隨機坐標交換算法[9],其性能優于貪婪坐標交換算法,且可通過多次試算來避免局部最優問題,但算法穩定性較差且僅針對單一設計準則。

學者們為衡量試驗方案優劣提出了多種準則,包括正交性、均勻性、最大熵、最小勢能,以及以距離準則、中心偏差、φp為代表的空間填充性準則等。從多目標優化的角度出發,Yang以最大化設計點的平均距離和最小化距離偏差為判據[10],Zhang等對正交性和均勻性進行綜合考量[11],王東輝等人提出了適用于約束空間的設計點可行性和均勻性的綜合準則[12-13]。Joseph同時考慮了LHD的正交性和均勻性,首先提出了正交-極大極小多目標優化準則[14],劉新亮[15]和張昆侖[16]等人則對其優化算法進行了改進。Wang等人也相繼構造了正交或近似正交的空間填充設計[17-21],都是針對于規則正交設計或基礎LHD而構造的,但其在生成設計點數目或不規則的試驗空間上不具有靈活性。并且以上設計采用諸如SA、增強型隨機進化(enhanced stochastic evolutionary,ESE)[22]等算法作為外部優化循環,為了能夠從低質量的局部最優解轉移到高質量的全局解,而內部循環一般使用列元素交換(為了保證LHD的平衡屬性),這都是在初始LHD基礎上進行迭代調整的,適用范圍有限,且對于非凸約束空間等復雜約束、元素交換具有不確定性,不能保證產生可行解或更優解。

為此，提出了一種約束設計空間近似正交的空間填充準則,該準則將注意力集中于設計矩陣的正交性和空間填充特性,并且在實際設計中可以通過設置權重系數調節對兩個準則的偏重程度。此外,將該準則引入改進的隨機坐標交換算法,分別以空間填充性和正交性的概率函數制定了該算法中交換坐標的選擇策略,從而在約束空間坐標交換的過程中達到設計矩陣正交性和空間填充性的同步優化。還將原隨機坐標交換算法與新的算法在解析約束和非解析這兩種典型的約束空間類型中的應用做了對比,依據本文提出的方法得到的設計方案均具有良好的正交性和空間填充特性。

1 近似正交空間填充設計準則

正交性和空間填充性都是試驗設計常用的準則。正交性設計中試驗因子的主效應是相互獨立的,所以在回歸模型擬合,特別是主效應模型的擬合方面,正交性試驗設計具有更高的有效性[20-23]。空間填充性準則將設計點均勻分布在整個設計空間,避免設計點重疊導致的試驗資源浪費,能夠提供更全面的試驗空間信息。Joseph觀察發現正交性和空間填充性這兩個準則并不一致,分別采用這兩個標準得到的試驗方案可能會有較大差異,且因子數量越多,問題就越嚴重[14]。為此,本文提出一種多目標準則,可以兼顧設計方案的正交性和空間填充性。

1.1 空間填充性度量

在計算機試驗中對于空間填充性的度量有很多設計準則,包括極大極小準則、極小極大準則、最大投影準則等,但基于距離的準則(如maximin準則)傾向于將更多的點放置在超立方體角點和邊界上,因此在該準則下每個因子并不具有良好的投影屬性[24]。基于距離的φp準則最先由Morris和Mitchell提出[25],并應用于坐標為整數的LHD(n,m),該準則可以保證m維良好的空間填充和每一維的均勻投影性質。即最小化:

(1)

式中：p取正整數；dij表示設計矩陣Dn×m中任意兩設計點,即行向量xi和xj之間的距離,可表示為

(2)

式中：

xi=[xi1,xi2,…,xim]

xj=[xj1,xj2,…,xjm]

t取1和2分別表示曼哈頓距離和歐氏距離。

1.2 正交性度量

試驗點之間存在正交性可以保證回歸模型系數估計的相互獨立, 增強分析因子對試驗響應的影響和各因子交互作用的能力[26-27]。當基于正交表的設計不易構造或不能靈活適用時,可以用相關系數近似衡量設計矩陣的正交程度,即用設計矩陣中所有列的相關系數最大值作為設計矩陣正交性度量[28-29],構造近似正交的試驗設計。設計矩陣Dn×m任意兩個列向量Xi與Xj的相關系數定義為

(3)

式中：

Xi=[X1i,X2i,…,Xni]T

Xj=[X1j,X2j,…,Xnj]T

1.3 多目標優化準則

為了獲得近似正交的空間填充設計,將試驗設計問題轉化為多目標優化問題:在給定的約束條件下,找到一個同時最小化ρ=max|ρi j|和φp的試驗方案。

多目標優化的一個常用方法是優化所有目標函數的加權平均,即以權重作為設計系數ω1ρ+ω2φp。其中ω1和ω2是預先設定的權重。由于ρ和φp的尺度差別很大且數量級不同,比如目標函數ρ∈[0, 1],而目標函數φp可能很大,選擇合適的權重并非易事。需要對φp進行無尺度化處理,使目標函數權重的分配更合理。由Joseph可知LHD中φp的上、下界分別如下[14]:

(4)

(5)

于是定義:

(6)

將φp進行無量綱化,新的目標優化準則為最小化如下目標函數:

(7)

2 約束空間試驗設計算法

試驗點交換或坐標交換是構造設計方案的一類常用方法。點交換是每次選擇設計矩陣的一行迭代改進一個設計點,列交換是每次選擇設計矩陣的一列迭代提高某一因子的設計水平。這兩種方法應用于約束空間試驗設計,需要解決候選試驗點集生成和坐標改進的多維優化問題,這在復雜約束和高維情況下都不易操作。坐標交換法通過對當前坐標可行域投影,針對優化準則函數求解一維優化問題,可降低計算復雜度,解決復雜約束空間上的試驗設計問題。

2.1 隨機坐標交換算法

坐標交換法需要解決的一個重要問題是,在每次迭代中應該選擇哪個坐標進行交換,以最大限度地改善設計方案。約束空間是以確定性的貪婪準則對坐標進行改進的方式,容易導致局部最優,為此,Kang提出隨機坐標交換算法[9],通過定義刪除函數來評估行、列的交換給目標函數帶來的改進,并以正比于刪除函數的概率選擇坐標進行交換。隨機坐標交換算法通過依概率選擇行、列實現算法的隨機性,有利于克服局部最優問題。

坐標交換法算法可以描述如下:

步驟 4確定要交換的坐標Dij,根據因子取值范圍及約束條件計算點i在第j維投影的可行區間,求解一維優化,得到最優解x;

2.2 坐標交換策略

以上給出的坐標交換算法的基本框架需要根據具體準則給出刪除函數的具體實現,以便在此基礎上選擇交換的行和列。下面給出利用第1節中近似正交的空間填充優化準則指導的坐標交換具體策略。

(1) 根據第1.2節中提出的方法計算矩陣列相關系數的大小,從矩陣列向量[X1,X2,…,Xm]中,以

(8)

為概率隨機選擇一對因子組合,即列向量對(Xk,Xl)。

(3) 根據第1.1節中提出的方法計算設計點之間距離的大小,從矩陣行向量[x1,x2,…,xn]T中,依概率

(9)

隨機選擇一對設計點,即行向量對(xa,xb)。若某兩點之間的距離為0,則其選擇概率為1。

(4) 計算設計點xa、xb與其他設計點之間的距離之和,并以正比于

(10)

的概率隨機選擇(xa,xb)中的一個作為待刪除行i。

3 示例分析

下面通過示例,說明本文提出算法的性能及算法的適用性。

3.1 等式或不等式約束的受限空間

Kang提出試驗空間上的約束條件[9]為

(11)

表1 設計結果對比

圖1 n=16時設計方案對比Fig.1 Comparison of design schemes at n=16

比較本文算法和Kang提出的方法[9],算法收斂過程如圖2所示。其中，橫坐標代表坐標交換尋優次數,縱坐標代表目標函數值。可以看出本文算法具有更快的收斂速度。

圖2 兩種算法收斂速度對比Fig.2 Comparison of convergence speed between two algorithms

重復運行100次,對每次運行得到的最優目標值做直方圖,如圖3所示。其中，橫坐標代表目標函數值,縱坐標代表其出現頻次。可以看出本文算法的穩定性明顯優于Kang提出的方法。此外,該結果說明,基于初始隨機選擇試驗點和坐標交換的試驗方案優化算法,都存在一定的不穩定性,即單次優化會陷入局部最優。為此,可通過多次改變初始設計點來獲得最優的試驗方案。

圖3 兩種算法穩定性對比Fig.3 Stability comparison between two algorithms

針對不同的設計點數量,分別利用本文的算法和Kang提出算法[9]生成試驗方案,試驗方案的相關性準則值和空間填充準則值如表2所示,由于本文權重系數設置為ω=0.5,所以空間填充方面的表現整體與SF-SCE相差不多,而正交性則明顯優于SF-SCE。如果需要提高空間填充性,可以適當調節權重系數取值。

表2 不同設計點數下的算法表現

3.2 非解析約束的受限空間

在Kang所提到的例5中,展示了一類非解析定義的受限空間(邊界點約束受限空間)對冰川樁網的二維設計,其邊界由247個點定義,而非等式或不等式約束。利用247個邊界點構造多邊形約束問題,結合纏繞數算法判斷設計點是否在受限空間內,具體算法可參照Hormann[30]。對于該例中的14樁設計,本文的多目標優化算法設置準則參數p=20,設置權重分配ω=0.5,可根據對空間填充特性和正交性的優化需求調節權重系數。SF-SCE算法與本文方法均設置準則參數p=20,t=1,設計結果如圖4和表3所示。

表3 設計結果對比

圖4 非解析約束設計方案對比Fig.4 Comparison of design schemes with non-analytic constraints

圖4(a)設計方案的相關性為0.21、空間填充性為4.02;圖4(b)設計方案的相關性為0.09、空間填充性為3.88,MO-SCE兩項均優于SF-SCE算法獲得的試驗設計結果。因此,本文提出的試驗設計方法應用于更加不規則的非解析約束空間也具有較大的優勢。

4 結 論

本文基于隨機坐標交換算法,提出了一種新型適用于約束試驗空間的近似正交空間填充試驗設計方法,設計準則由空間填充性和正交性兩部分組成,可以根據設計需求調節權重系數。通過對不同約束類型、不同試驗規模等示例分析表明,本文提出的設計方法設計效果較好,且具有較好的穩定性，適用于多維約束空間。本文僅針對連續定量試驗因子的近似正交空間填充設計,后續將對于定性定量混合因子、混合約束以及其他試驗設計準則,繼續開展有關試驗設計方法研究。