約束空間近似正交的空間填充試驗(yàn)設(shè)計(jì)方法

尤 楊, 金 光, 潘正強(qiáng), 郭 芮

(1. 國(guó)防科技大學(xué)系統(tǒng)工程學(xué)院, 湖南 長(zhǎng)沙 410073; 2. 軍事科學(xué)院系統(tǒng)工程研究院, 北京 102300)

0 引 言

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

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

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

為此，提出了一種約束設(shè)計(jì)空間近似正交的空間填充準(zhǔn)則,該準(zhǔn)則將注意力集中于設(shè)計(jì)矩陣的正交性和空間填充特性,并且在實(shí)際設(shè)計(jì)中可以通過(guò)設(shè)置權(quán)重系數(shù)調(diào)節(jié)對(duì)兩個(gè)準(zhǔn)則的偏重程度。此外,將該準(zhǔn)則引入改進(jìn)的隨機(jī)坐標(biāo)交換算法,分別以空間填充性和正交性的概率函數(shù)制定了該算法中交換坐標(biāo)的選擇策略,從而在約束空間坐標(biāo)交換的過(guò)程中達(dá)到設(shè)計(jì)矩陣正交性和空間填充性的同步優(yōu)化。還將原隨機(jī)坐標(biāo)交換算法與新的算法在解析約束和非解析這兩種典型的約束空間類型中的應(yīng)用做了對(duì)比,依據(jù)本文提出的方法得到的設(shè)計(jì)方案均具有良好的正交性和空間填充特性。

1 近似正交空間填充設(shè)計(jì)準(zhǔn)則

正交性和空間填充性都是試驗(yàn)設(shè)計(jì)常用的準(zhǔn)則。正交性設(shè)計(jì)中試驗(yàn)因子的主效應(yīng)是相互獨(dú)立的,所以在回歸模型擬合,特別是主效應(yīng)模型的擬合方面,正交性試驗(yàn)設(shè)計(jì)具有更高的有效性[20-23]?？臻g填充性準(zhǔn)則將設(shè)計(jì)點(diǎn)均勻分布在整個(gè)設(shè)計(jì)空間,避免設(shè)計(jì)點(diǎn)重疊導(dǎo)致的試驗(yàn)資源浪費(fèi),能夠提供更全面的試驗(yàn)空間信息。Joseph觀察發(fā)現(xiàn)正交性和空間填充性這兩個(gè)準(zhǔn)則并不一致,分別采用這兩個(gè)標(biāo)準(zhǔn)得到的試驗(yàn)方案可能會(huì)有較大差異,且因子數(shù)量越多,問(wèn)題就越嚴(yán)重[14]。為此,本文提出一種多目標(biāo)準(zhǔn)則,可以兼顧設(shè)計(jì)方案的正交性和空間填充性。

1.1 空間填充性度量

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

(1)

式中：p取正整數(shù)；dij表示設(shè)計(jì)矩陣Dn×m中任意兩設(shè)計(jì)點(diǎn),即行向量xi和xj之間的距離,可表示為

(2)

式中：

xi=[xi1,xi2,…,xim]

xj=[xj1,xj2,…,xjm]

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

1.2 正交性度量

試驗(yàn)點(diǎn)之間存在正交性可以保證回歸模型系數(shù)估計(jì)的相互獨(dú)立, 增強(qiáng)分析因子對(duì)試驗(yàn)響應(yīng)的影響和各因子交互作用的能力[26-27]。當(dāng)基于正交表的設(shè)計(jì)不易構(gòu)造或不能靈活適用時(shí),可以用相關(guān)系數(shù)近似衡量設(shè)計(jì)矩陣的正交程度,即用設(shè)計(jì)矩陣中所有列的相關(guān)系數(shù)最大值作為設(shè)計(jì)矩陣正交性度量[28-29],構(gòu)造近似正交的試驗(yàn)設(shè)計(jì)。設(shè)計(jì)矩陣Dn×m任意兩個(gè)列向量Xi與Xj的相關(guān)系數(shù)定義為

(3)

式中：

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

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

1.3 多目標(biāo)優(yōu)化準(zhǔn)則

為了獲得近似正交的空間填充設(shè)計(jì),將試驗(yàn)設(shè)計(jì)問(wèn)題轉(zhuǎn)化為多目標(biāo)優(yōu)化問(wèn)題:在給定的約束條件下,找到一個(gè)同時(shí)最小化ρ=max|ρi j|和φp的試驗(yàn)方案。

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

(4)

(5)

于是定義:

(6)

將φp進(jìn)行無(wú)量綱化,新的目標(biāo)優(yōu)化準(zhǔn)則為最小化如下目標(biāo)函數(shù):

(7)

2 約束空間試驗(yàn)設(shè)計(jì)算法

試驗(yàn)點(diǎn)交換或坐標(biāo)交換是構(gòu)造設(shè)計(jì)方案的一類常用方法。點(diǎn)交換是每次選擇設(shè)計(jì)矩陣的一行迭代改進(jìn)一個(gè)設(shè)計(jì)點(diǎn),列交換是每次選擇設(shè)計(jì)矩陣的一列迭代提高某一因子的設(shè)計(jì)水平。這兩種方法應(yīng)用于約束空間試驗(yàn)設(shè)計(jì),需要解決候選試驗(yàn)點(diǎn)集生成和坐標(biāo)改進(jìn)的多維優(yōu)化問(wèn)題,這在復(fù)雜約束和高維情況下都不易操作。坐標(biāo)交換法通過(guò)對(duì)當(dāng)前坐標(biāo)可行域投影,針對(duì)優(yōu)化準(zhǔn)則函數(shù)求解一維優(yōu)化問(wèn)題,可降低計(jì)算復(fù)雜度,解決復(fù)雜約束空間上的試驗(yàn)設(shè)計(jì)問(wèn)題。

2.1 隨機(jī)坐標(biāo)交換算法

坐標(biāo)交換法需要解決的一個(gè)重要問(wèn)題是,在每次迭代中應(yīng)該選擇哪個(gè)坐標(biāo)進(jìn)行交換,以最大限度地改善設(shè)計(jì)方案。約束空間是以確定性的貪婪準(zhǔn)則對(duì)坐標(biāo)進(jìn)行改進(jìn)的方式,容易導(dǎo)致局部最優(yōu),為此,Kang提出隨機(jī)坐標(biāo)交換算法[9],通過(guò)定義刪除函數(shù)來(lái)評(píng)估行、列的交換給目標(biāo)函數(shù)帶來(lái)的改進(jìn),并以正比于刪除函數(shù)的概率選擇坐標(biāo)進(jìn)行交換。隨機(jī)坐標(biāo)交換算法通過(guò)依概率選擇行、列實(shí)現(xiàn)算法的隨機(jī)性,有利于克服局部最優(yōu)問(wèn)題。

坐標(biāo)交換法算法可以描述如下:

步驟 4確定要交換的坐標(biāo)Dij,根據(jù)因子取值范圍及約束條件計(jì)算點(diǎn)i在第j維投影的可行區(qū)間,求解一維優(yōu)化,得到最優(yōu)解x;

2.2 坐標(biāo)交換策略

以上給出的坐標(biāo)交換算法的基本框架需要根據(jù)具體準(zhǔn)則給出刪除函數(shù)的具體實(shí)現(xiàn),以便在此基礎(chǔ)上選擇交換的行和列。下面給出利用第1節(jié)中近似正交的空間填充優(yōu)化準(zhǔn)則指導(dǎo)的坐標(biāo)交換具體策略。

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

(8)

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

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

(9)

隨機(jī)選擇一對(duì)設(shè)計(jì)點(diǎn),即行向量對(duì)(xa,xb)。若某兩點(diǎn)之間的距離為0,則其選擇概率為1。

(4) 計(jì)算設(shè)計(jì)點(diǎn)xa、xb與其他設(shè)計(jì)點(diǎn)之間的距離之和,并以正比于

(10)

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

3 示例分析

下面通過(guò)示例,說(shuō)明本文提出算法的性能及算法的適用性。

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

Kang提出試驗(yàn)空間上的約束條件[9]為

(11)

表1 設(shè)計(jì)結(jié)果對(duì)比

圖1 n=16時(shí)設(shè)計(jì)方案對(duì)比Fig.1 Comparison of design schemes at n=16

比較本文算法和Kang提出的方法[9],算法收斂過(guò)程如圖2所示。其中，橫坐標(biāo)代表坐標(biāo)交換尋優(yōu)次數(shù),縱坐標(biāo)代表目標(biāo)函數(shù)值?？梢钥闯霰疚乃惴ň哂懈斓氖諗克俣?。

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

重復(fù)運(yùn)行100次,對(duì)每次運(yùn)行得到的最優(yōu)目標(biāo)值做直方圖,如圖3所示。其中，橫坐標(biāo)代表目標(biāo)函數(shù)值,縱坐標(biāo)代表其出現(xiàn)頻次?？梢钥闯霰疚乃惴ǖ姆€(wěn)定性明顯優(yōu)于Kang提出的方法。此外,該結(jié)果說(shuō)明,基于初始隨機(jī)選擇試驗(yàn)點(diǎn)和坐標(biāo)交換的試驗(yàn)方案優(yōu)化算法,都存在一定的不穩(wěn)定性,即單次優(yōu)化會(huì)陷入局部最優(yōu)。為此,可通過(guò)多次改變初始設(shè)計(jì)點(diǎn)來(lái)獲得最優(yōu)的試驗(yàn)方案。

圖3 兩種算法穩(wěn)定性對(duì)比Fig.3 Stability comparison between two algorithms

針對(duì)不同的設(shè)計(jì)點(diǎn)數(shù)量,分別利用本文的算法和Kang提出算法[9]生成試驗(yàn)方案,試驗(yàn)方案的相關(guān)性準(zhǔn)則值和空間填充準(zhǔn)則值如表2所示,由于本文權(quán)重系數(shù)設(shè)置為ω=0.5,所以空間填充方面的表現(xiàn)整體與SF-SCE相差不多,而正交性則明顯優(yōu)于SF-SCE。如果需要提高空間填充性,可以適當(dāng)調(diào)節(jié)權(quán)重系數(shù)取值。

表2 不同設(shè)計(jì)點(diǎn)數(shù)下的算法表現(xiàn)

3.2 非解析約束的受限空間

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

表3 設(shè)計(jì)結(jié)果對(duì)比

圖4 非解析約束設(shè)計(jì)方案對(duì)比Fig.4 Comparison of design schemes with non-analytic constraints

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

4 結(jié) 論

本文基于隨機(jī)坐標(biāo)交換算法,提出了一種新型適用于約束試驗(yàn)空間的近似正交空間填充試驗(yàn)設(shè)計(jì)方法,設(shè)計(jì)準(zhǔn)則由空間填充性和正交性兩部分組成,可以根據(jù)設(shè)計(jì)需求調(diào)節(jié)權(quán)重系數(shù)。通過(guò)對(duì)不同約束類型、不同試驗(yàn)規(guī)模等示例分析表明,本文提出的設(shè)計(jì)方法設(shè)計(jì)效果較好,且具有較好的穩(wěn)定性，適用于多維約束空間。本文僅針對(duì)連續(xù)定量試驗(yàn)因子的近似正交空間填充設(shè)計(jì),后續(xù)將對(duì)于定性定量混合因子、混合約束以及其他試驗(yàn)設(shè)計(jì)準(zhǔn)則,繼續(xù)開(kāi)展有關(guān)試驗(yàn)設(shè)計(jì)方法研究。