智能虛擬布局設(shè)計(jì)關(guān)鍵技術(shù)研究與運(yùn)用

宗立成，余隋懷，胡志剛

西北工業(yè)大學(xué) 機(jī)電學(xué)院 工業(yè)設(shè)計(jì)研究所，西安 710072

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

1 智能化布局問(wèn)題建模

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

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

2 基于智能虛擬技術(shù)的規(guī)則物體布局設(shè)計(jì)關(guān)鍵技術(shù)

布局問(wèn)題的研究具有廣泛的工程應(yīng)用背景。自1831年Gauss（高斯）對(duì)Lattice（格）裝填問(wèn)題的研究開(kāi)始，經(jīng)過(guò)幾代人的努力，目前對(duì)布局問(wèn)題的研究初見(jiàn)成效?？v觀現(xiàn)有文獻(xiàn)資料，布局問(wèn)題可以分為一維、二維、三維布局問(wèn)題。根據(jù)研究?jī)?nèi)容，布局問(wèn)題又可細(xì)分為切段問(wèn)題和裝填問(wèn)題，其中裝填問(wèn)題按照研究理論體系分為規(guī)則圖形裝填和不規(guī)則圖形裝填，本文所研究的就是規(guī)則圖形裝填布局問(wèn)題。

2.1 虛擬設(shè)計(jì)建模

布局問(wèn)題的研究發(fā)展到目前為止，已經(jīng)不單單局限于數(shù)學(xué)角度和數(shù)學(xué)模型求解，傳統(tǒng)的單獨(dú)采用計(jì)算機(jī)求解布局優(yōu)化問(wèn)題往往很難以獲得優(yōu)化解。隨著虛擬現(xiàn)實(shí)技術(shù)的發(fā)展，特別是虛擬設(shè)計(jì)技術(shù)的發(fā)展，可以將專(zhuān)家領(lǐng)域的知識(shí)、經(jīng)驗(yàn)引入到智能虛擬布局設(shè)計(jì)問(wèn)題中，使專(zhuān)家、設(shè)計(jì)師從繁瑣的計(jì)算和操作工作中解脫出來(lái)，系統(tǒng)地融入到虛擬設(shè)計(jì)進(jìn)程中，充分發(fā)揮專(zhuān)家的知識(shí)、經(jīng)驗(yàn)和關(guān)鍵決策作用。

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

圖1 虛擬設(shè)計(jì)系統(tǒng)架構(gòu)

基于專(zhuān)家系統(tǒng)的虛擬布局設(shè)計(jì)方法求解復(fù)雜布局問(wèn)題，將成為復(fù)雜布局問(wèn)題自動(dòng)化求解的發(fā)展方向。

2.2 規(guī)則圖形布局問(wèn)題及其編碼

2.2.1 規(guī)則圖形布局問(wèn)題

規(guī)則圖形裝填問(wèn)題是布局領(lǐng)域研究較多的方面，在實(shí)際工程中，絕大多數(shù)不規(guī)則物體的布局問(wèn)題都可以轉(zhuǎn)化為規(guī)則圖形進(jìn)行布局優(yōu)化設(shè)計(jì)，這也是解決復(fù)雜不規(guī)則產(chǎn)品布局問(wèn)題的有效方法。

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

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

規(guī)則圖形裝填問(wèn)題的研究在機(jī)械產(chǎn)品、大規(guī)模集成電路、建筑物布局、工廠場(chǎng)地布局、工裝平臺(tái)等方面具有廣泛的工程應(yīng)用背景。

2.2.2 序列三元組編碼

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

序列三元組編碼方法在求解矩形塊布局問(wèn)題是，其組合數(shù)為(n!)3，即是4個(gè)待布物體，組合數(shù)也達(dá)到13 824次。當(dāng)布局物體規(guī)模增大時(shí)，組合爆炸不可避免。因此，結(jié)合模擬退火算法，對(duì)布局問(wèn)題進(jìn)行數(shù)學(xué)建模。

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

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

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

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

定義2在n×n的二值矩陣中，會(huì)出現(xiàn)以下情況：

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

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

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

定義5如果三個(gè)部分序列P1，P2，P3使得P1+P2+P3是序列，則稱(chēng)P1，P2，P3是序列的三元分解。

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

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

采用三元組(Γ1,Γ2,Γ3)對(duì)優(yōu)化布局問(wèn)題進(jìn)行編碼，譯碼過(guò)程如下：

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

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

代碼反求譯碼過(guò)程如下：

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

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

2.3 模擬退火算法策略

模擬退火算法具有良好的尋優(yōu)性和跳出局部最優(yōu)陷阱能力，其中初始溫度、溫度下降系數(shù)和循環(huán)次數(shù)的設(shè)定會(huì)影響算法的質(zhì)量效率。在本文中，模擬退火算法的優(yōu)化目標(biāo)函數(shù)表述如下：

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

接受概率函數(shù)表述如下：

式中，Δ=Fnew-Fcurrent，F(xiàn)new為新?tīng)顟B(tài)下的目標(biāo)函數(shù)值，F(xiàn)current為當(dāng)前狀態(tài)下的目標(biāo)函數(shù)值。

3 智能虛擬布局設(shè)計(jì)系統(tǒng)構(gòu)建

基于虛擬現(xiàn)實(shí)的虛擬布局設(shè)計(jì)方法，提出了虛擬環(huán)境下利用三元組編碼和模擬退火算法求解規(guī)則布局問(wèn)題。設(shè)計(jì)師通過(guò)虛擬設(shè)備進(jìn)入虛擬環(huán)境中，實(shí)現(xiàn)傳統(tǒng)布局設(shè)計(jì)算法所不具備的實(shí)時(shí)反饋和觀察算法進(jìn)程及布局算法的搜索方向，同時(shí)借助數(shù)據(jù)手套對(duì)待布物或待布容器進(jìn)行操作，經(jīng)過(guò)算法代碼反求，獲得當(dāng)前狀態(tài)下布局狀態(tài)編碼，進(jìn)行優(yōu)化計(jì)算。如此循環(huán)進(jìn)化獲得目標(biāo)函數(shù)值最優(yōu)，最終布局方案最優(yōu)。智能虛擬布局與傳統(tǒng)布局方法不同在于優(yōu)化計(jì)算過(guò)程的人機(jī)結(jié)合性，傳統(tǒng)算法只能在獲取計(jì)算方案之后，進(jìn)行評(píng)價(jià)，智能虛擬布局方法直接將專(zhuān)家知識(shí)、經(jīng)驗(yàn)以及評(píng)價(jià)融入在優(yōu)化設(shè)計(jì)進(jìn)程中，最終獲得方案具有最優(yōu)性。算法流程如圖2。

圖2 虛擬與傳統(tǒng)布局設(shè)計(jì)流程圖

4 布局實(shí)例

以某型號(hào)整合機(jī)柜為例，待布設(shè)備n為4，終止條件為達(dá)到最大循環(huán)次數(shù)（本例取100）或空間利用率大于0.90。

初始溫度設(shè)定T0=10 000，線性降溫系數(shù)DT=1.0，初始序列三元組隨即產(chǎn)生，進(jìn)行求解，詳細(xì)待布設(shè)備參數(shù)見(jiàn)表1和表2，表3為詳細(xì)布局結(jié)果參數(shù)。

表1 待布設(shè)備參數(shù)

由于待布設(shè)備不是規(guī)則圖形，為了計(jì)算方便，對(duì)待布設(shè)備進(jìn)行規(guī)則轉(zhuǎn)化。待布設(shè)備最終需要互不干涉的布置與機(jī)柜內(nèi)部，因此，進(jìn)行矩形轉(zhuǎn)化并不會(huì)影響布局方案計(jì)算，反而會(huì)加快計(jì)算進(jìn)程。詳細(xì)參數(shù)見(jiàn)表2。

經(jīng)過(guò)計(jì)算求解，獲得近似優(yōu)化解和中間解，如圖3所示。根據(jù)求解獲得的最優(yōu)布局方案，將各待布設(shè)備進(jìn)行布置安放，進(jìn)入詳細(xì)設(shè)計(jì)階段，經(jīng)詳細(xì)設(shè)計(jì)階段，最終獲得機(jī)柜產(chǎn)品最終效果圖，如圖4所示。

5 結(jié)束語(yǔ)

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

表2 待布設(shè)備詳細(xì)信息

表3 布局結(jié)果詳細(xì)參數(shù)

圖3 布局結(jié)果

圖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]周前祥，陳善廣，姜國(guó)華，等.航天器座艙布局功效學(xué)仿真實(shí)驗(yàn)系統(tǒng)—虛擬座艙的研究[J].系統(tǒng)仿真學(xué)報(bào)，2001，13（3）：291-293.

[6]唐曉君，查建中，陸一平.基于虛擬現(xiàn)實(shí)的人機(jī)結(jié)合方法及其在布局中的應(yīng)用[J].機(jī)械工程學(xué)報(bào)，2003，39（8）：95-100.

[7]張煜，王少梅.虛擬現(xiàn)實(shí)技術(shù)在碼頭布局設(shè)計(jì)中的應(yīng)用[J].計(jì)算機(jī)工程與設(shè)計(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問(wèn)題的兩個(gè)擬人策略[J].中國(guó)科學(xué)：E輯，1999，29（4）：347-353.

[13]陸一平，查建中.求解裝填布局問(wèn)題的膨脹算法[J].計(jì)算機(jī)學(xué)報(bào)，2001，24（10）：1077-1084.