基于蒙特卡羅方法的矩形布局問題研究

鄭榮杰， 張鵬程， 崔海良， 李國(guó)順， 羅海兵， 劉昕彤

（河北工程技術(shù)高等專科學(xué)校，河北 滄州 061001）

矩形布局[1]是在矩形的邊與布局空間邊界平行的情況下，將其不相嵌地放入布局空間中，同時(shí)達(dá)到空間排布的最優(yōu)化。這一問題屬于布局問題的一個(gè)子問題。它在機(jī)械設(shè)計(jì)與制造、交通運(yùn)輸、大規(guī)模集成電路設(shè)計(jì)等領(lǐng)域有著廣泛的應(yīng)用，是當(dāng)前CAD/CAM研究的熱點(diǎn)問題之一[2]。

布局問題作為具有NP-hard的最優(yōu)組合問題，在有限的時(shí)間內(nèi)一般無法獲得全局最優(yōu)解[3]。對(duì)其求解只能依賴于各種啟發(fā)算法，其中構(gòu)造式啟發(fā)方法應(yīng)用最廣[4]。使用構(gòu)造式方法求解矩形布局，其過程分為定序和定位兩步:定序規(guī)則確定矩形布入的次序，定位規(guī)則確定矩形布入位置。矩形可行域是指待布矩形在布局空間中所有可行位置的集合。近來，研究發(fā)現(xiàn)結(jié)合矩形可行域制定定序規(guī)則和定位規(guī)則，可以使矩形布局過程更靈活，算法的自適應(yīng)性更強(qiáng)[4]。

隨著矩形布入，布局空間的邊界發(fā)生變化，邊界的形狀變得復(fù)雜。確定此類空間中矩形可行域成為一個(gè)難題。考慮到蒙特卡羅方法研究非確定性問題的優(yōu)勢(shì)[5]，我們將其引入到于矩形可行域研究，最終得到了有意義的結(jié)果。

1 蒙特卡羅方法

蒙特卡羅方法[6]，是一種根據(jù)統(tǒng)計(jì)抽樣理論近似求解數(shù)學(xué)物理問題的計(jì)算機(jī)模擬方法，已廣泛應(yīng)用于金融工程學(xué)，宏觀經(jīng)濟(jì)學(xué)，生物醫(yī)學(xué)，計(jì)算物理學(xué)等領(lǐng)域。對(duì)于確定性問題，其基本思想是：建立一個(gè)與所求解有關(guān)的概率模型，基于這個(gè)模型進(jìn)行隨機(jī)抽樣；通過對(duì)隨機(jī)抽樣進(jìn)行統(tǒng)計(jì)，得到概率模型的分布或數(shù)學(xué)期望作為近似解。對(duì)于非確定性問題，蒙特卡羅方法則無需將非確定性問題轉(zhuǎn)化為確定問題再求解，而是直接從非確定性問題出發(fā)，通過模擬問題的實(shí)際過程得到問題的解?？紤]到布局問題具有非確定性,采用蒙特卡羅方法對(duì)矩形布局過程進(jìn)行直接模擬，可以獲得一種有效的布局方案。

2 矩形可行域

矩形可行域是指矩形在布局空間中所有可行位置的集合。在規(guī)則的布局空間中，矩形的可行域?yàn)榫匦窝夭季挚臻g邊界移動(dòng)時(shí)，矩形的中心形成的封閉軌跡占據(jù)的區(qū)域。如圖1所示，長(zhǎng)為2，寬為1的矩形在邊長(zhǎng)為5的正方形中沿邊界移動(dòng)，得到多邊形占據(jù)的區(qū)域即為矩形可行域。

圖1 正方形布局空間中矩形的可行域

隨著矩形布入，剩余布局空間的邊界發(fā)生變化，成為不規(guī)則的布局空間。對(duì)于此類布局空間，可行域不能由矩形沿著空間邊界移動(dòng)直接得到。如圖2所示，在布局空間左下角布入一個(gè)矩形后，下一個(gè)矩形在沿剩余布局空間邊界移動(dòng)時(shí)，位于位置1時(shí)滿足邊界條件；位置2時(shí)，則不符合。

如何得到不規(guī)則布局空間中符合邊界條件的可行域是計(jì)算可行域的難點(diǎn)。王金敏等提出偏移多邊形法，利用布局空間頂點(diǎn)的坐標(biāo)及布局矩形的尺寸關(guān)系進(jìn)行比較得到矩形可行域的邊界[7]。此方法較好的解決了這一問題，但在計(jì)算可行域邊界時(shí)，算法較為復(fù)雜。本文使用蒙特卡羅方法控制矩形在布局空間中移動(dòng)，由邊界條件限制矩形布局的范圍，可行域的邊界自動(dòng)滿足布局空間邊界條件，簡(jiǎn)化了可行域邊界的確定過程。

圖2 剩余布局空間中矩形的可行域

3 矩形可行域求解算法及步驟

使用蒙特卡羅方法確定矩形可行域的步驟如下：

1）將布局空間劃分成若干個(gè)格子。

2）確定矩形在布局空間的初始分布。依次在布局空間的頂點(diǎn)上設(shè)置滿足邊界約束條件的矩形，使得矩形可以到達(dá)布局空間的任何區(qū)域。

3）布局空間中，矩形按照蒙特卡羅法得到的隨機(jī)步長(zhǎng)沿水平或垂直方向做試探移動(dòng)；同時(shí)矩形的移動(dòng)需滿足布局空間的邊界條件。

4）統(tǒng)計(jì)滿足布局空間邊界條件的矩形中心分布位置。

5）根據(jù)矩形中心的分布位置得到矩形可行域。

下面給出了不規(guī)則布局空間中矩形可行域的求解實(shí)例。如圖3所示，布局空間是一個(gè)不規(guī)則多邊形，在x軸上位于區(qū)間[0,20]，y軸上位于區(qū)間[0,16]內(nèi)。待布矩形是長(zhǎng)為4，寬為2的矩形。為了保證矩形可以到達(dá)布局空間的任何位置，矩形在布局空間中初始位置需要滿足條件：矩形至少有一條邊和一個(gè)頂點(diǎn)分別與不規(guī)則多邊形的邊和頂點(diǎn)重合，并且位于布局空間內(nèi)。如圖2中所示，虛線構(gòu)成的陰影矩形作為矩形的初始位置。

圖3 不規(guī)則布局空間及矩形的一些初始分布位置

矩形按照蒙特卡羅方法產(chǎn)生的隨機(jī)步長(zhǎng)在布局空間中沿水平或垂直方向試探移動(dòng)。如果矩形在試探移動(dòng)后，仍位于布局空間內(nèi)，則記錄此時(shí)矩形中心的位置；否則不記錄，做下一次試探移動(dòng)。統(tǒng)計(jì)矩形的中心在布局空間中分布區(qū)域，即得到如圖4所示的矩形可行域。圖4中的點(diǎn)、直線以及閉合曲線占據(jù)的區(qū)域即為矩形可行域。其中，點(diǎn)表示此處只存在一種矩形的放置方式；直線表示矩形的中心可以沿著此直線運(yùn)動(dòng)。圖中閉合曲線圍住的區(qū)域表示矩形中心可在此區(qū)域內(nèi)運(yùn)動(dòng)。

圖4 矩形在布局空間中的可行域

顯然，通過蒙特卡羅方法移動(dòng)的矩形，自動(dòng)滿足布局空間的邊界條件；得到的可行域邊界必然同樣符合布局空間邊界約束。該方法在模型及算法上較傳統(tǒng)方法更為直觀，簡(jiǎn)單。

4 實(shí)例分析

利用蒙特卡羅方法確定矩形可行域，采用王金敏提出的定位函數(shù)及吸引子方法進(jìn)行矩形的定位，從而完成矩形的布局過程[4]。定位函數(shù)的具體形式為

采用java語言完成了自動(dòng)布局系統(tǒng)的設(shè)計(jì)。在Pentium(R) Dual-Core (2G/2.5GHz)微機(jī)上，測(cè)試了 http://people.brunel.ac.uk/～mastjjb/jeb/orlib/files/strip3.xls下載的實(shí)例數(shù)據(jù)，驗(yàn)證了本算法的有效性。在圖5中，給出了strip3.xls文件的T1表中兩例17個(gè)矩形在布局空間中的典型測(cè)試結(jié)果。圖6為矩形占據(jù)布局空間的比例隨著布入矩形數(shù)的變化規(guī)律。在實(shí)例1中矩形最終占據(jù)布局面積比例為91.653%，實(shí)例2中為91.368%。結(jié)果顯示，使用蒙特卡羅方法得到的矩形可行域，應(yīng)用于矩形布局時(shí)，可以達(dá)到較好的布局效果。

圖5 實(shí)例中矩形的布局結(jié)果

圖6 矩形占據(jù)布局空間比例與布入矩形數(shù)的關(guān)系

5 結(jié) 論

本文基于蒙特卡羅方法研究矩形布局問題。使用蒙特卡羅方法控制矩形在布局空間中移動(dòng)，由邊界條件限制矩形布局的范圍，得到的可行域邊界自動(dòng)滿足布局空間邊界約束。結(jié)合定位函數(shù),最終獲得了良好的布局結(jié)果。該方法很大程度上簡(jiǎn)化了可行域邊界的確定過程，最終提高了布局算法的效率。

使用蒙特卡羅方法確定矩形的可行域，計(jì)算過程只受布局空間邊界約束，與待布矩形的形狀和位置無關(guān)，所以在確定邊界條件的前提下，該方法可擴(kuò)展應(yīng)用于矩形、三角形和圓形的混合布局問題。

[1]Dowsland K A, Dowsland W B. Packing problem [J].European Journal of Operational Research, 1992,56(1): 2-14.

[2]Sweeney P W, Paternoster E R. Cutting and packing problem: a categorized application-orientated research [J]. Journal of Operation Research Socity,1992, 43(7): 691-706.

[3]王金敏, 喻宏波, 陳東祥, 等. 布局模裝系統(tǒng)的研究[J].工程圖學(xué)學(xué)報(bào), 2001, (1): 47-54.

[4]王金敏, 楊維嘉. 動(dòng)態(tài)吸引子在布局求解中的應(yīng)用[J].計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào), 2005, 17(8):1725-1730.

[5]馬海云, 齊小軍. 蒙特卡羅仿真機(jī)及其應(yīng)用[J]. 電腦與信息技術(shù), 2006, 14(3): 8-10.

[6]Metropolis N, Rosenbluth A W, Rosenbluth M N, et al.Equation of state calculations by fast computing machines [J]. J. Chem. Phys, 1953, 21: 1087.

[7]王金敏, 張鵬程, 朱艷華. 矩形布局可行域的確定[J].計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào), 2008, 20(2):246-252.