一種適用于約束空間的拉丁超立方取點策略

杜 麗，呂利葉，孫 偉，宋學官

（大連理工大學機械工程學院，遼寧 大連 116024）

1 引言

復雜機械系統的設計與優化一般需要成千上萬次的高保真模型仿真方可完成，這個過程耗時巨大成本高昂，因此基于小樣本數據的代理模型技術應運而生，且已廣泛應用于工程實際中[1]。試驗設計（Design of Experiment，DoE）是代理模型技術中關鍵的一環，其抽樣結果對模型的預測精度與后續優化設計有著至關重要的影響。一個好的DoE方法，既可以減少試驗次數，縮短試驗時間，又可避免盲目性，迅速得到有效的結果。

常用的DoE方法有[2-4]：全析因試驗設計（Full Factorial Sam?pling，FFS）、正交試驗設計（Orthogonal Design，OD）[2]、均勻試驗設計（Uniform Design，UD）[3]、拉丁超立方取樣[4]（Latin Hypercube Sampling，LHS）等。

LHS是由文獻[4]于1980年提出的一種抽樣方法，也是目前最受歡迎的抽樣方法之一。LHS最重要的特性是其投影特性，即任意兩個樣本點在任意維度的投影都不會重合，其重要意義在于減少在相同維度的不必要試驗。但是，一個好的試驗設計應該同時滿足投影特性和空間填充性或空間均勻性[5-6]。研究者針對DoE的空間填充性與投射特性進行了諸多研究，發展了基于不同準則的優化的拉丁超立方取樣（Optimal Latin Hypercube Sam?pling，OLHS）[7-9]。這些準則包括最小Audze Eglais勢能準則[7]）、最小綜合均方誤差（IMSE）準則[8]，最大熵準則[9]以及最大最小距離準則[5]等。

以上提出DoE方法均只適用于無約束空間，而對于約束空間這些方法均不能直接使用。所以，一些研究者就考慮了設計變量構建的約束條件并提出約束拉丁超立方抽樣（Constrained Lat?in Hypercube Sampling，CLHS）[10-11]。Petelet等開發了一種考慮不等式約束的LHS方法（CLHS），通過對初始拉丁超立方設計進行置換以滿足所需的單調約束，它是CLHS的先驅，但是當兩個約束變量的最小邊界接近時，其空間填充性能變差。Stinstra等提出了一種針對約束空間的最大最小距離方法，叫做SFDP**法。該方法結合非線性規劃求解器CONOPT來解決最大最小設計問題，但其投影性能不理想。

由此提出了一種應用于約束空間的連續局部枚舉拉丁超立方取樣方法（Sequential Local Enumeration-Based LHS for Con?strained Design Space，SLE-CLHS），稱為SLE-CLHS策略。SLECLHS策略中涉及LHS理論、最大最小距離（Maximin）理論、連續局部枚舉拉丁超立方取樣（SLE-LHS）[13]，因此在接下來的文章中，將會先介紹經典拉丁超立方抽樣、最大最小距離拉丁超立方取點（maximin-LHS），然后詳細論述所提出的SLE-CLHS算法，接著利用一個二維及兩個三維數值案例對SLE-CLHS方法進行演示，并用空間填充特性與投影特性對SLE-CLHS方法進行評估，最后是結論與展望。

2 LHS、OLHS及Maxmin-LHS抽樣

2.1 拉丁超立方抽樣（LHS）

LHS方法，也叫做隨機LHS，由蒙特卡羅（Monte Carlo）方法演化而來，Monte Carlo方法的主要特點是它的斂散性依賴于獨立的隨機參數個數，而LHS則完全不同。LHS是一種分層抽樣方法，當考慮一維的單個變量輸入問題：y=f（x），其中x是一個隨機變量。對于有多個隨機變量輸入，一般的分層抽樣需要將輸入的樣本空間等概率地轉化為N個區域，這操作起來是很困難的。此時LHS又是另一種多維分層抽樣方法，其工作原理如下：

（1）定義參與計算機運行的抽樣數目N；

（2）把每一次輸入等概率得分成N，且有：

（3）對每一列僅抽取一個樣本，各列中所抽取樣本位置是隨機的。

相對于單純的分層抽樣，LHS抽樣的最大優勢就在于任何大小的抽樣數目都能容易地產生。至于估計均值，通常的做法是：

一般情況下，這種估計的標準誤差并沒有對標準蒙特卡羅抽樣方法進行任何改進，但實際上，LHS對均值和方差的估計和Mon?te Carlo方法相比，在效果上至少是一樣的，且常常會顯著改善。

2.2 優化拉丁超立方抽樣（OLHS）

最優化拉丁超立方（Optimal Latin Hypercube Sampling，OL?HS）是一種典型的“充滿空間”（Space Filling）試驗設計，該方法能很好地應用于復雜系統仿真試驗的試驗設計問題。產生OLHS分布點的優化準則有很多，比如最大熵準則[9]、中心偏差準則[12]、最大最小距離和最小最大距離準則[5]等。LHS利用隨機抽樣得到試驗設計的點，與OLHS的區別在于抽樣點的分布不同。OLHS的點的分布更加結構化，優化出來的點的分布更加均勻。但是OLHS比LHS更耗時，比如：一個試驗設計有5個設計變量，10個樣本點，那么將會有6*1032個可能的分布方案，這顯然是不可能的，因此需要一個更加高效的方法在設計空間中搜索，接下來介紹的最大最小距離準則（Maximin）就是一種行之有效的方法。

2.3 最大最小距離拉丁超立方（Maximin-LHS）

相對于其他的抽樣方法，Maximin-LHS主要有三方面的主要優勢。首先，Maximin-LHS可以在不耗費過多的計算成本的前提下用來產生任意數量的樣本點，且Maximin-LHS在模擬實驗中是參數化的，非常適合于數值仿真；其次，Maximin-LHS在減少抽樣點誤差的均值與方差方面表現良好；最后，Maximin-LHS可以較好的保證樣本點的空間填充性能與投影性能。對比了Maximin-LHS和隨機LHS的取點情況，如圖1所示。可以明確看出隨機LHS可能出現所有樣本點都位于對角線上的情況，雖然這照樣滿足抽樣方案的投影性質但填充性能很差，而Maximin-LHS卻能較好的填充整個空間，均勻分布在可行域內。

圖1 最大最小距離LHS分布和常規LHS的糟糕分布Fig.1 Maximin-LHS Sampling and Terrible LHS Sampling

Maximin準則可以理解為最大化樣本點之間的最小距離，如式（3）所示。

式中：d（xi，x）j—兩個樣本點xi，xj之間的距離：

文獻[6]最先提出基于退火理論的Maximin準則，對于一個給定的試驗設計，通過對內部點與點距離d（ij1<=i，j<=n；1<=t<=2>）的排序，會產生一個索引序列（J1，J2，…J）s，式中di代表不同的距離值d1

式中：p—正整數，如果p值太大將會影響后續的分布。也將采用?p準則用于后續研究。

3 SLE-CLHS算法

3.1 SLE-CLHS算法的概述

SLE-CLHS算法考慮了樣本變量之間的約束，可直接用于約束設計空間的可行域采樣。在采樣過程中先剔除不滿足約束條件的點，然后在可行域中產生新的點，新點在約束空間中繼續搜索，直到該點達到滿足整體抽樣的空間填充性和投影性。SLE-CLSH的采樣過程如下：

當用Maxmin-LHS算法在無約束設計空間中產生m個樣本點時，落在可行域之外的點是無意義的，應予以消除。為了解決這個問題，可以考慮將這些無用的點移動到可行域中，或者刪除這些點，然后在可行域中重新生成。假設在二維設計空間中產生m個樣本點，m個樣本點中有t個點滿足約束條件，其中t

為了重新生成新的點，強調了兩個不可忽略的方面，即投影性和空間填充性。

（1）投影特性：為了在所有維度上滿足這一特性，以x1軸為基準方向。選擇上述最大距離值所在的相鄰兩點，并將第t+1個點沿x1方向放置在這兩點的1∕2處，同時在D中重新排列d′，重新生成新的距離集。重復這個過程，直到所有剩余點在X1方向上都被固定，其中接下來，確定這些新點在x2軸方向上的坐標，具體過程如下。

（2）空間填充性：確定點在x2軸方向的坐標時，以第t+1個點為例，由于其在x1方向的坐標已經確定，在x2方向上以步長λ搜索從0到約束邊界的最佳位置。在每次迭代中，計算特征值，特征值是待定的可能采樣點與前面已經產生的樣本點之間歐式距離的最小值。然后在可行域的x2軸方向上選擇最大特征值所在的位置。因此，該位置是x2軸方向上的點t+1的坐標。此時點t+1的位置已經確定Xnew=｛X1，X2，…，Xt，Xt+1｝，重復這個過程直到所有的點都被固定，X得以更新Xnew=｛X1，X2，…，Xt，Xt+1…Xm｝。

SLE-CLHS算法的n維（n>2）采樣過程與二維類似，都能較好地滿足空間填充性和投影特性。

3.2 SLE-CLHS算法的實例演示

SLE-CLSH策略可用一個實例來詳細演示運行步驟。

假設要在二維空間可行域內產生5個樣本點，可行域的數學表達式為：

則用SLE-CLSH的采樣過程可以詳細描述如下：

用maxmin-LHS方法在整個空間內產生5個樣本點。

由圖2可以看出，點p2和p4落在了可行區域外部。

圖2 用MaxminLHS方法在空間取5個樣本點Fig.2 Sampling 5 Points by MaxminLHS

由于p2和p4為無效點，所以將其刪除，并將要在可行域內產生2個新點p′2和p′4，這兩個新點要充分滿足試驗設計抽樣的空間填充性和投影特性。首先，計算點與點間的橫坐標間隙。由圖2可知，從左邊界至右邊界，點的橫坐標間距分別為1.5、1、2和0.5，所以為了滿足投影特性，將第一個新點p′2定在點p1和p3的1∕2處，橫坐標3.5的位置，接下來確定該點在下一維度的位置。

（3）現已得p′2的橫坐標為3.5，對于縱坐標的位置，我們從縱坐標為0到可行域邊界區間，以步長λ進行搜索，在每一步搜索中計算該位置的特征值，直至搜索完畢后，取特征值的最大值所在的位置為p′2點所在的縱坐標的位置。上文已經提到，特征值為該位置與已經產生的樣本點之間的歐式距離的最小值。

（4）重復步驟（2），（3）中p′2點的確定過程，可得到p′4點在該可行域內的位置。如圖3所示。

圖3 用SLE-CLHS方法在可行域內取5個點Fig.3 Sampling 5 Points in Constrained Space Using SLE-CLHS Method

4 數值案例

本節分別給出了SLE-CLHS算法在二維和三維設計空間的三個數值實例，案例中的約束都是正則凸約束。

4.1 二維空間的正則凸約束

式（7）定義了這個例子的設計空間。

它的可行域實際上是一個具有組合線性約束的不規則區域。如果要在可行域內產生5個樣本點，常規方法，如圖4所示。該方法消除了三個不滿足條件的點，剩下5個點。對于新方法，直接使用SLE-CLHS方法在可行域中產生5個樣本點，如圖5所示。參數x1在水平軸上繪制，參數x2在垂直軸上繪制。用LHS和SLE-CLHS方法進行采樣的樣本點的Φ值的比較，如表1所示?？梢钥闯鯯LE-CLHS方法在可行域所得到的Φ值比常規的方法小，即樣本點在可行域的分布更加均勻。

圖4 隨機LHS方法在可行域內采樣Fig.4 Normal Sampling in Constrained Space

圖5 SLE-CLHS算法在可行域內采樣Fig.5 SLE-CLHS Sampling in Constrained Space

表1 SLE-CLHS和LHS兩種取樣方法的Φ值比較Tab.1 Comparison of SLE-CLHS and LHS onΦ

4.2 三維球體的1/8約束空間

對于規則的三維可行域，在此以三維球體的1∕8空間為例，如圖6所示。

圖6 用常規方法和SLE-CLHS方法在1∕8球體內采樣Fig.6 Sampling in 1∕8 Sphere Space by Normal Method and SLE-CLHS

這是一個規則的設計空間，根據圖6所示的曲面約束空間，分別用常規的Maxmin-LHS抽樣方法及SLE-CLHS方法取10個樣本點。約束空間表達式，如式（8）所示。

由圖6可以看到，用常規的Maxmin-LHS抽樣方法所抽取的10個樣本點中，只有5個樣本點落在可行域內，這就造成了取樣時間的浪費，以及試驗盲目性，不能迅速得到有效的結果。

而SLE-CLHS方法取的10個樣本點全部位于三維約束區域內部，并擁有著良好的空間填充性和投影特性，能同時節約取樣時間和得到精確的樣本點數目，并且有良好的取樣效果。

4.3 三維空間的不規則凸約束

但是在實際的工程應用中，變量之間的耦合更多是多變的，所形成的可行域也是不規則的，這也給約束試驗設計方法的研究帶來了很大的挑戰。在此以三維空間的不規則可行域為例進行樣本點選取。三維的不規則約束空間中，凸約束邊界條件為：

分別用常規的Maxmin-LHS抽樣方法及SLE-CLHS方法在可行域內采樣產生15個樣本點。

由圖7可以看到，用Maxmin-LHS抽樣方法選取的樣本點部分落在了空間可行域外部，很難控制取樣個數。而用SLE-CLHS方法的選取結果比較滿意，在較好地滿足了空間填充性和投影特性的同時，保證了取樣效率，降低了試驗成本。

圖7 在不規則三維可行域內采樣Fig.7 Sampling in Irregular Convex Constrained Space

5 結論

針對現有的無約束空間的取樣方法連續局部枚舉拉丁超立方取點，提出了一種適用于約束空間的連續局部枚舉拉丁超立方體取樣（SLE-CLHS）方法。所提出的SLE-CLHS方法重點考慮了樣本變量之間的約束，并在這些約束構成的約束空間中進行有效取點。

在設計過程中，先剔除不滿足約束條件的點，然后在可行域中確定新樣本點的方向，并以一定的步長進行迭代直到達到最優位置。通過3個數值案例對SLE-CLHS方法進行演示與驗證，并利用maximin準則的量化值?p，與隨機LHS進行取樣對比，結果表明SLE-CLHS能取得更小的?值，說明SLE-CLHS取得的樣本點比隨機LHS取得的樣本點具有更好的空間填充性能和投影性能，且SLE-CLHS方法能夠在約束空間中進行有效取點。

SLE-CLHS方法仍存在一定的不足，如在低維設計空間和樣本點個數較少的情況下性能優異，但是隨著維度和樣本點數增加，其采樣效率會相應降低。在以后的工作中，將對所提出的SLE-CLHS算法進行改進，提高其取樣效率，使其能夠高效便捷的運用到更高維空間中。