智能虛擬布局設計關鍵技術研究與運用

宗立成，余隋懷，胡志剛

西北工業大學 機電學院 工業設計研究所，西安 710072

虛擬設計（Virtual Design）是20世紀90年代發展起來的研究領域，是基于虛擬現實技術的CAD設計方法。虛擬設計利用虛擬環境中豐富的交互式手段對計算機模型進行修改和實時數據反饋。虛擬布局設計中，建立布局對象與布局空間虛擬模型，借助直觀的虛擬現實交互工具，設計師可以沉浸在虛擬布局環境中實時與虛擬場景交互，直接將待布物虛擬模型布置在虛擬空間中，布局設計將呈現動態感知。傳統布局設計需要經過計算，才能獲得布局方案，不具有交互性和動態修改性，虛擬布局通過虛擬現實技術可以實時看到布局立體效果，通過及時反饋和修改參數，實現布局優化設計的可視化。加拿大Alberta大學Liang與green[1]開發的JDCAD系統通過三維操作進行幾何造型設計研究，在三維形狀草圖繪制方面獲得一定成果。NASA（美國國家航空宇航局）最早借助虛擬設計技術對航空器進行布局、設計以及分析[2]。Smith等[3]采用三維交互式虛擬設計對制造業設備布局提出布局方案。Korves和Iqbal[4]分別利用虛擬設計技術求解工廠布局問題。周前祥[5]以虛擬布局場景實現實驗參數設置，針對航天器座艙提出布局工效學實驗系統。查建中教授[6]在虛擬環境下建立了布局模型機器人機交互接口，實現了三維布局問題求解的人機結合性。王少梅[7]使用MultiGenCreater軟件，建立碼頭場景中三維模型的數據并開發了碼頭布局軟件，實現碼頭動態布局設計。利用虛擬設計技術進行布局問題的研究是布局問題求解的方向之一。

1 智能化布局問題建模

計算智能技術的發展將極大促進布局問題的研究?，F代學術研究已經證明布局問題具有NP難度，在有限的時間內很難獲得最優解，啟發式算法的出現和發展就證明了這點。啟發式算法利用專家經驗和知識，建立規則集指導計算機在解的空間域搜索滿意解，而并非最優解。目前，鑒于布局問題的復雜性、約束性和建模困難等特點，智能計算技術被廣泛采用。其中包括遺傳算法、模擬退火算法、小生境技術、序列三元組編碼等。

模擬退火算法具有一定的概率落入局部最優的陷阱中，但經過足夠長的時間也可以收斂到全局最優解。任何算法都有其缺陷和不足，為了避免模擬退火算法的局部最優陷阱，引入人機交互模塊，通過虛擬環境，實時的人機交互技術可以指導算法優化方向，避免落入局部最優。其質量和效率受三方面因素的影響。（1）初始溫度。初始溫度的選擇在一定程度上會使布局方案落入局部最優陷阱中或增加計算時間無法忍受。（2）溫度下降系數。在實際的物質退火狀態中，降溫過程是緩慢進行的，在算法中也同理，每步降溫值太小會造成計算時間過長，每步降溫值過大，則不能獲得較好的解。（3）循環次數。循環的目的是為了改善目標函數值，因此，在允許的時間內應盡量增大算法的循環次數，以保證獲得最優解。

2 基于智能虛擬技術的規則物體布局設計關鍵技術

布局問題的研究具有廣泛的工程應用背景。自1831年Gauss（高斯）對Lattice（格）裝填問題的研究開始，經過幾代人的努力，目前對布局問題的研究初見成效。縱觀現有文獻資料，布局問題可以分為一維、二維、三維布局問題。根據研究內容，布局問題又可細分為切段問題和裝填問題，其中裝填問題按照研究理論體系分為規則圖形裝填和不規則圖形裝填，本文所研究的就是規則圖形裝填布局問題。

2.1 虛擬設計建模

布局問題的研究發展到目前為止，已經不單單局限于數學角度和數學模型求解，傳統的單獨采用計算機求解布局優化問題往往很難以獲得優化解。隨著虛擬現實技術的發展，特別是虛擬設計技術的發展，可以將專家領域的知識、經驗引入到智能虛擬布局設計問題中，使專家、設計師從繁瑣的計算和操作工作中解脫出來，系統地融入到虛擬設計進程中，充分發揮專家的知識、經驗和關鍵決策作用。

虛擬現實技術為虛擬設計研究提供保障，虛擬現實具有交互性、沉浸感和想象性，設計師在虛擬環境中是主動參與者，通過虛擬現實技術將復雜、抽象的計算機模型數據空間直觀地表現出來。設計師通過數據手套等輸入設備在虛擬環境中操作待布設備，每步操作后經過計算機系統處理，設計師可以通過三維頭盔或數字眼鏡等輸出設備看到虛擬環境中設備的布局結果，這種顯示狀態是實時反饋的。虛擬布局設計將設計師實時融入布局設計和優化進程中，設計師在三維狀態下，可以自由地觀察、操作、干涉、修改布局狀態，這種人機交互式的布局方法可以更快地獲得最優設計方案，避免算法的缺陷，最終獲得優化布局方案。

圖1 虛擬設計系統架構

基于專家系統的虛擬布局設計方法求解復雜布局問題，將成為復雜布局問題自動化求解的發展方向。

2.2 規則圖形布局問題及其編碼

2.2.1 規則圖形布局問題

規則圖形裝填問題是布局領域研究較多的方面，在實際工程中，絕大多數不規則物體的布局問題都可以轉化為規則圖形進行布局優化設計，這也是解決復雜不規則產品布局問題的有效方法。

Beasley[8]利用數學規劃法對矩形裝填問題進行求解，但由于受限于算法只可解中等規模的裝填問題。Younis[9]提出了一種0-1混合集成規劃公式，對若干不同矩形進行布局。Tam[10]等通過啟發式算法，利用專家或設計師知識和經驗來解決矩形布局問題。隨著計算機信息技術的發展，近年來計算智能技術也被大量應用于矩形布局問題中。Georgis[11]等提出了自適應搜索算法的模擬退火法，在允許的時間內，對布局問題進行求解。黃文奇等[12]通過擬物和擬人思路，給出了圓形裝填問題的啟發式算法。陸一平等[13]提出膨脹裝填布局的策略，通過施加膨脹-排斥操作，實現自動產生布局位置，具有較強的直觀性和集聚性。

本文討論的是規則矩形塊布局優化問題，多種矩形塊物品裝填問題的定義為：給定一個約束寬度為W，長為L，高位H的裝填空間K和N種不同類的待布物品A1，A2，A3，…，An，第i(i=1,2,…,n)種物品有 Mi個，第i種待布物的尺寸為ti×ri×pi。求解待布物在K空間中的最優裝填方案，使其在滿足約束條件的情況下空間占用率最高，用在機械產品布局問題上，就是產品組合優化在滿足約束條件的情況下，占用空間最小，即消耗材料最小、造價最低、運輸最方便等。

規則圖形裝填問題的研究在機械產品、大規模集成電路、建筑物布局、工廠場地布局、工裝平臺等方面具有廣泛的工程應用背景。

2.2.2 序列三元組編碼

陸一平在《三維矩形塊布局的序列三元組編碼方法》一文中，已經證明序列三元組編碼方法在求解三維矩形裝填問題的P-Admissible的，因此本文不再對此進行論述。

序列三元組編碼方法在求解矩形塊布局問題是，其組合數為(n!)3，即是4個待布物體，組合數也達到13 824次。當布局物體規模增大時，組合爆炸不可避免。因此，結合模擬退火算法，對布局問題進行數學建模。

本文采用模擬退火思路進行編碼，具體描述如下：將待布物編號為1,2,…,n；將待布物編號的一個次序排列即為序列Γ=k1,k2,…,kn，使用三個相互獨立的序列組成三元組(Γ1,Γ2,Γ3)來表述裝填優化的解空間。

為了更好地理解三元組的編碼思路和方便后期算法求解，進行如下定義：

定義1使用二值矩陣Z表示序列Γ：

式中，Z為n×n的二值矩陣，即aii只能取0或1；如果在序列 Γ中，編號 j在i之后，則aij=1，否則aij=0，并規定在序列Γ中，所有對角線元素都為0。

定義2在n×n的二值矩陣中，會出現以下情況：

Pij的取值為 0或 1；對角線元素 Pii=0 ；Pij?Pji=0 ；Pik=1且 Pkj=1，則一定有 Pij=1。

定義3在n×n的二值矩陣中，如果所有元素都為1，那么為滿矩陣，記為F；如果對角線元素為1，而其余元素為0，那么為單位矩陣，記為I。

定義4如果三個部分序列P1，P2，P3，P1+P2+P3+(P1+P2+P3)′=F-I ，則稱P1，P2，P3是正交的。

定義5如果三個部分序列P1，P2，P3使得P1+P2+P3是序列，則稱P1，P2，P3是序列的三元分解。

定理1如果A1，A2，A3是序列矩陣，則如下矩陣G1，G2，G3是序列的三元分解：

定理2如果G1，G2，G3是序列的三元組，且G1+G2，G2+G3，G3+G1是部分序列，則必有三個序列A1，A2，A3，通過定理1的計算得出G1，G2，G3。

采用三元組(Γ1,Γ2,Γ3)對優化布局問題進行編碼，譯碼過程如下：

將三元組 (Γ1,Γ2,Γ3)表述成序列矩陣（A1，A2，A3），按照定理1求解出序列三元解G1，G2，G3，使其產生G1，G2，G3約束下的裝填空間所占用的三度長度L1，L2，L3，優化目標函數即裝填空間的體積，V=L1×L2×L3。

在三元組序列中，任何一個裝填布局都可以適用序列三元分解為G1，G2，G3表達，而且，任何一個序列的三元分解可以通過序列三元組(Γ1,Γ2,Γ3)獲得，通過上述方法譯碼的三元組編碼所構成的解空間中一定包含了裝填塊布局的優化解。

代碼反求譯碼過程如下：

計算人工移動后視圖的序列三元分解G1，G2，G3。由定理2，可以得到布局方案的三個序列矩陣A1，A2，A3。

由序列矩陣A1，A2，A3，逆向求解當前模型對應的序列三元組 (Γ1,Γ2,Γ3)。

2.3 模擬退火算法策略

模擬退火算法具有良好的尋優性和跳出局部最優陷阱能力，其中初始溫度、溫度下降系數和循環次數的設定會影響算法的質量效率。在本文中，模擬退火算法的優化目標函數表述如下：

式中，n為待布物體的數量，Vi是第i個待布物體的體積，VBB為布局后包圍盒的體積，VBB=l×b×h。

接受概率函數表述如下：

式中，Δ=Fnew-Fcurrent，Fnew為新狀態下的目標函數值，Fcurrent為當前狀態下的目標函數值。

3 智能虛擬布局設計系統構建

基于虛擬現實的虛擬布局設計方法，提出了虛擬環境下利用三元組編碼和模擬退火算法求解規則布局問題。設計師通過虛擬設備進入虛擬環境中，實現傳統布局設計算法所不具備的實時反饋和觀察算法進程及布局算法的搜索方向，同時借助數據手套對待布物或待布容器進行操作，經過算法代碼反求，獲得當前狀態下布局狀態編碼，進行優化計算。如此循環進化獲得目標函數值最優，最終布局方案最優。智能虛擬布局與傳統布局方法不同在于優化計算過程的人機結合性，傳統算法只能在獲取計算方案之后，進行評價，智能虛擬布局方法直接將專家知識、經驗以及評價融入在優化設計進程中，最終獲得方案具有最優性。算法流程如圖2。

圖2 虛擬與傳統布局設計流程圖

4 布局實例

以某型號整合機柜為例，待布設備n為4，終止條件為達到最大循環次數（本例取100）或空間利用率大于0.90。

初始溫度設定T0=10 000，線性降溫系數DT=1.0，初始序列三元組隨即產生，進行求解，詳細待布設備參數見表1和表2，表3為詳細布局結果參數。

表1 待布設備參數

由于待布設備不是規則圖形，為了計算方便，對待布設備進行規則轉化。待布設備最終需要互不干涉的布置與機柜內部，因此，進行矩形轉化并不會影響布局方案計算，反而會加快計算進程。詳細參數見表2。

經過計算求解，獲得近似優化解和中間解，如圖3所示。根據求解獲得的最優布局方案，將各待布設備進行布置安放，進入詳細設計階段，經詳細設計階段，最終獲得機柜產品最終效果圖，如圖4所示。

5 結束語

智能虛擬布局設計為布局設計提供了新的發展方向和研究方法，使得設計師可以將自身知識和長期積累的經驗系統地融入布局優化進程中，根據實時交互和反饋控制優化設計方向，最終獲得的解具有最優性。智能虛擬設計方法有效地避免傳統的數學計算方法在求解布局問題時的局限性，借助虛擬現實技術，實現布局優化設計的虛擬三維顯示。本文在采用序列三元組編碼和模擬退火算法策略的基礎上，對布局問題進行智能虛擬設計，根據布局實例顯示，本方法具有很好的發展前景，實時的人機交互也為布局方案評價奠定基礎。在實際工程中，規則圖形布局比較常見，不規則布局也可以借助一定的方法轉化為規則布局問題進行建模求解，但有些特殊復雜產品布局，會受性能約束限制，轉化為規則圖形會影響其布局方案最優性，因此，建議在本文的基礎上對不規則復雜產品布局設計問題進行繼續研究。

表2 待布設備詳細信息

表3 布局結果詳細參數

圖3 布局結果

圖4 最終布局方案效果

[1]Liang J，Green M.JDCAD：a highly interactive 3D modeling system[J].Computers&Graphic，1994，18（4）：499-506.

[2]Bryson S，Levit C.The virtual wind tunnel[J].IEEE CG&A，1992，12（4）.

[3]Smith R P，Heim J A.Virtual facility layout design：the value of an interactive three-dimensional representation[J].International Journal of Production Research，1999，37（17）：3941-3957.

[4]Lqbal M，Hashmi M S J.Design and analysis of a virtual factory layout[J].Journal of Materials Processing Technology，2001，118（1）：403-410.

[5]周前祥，陳善廣，姜國華，等.航天器座艙布局功效學仿真實驗系統—虛擬座艙的研究[J].系統仿真學報，2001，13（3）：291-293.

[6]唐曉君，查建中，陸一平.基于虛擬現實的人機結合方法及其在布局中的應用[J].機械工程學報，2003，39（8）：95-100.

[7]張煜，王少梅.虛擬現實技術在碼頭布局設計中的應用[J].計算機工程與設計，2006，27（23）：421-423.

[8]Beasley J E.An exact two-dimensional non-guillotine cutting tree search procedure[J].Operational Research，1985，33：49-64.

[9]Younis N A，Cavalier T M.On locating part bins in a constrained layout area for an automated assembly process[J].Computers&Industrial Engineering，1990，18（2）：111-118.

[10]Tam Y，Wu Yuliang，Huang Wenqi，et al.Effective quasi-human based heuristic for solving rectangle packing problem[C]//IEEE Asia-Pacific Conference on Circuits and Systems-Proceedings，1998：137-140.

[11]Georgis N，Petrou M，Kittler J.On the constrained rectangle packing problem[J].International Journal of Modeling and Simulation，2000，20（4）：293-299.

[12]黃文奇，許如初.支持求解圓形packing問題的兩個擬人策略[J].中國科學：E輯，1999，29（4）：347-353.

[13]陸一平，查建中.求解裝填布局問題的膨脹算法[J].計算機學報，2001，24（10）：1077-1084.