王金敏， 齊 楊

（天津職業(yè)技術(shù)師范大學(xué)天津市高速切削與精密加工重點實驗室，天津 300222）

矩形布局問題吸引子法研究

王金敏， 齊 楊

（天津職業(yè)技術(shù)師范大學(xué)天津市高速切削與精密加工重點實驗室，天津 300222）

吸引子法是布局定位函數(shù)中的一種，在解決布局問題中取得了較好的效果。論文的研究，獲得了吸引子法的一些基本性質(zhì)：諸如定位函數(shù)的三維圖像為一個平面、定位函數(shù)值相等的點共線、吸引子法使矩形塊堆積在一個角上等。此外，通過研究布入點的幾何意義，提出了一種手動快速布局方法。最后通過研究吸引子放置位置對布局的影響，還得出了隱性吸引子這一重要的性質(zhì)。

布局問題；啟發(fā)式算法；定位函數(shù)；吸引子法

矩形布局問題[1]廣泛地存在于工業(yè)生產(chǎn)實踐之中。長期以來，人們?yōu)榻鉀Q該問題提出各種理論和方法[2]，并取得了一定的效果。這些方法中最主要的有兩種[3]：優(yōu)化算法和啟發(fā)式算法。其中優(yōu)化算法只能找到局部最優(yōu)解，且所得解的質(zhì)量在很大程度上依賴于初始解的選擇[4]。于是人們將研究的重心轉(zhuǎn)向了啟發(fā)式算法[5],并提出了一系列求解算法，其中，構(gòu)造啟發(fā)算法是最常見的一種算法。構(gòu)造啟發(fā)算法主要由定序規(guī)則和定位規(guī)則確定[6]。常見的定序規(guī)則有按面積遞減、按最長邊遞減和按可行域面積等順序確定布局塊的布局次序。常見的定位規(guī)則有占角順放策略、金角策略、下臺階法和定位函數(shù)法等。吸引子法[7]是定位函數(shù)法中的一種。吸引子法吸收了下臺階法、BL算法等許多定位規(guī)則的優(yōu)點，并且其可量化的特點使其更容易在計算機上得到實現(xiàn)。

在對吸引子法的文獻(xiàn)檢索中，發(fā)現(xiàn)文獻(xiàn)都只注重對于吸引子法的應(yīng)用，如朱艷華[8]利用吸引子法結(jié)合遺傳算法求解二維布局問題；王保春[9]利用吸引子法與混合 SAGA算法結(jié)合求解矩形布局問題；而對吸引子法自身性質(zhì)的研究卻未見論述。

本文對吸引子法的基本內(nèi)容進(jìn)行推理研究，得出吸引子法的一些基本性質(zhì)，這將有利于吸引子法在矩形布局問題求解中得到更好地運用。

1 吸引子法趨角性研究

吸引子法的數(shù)學(xué)描述如下：

在空間中設(shè)置m個吸引子，吸引子t的位置為 ),(00ttyx 。矩形塊i在 ),(iiyx 處的定位函數(shù)

其中， ),(iityxg 是關(guān)于吸引子 t的定位函數(shù)，n為待布矩形塊的個數(shù)，tα、tβ和tω為權(quán)重因子，且令矩形塊的布入點 (xj,yj)是其可行域內(nèi)定位函數(shù)值最小的點，即 G (xj,yj)= minG(xi,yi)。因矩形塊要求完全布入空間內(nèi)，故定位函數(shù)的最大定義域為布局空間。

吸引子法在求解二維矩形布局問題時，通常會采用4個吸引子，分別布在矩形布局空間的四角。 ω1、 ω2、 ω3和 ω4分別為布局空間的左下、右下、右上和左上四角吸引子的權(quán)重因子。

現(xiàn)研究在定位函數(shù)中參數(shù) αt， βt和 ωt確定時，定位函數(shù)值在布局空間內(nèi)的變化情況。設(shè)對于某個任意點 (xi,yi)的定位函數(shù)值已知，則該點在X方向偏移 Δ x后所得點 (xi+ Δx,yi)（依然在布局空間內(nèi)）的定位函數(shù)為

因點 (xi,yi)與點 (xi+ Δx,yi)都在矩形布局空間內(nèi)，故存在 x01= x04≤ xi≤ x02= x03和x01= x04≤ xi+ Δx≤ x02= x03，其中，

同理可得

由式（2）、（3）可得

若取 xi=0,yi=0,Δx =x,Δy=y，可得 G(x ,y)=

需要說明的是，上式中 (xi,yi)所取的原點(0 ,0)一般選在布局空間左下角點，但根據(jù)情況也可選在其他點，該點的選取并不影響最終的布局結(jié)果。

由上式可知，當(dāng)吸引子的位置與參數(shù)值確定時, ω1α1? ω2α2?ω3α3+ω4α4， ω1β1+ω2β2?ω3β3? ω4β4和 G (0,0)都為常數(shù)。若設(shè)

G (0 ,0)=C，則上式可簡化為

由此方程可得出如下性質(zhì)：

性質(zhì)1 由各個點坐標(biāo) (xi,yi)與其定位函數(shù)值 G (xi,yi)所確定的三維點群 (xi,yi,G(xi,yi))在同一個平面內(nèi)，即在以布局空間所在平面為XOY平面、定位函數(shù)值為Z軸的三維空間內(nèi)，定位函數(shù)圖像為一個平面。

性質(zhì)2 在矩形布局空間內(nèi)，定位函數(shù)值相同的點在同一條直線上。

當(dāng)在這些點群中選出定位函數(shù)值 ),( yxG 最小的點作為矩形塊布入點時，此時問題已經(jīng)轉(zhuǎn)化成為一個二維線性規(guī)劃問題。該線性規(guī)劃問題可描述為

其中，iI為第i塊布入矩形塊的可行域。

因此矩形塊布入點的確定有許多與線性規(guī)劃問題相同的性質(zhì)和特點。

首先，由線性規(guī)劃的理論可知，線性規(guī)劃問題可能存在無限解[10]。同樣，可行域內(nèi)也可能存在多個甚至是無限個備選點。在理論上，這些點都可以成為矩形塊的布入點。但實踐的經(jīng)驗告訴我們，矩形塊布在中間位置往往得不到較好的布局結(jié)果，所以在定位原則中往往有“貼邊靠角”的特點。因此我們在此規(guī)定：當(dāng)有多個點可做布入點時，選擇這些點中最靠左或最靠下的點作為布入點，靠下的原則要高于靠左的原則。需要說明的是，這樣一個特別規(guī)定只是為了方便尋找布入點，而對吸引子法本身的性質(zhì)沒有任何影響，尤其是后面將提到的趨角性。事實上，矩形塊選擇備選點中的任何一點作為布入點都不影響其趨角性，趨角性是由后文所提到的隱形吸引子這個性質(zhì)所決定的。

其次，線性規(guī)劃最優(yōu)解的一個重要特征是最優(yōu)解總是發(fā)生在解空間的角點，且當(dāng)求目標(biāo)函數(shù)最小值時，最優(yōu)點出現(xiàn)于在等值線負(fù)梯度方向區(qū)域[10]。同樣，矩形塊的布入點也存在于其可行域的頂點之中。且當(dāng)A≥0，B≥0時，矩形塊的布入點存在于可行域的左下角區(qū)域；當(dāng) A≥0，B＜0時，矩形塊的布入點存在于可行域的左上角區(qū)域；當(dāng)A＜0，B＜0時，矩形塊的布入點存在于可行域的右上角區(qū)域；當(dāng)A＜0，B≥0時，矩形塊的布入點存在于可行域的右下角區(qū)域，如圖1所示。

最后，當(dāng)可行域不變時，目標(biāo)函數(shù)中價值系數(shù)的改變有可能導(dǎo)致解的變化[10]。同樣，矩形塊的可行域是固定的，而A和B卻可能隨吸引子參數(shù)變化而變化，故矩形塊的布入點在很大程度上取決于由吸引子決定的目標(biāo)函數(shù)中的價值系數(shù)A和B。

以上的性質(zhì)雖然是單個矩形塊布入點的特征，但是眾多矩形塊布入的積累效果使得吸引子法還存在以下性質(zhì)：

性質(zhì)3 吸引子法的布局結(jié)果會出現(xiàn)矩形塊堆積在一個角上的情況，而且根據(jù)A和B取值的不同，矩形塊堆積的角不同，堆積的狀態(tài)也不同。

可見在矩形塊布入順序確定的情況下，布局結(jié)果完全取決于A和B的取值，因此A和B是吸引子法的重要布局參數(shù)。

因為矩形布局問題的布局空間和矩形塊都是對稱的，所以任何一種布局情況，通過改變A和B的取值都可以出現(xiàn)于另外3個角上。故以下的分析中以左下角為主要研究對象，其他3個角的研究可參照該角。

圖1 價值系數(shù)確定矩形布入點所在區(qū)域

2 布入點的幾何意義

由研究可知，矩形塊堆積在布局空間的左下角區(qū)域時，A≥0，B≥0。

如圖2所示，設(shè)當(dāng)?shù)趇塊矩形塊布入時，可行域為 Ii（陰影部分），其中點 P (xj,yj)為矩形塊的布入點。此時由定位函數(shù)所確定的等值線為Ax + By+C'=0，該直線與水平線的夾角

若將可行域沿逆時針旋轉(zhuǎn)角度θ，如圖3所示，等值線經(jīng)過旋轉(zhuǎn)后成為水平線，則此時經(jīng)過旋轉(zhuǎn)后的矩形塊布入點 P'( x'j,y'j)為新可行域I'i內(nèi)的最低點，即 y'j= miny'i。

當(dāng)B=0時，等值線為 z = Ax+C'，等值線與水平線的夾角為 π /2。此時矩形塊布入點在可行域最左的邊界線段中，根據(jù)靠下的原則，矩形塊的布入點為該線段的下端點。若可行域沿逆時針旋轉(zhuǎn) π /2，可行域最左的邊界線段成為了新可行域中最下的邊界線段，新的矩形塊布入點依然為新可行域內(nèi)最低點。

同樣的性質(zhì)在其他3個角上也是成立的。但要注意的是，其他3個角需要旋轉(zhuǎn)的角度不一樣。右下角與左下角關(guān)于過布局空間中心點的垂直線對稱，故右下角要沿順時針旋轉(zhuǎn)角度θ，即沿逆時針旋轉(zhuǎn)角度2 π?θ ；而右上角與左下角關(guān)于布局空間中心點對稱，故右上角要沿逆時針旋轉(zhuǎn)角度π后再旋轉(zhuǎn)角度θ，即沿逆時針旋轉(zhuǎn)角度π+ θ；左上角與右下角關(guān)于布局空間中心點對稱，故左上角要演逆時針旋轉(zhuǎn)角度π后再沿順時針旋轉(zhuǎn)角度θ，即沿逆時針旋轉(zhuǎn)角度 π? θ。

圖2 左下角可行域與矩形塊布入點

圖3 旋轉(zhuǎn)角度θ后的可行域

綜上所述，矩形塊的布入點存在以下性質(zhì)。

性質(zhì)4 當(dāng)A≥0，B≥0時，可行域沿逆時針旋轉(zhuǎn)角度θ，當(dāng)A≥0，B＜0時，可行域沿逆時針旋轉(zhuǎn)角度 θπ? ，當(dāng)A＜0，B＜0時，可行域沿逆時針旋轉(zhuǎn)角度 θπ+ ，當(dāng)A＜0，B≥0時，可行域沿逆時針旋轉(zhuǎn)角度2 θπ? ，其中矩形塊的布入點都存在于新可行域的最低點中。

由上述性質(zhì)可得吸引子法的布局幾何過程描述：首先根據(jù)確定的吸引子參數(shù)得出布局參數(shù)A和B，根據(jù)A和B的取值確定矩形塊的堆積的角，再根據(jù)A和B確定旋轉(zhuǎn)角度φ，布局空間沿逆時針旋轉(zhuǎn)角度φ后，將矩形塊（也沿逆時針旋轉(zhuǎn)角度φ）布入布局空間的可行域中的最低位置，直至無法布入矩形塊為止。

以上布局描述可以成為一種手動快速布局方法。圖4為手動快速布局方法的流程圖。

圖4 手動快速布局流程圖

本文利用文獻(xiàn)[8]中的布局空間為2.5*2的算例進(jìn)行檢驗。文獻(xiàn)[8]中吸引子參數(shù)為

根據(jù)A和B的取值可確定矩形塊堆積于布局空間的左上角。由于

所以， θ=0.797038856，因矩形塊堆積于布局空間的左上角，故需要旋轉(zhuǎn)的角度為? =π? θ= 2.344553797，即 134.3°。將布局空間沿逆時針旋轉(zhuǎn)134.3°，并將算例中的布入矩形按面積大小進(jìn)行排序后，矩形塊的布入順序為14→29→2→23→20→0→28→10→9→24→8→30→1→25→33→35→31→4→32→36→27→19→18→16→39→7→13→22→11→17→12→3→38→21→5→26→6→15→37→34。將矩形塊依次布入布局空間中該矩形塊可行域的最低位置。布局結(jié)果如圖5所示，而圖6為文獻(xiàn)中算例的布局結(jié)果。兩圖比較可知兩種布局結(jié)果是一樣的。的 部 分 ， 當(dāng) xi＜ x0t時 ，

圖5 手動快速布局結(jié)果

圖6 文獻(xiàn)[8]中的布局結(jié)果

另外，傳統(tǒng)的定位規(guī)則BL算法也有趨角性，只不過其趨向的角僅為左下角。本文也利用 BL算法解決文獻(xiàn)[8]算例，再利用矩形的對稱性，將布局結(jié)果轉(zhuǎn)化為趨向左上角的情況，其結(jié)果如圖7所示。對比圖6與圖7的布局結(jié)果，我們可以發(fā)現(xiàn)，圖6的布局結(jié)果要優(yōu)于圖7，且圖6布局結(jié)果中間隙少而密，而圖7布局結(jié)果中間隙多而散。這是由于吸引子法的布局靈活，更容易保證矩形塊之間緊貼，不制造較大的間隙。

3 隱性吸引子研究

以上研究中，4個吸引子放置在布局空間的四個角上，這種放置是比較規(guī)則的。而理論上吸引子是可以任意放置的。以下研究吸引子的放置對布局問題的影響。

圖7 BL法布局結(jié)果

首先明確，整體空間是無界的，吸引子可以放置在其中任意位置。而布局空間只是整體空間的一部分，矩形塊只能放置于布局空間內(nèi)。不妨假設(shè)在整體空間內(nèi)任意放置若干吸引子，且放置位置與布局空間無關(guān)。矩形塊對位于 (x0t,y0t)的 吸 引 子 t的 定 位 函 數(shù) 為gt(xi,yi) = αt|xi? x0t|+ βt| yi? y0t|。其中關(guān)于；當(dāng)ix ≥0tx 時，同理可得，當(dāng)tiyy0＜時，當(dāng)iy≥0ty 時，于是關(guān)于吸引子t的定位函數(shù)可寫成

其中，當(dāng) xi＜ x0t時， λt=?1，否則 λt=1；當(dāng)yi＜ y0t時，ηt=?1，否則ηt=1。于是矩形塊的定位函數(shù)可寫成

所 以 當(dāng) 點 (xi,yi)經(jīng) 過 微 小 移 動 至(xi+Δx,yi+Δy )，且 λt與ηt不發(fā)生改變時，

由式（6）可知，對于吸引子任意放置的情況，布局參數(shù)為

需要注意的是，此時A和B已不再是常數(shù)。當(dāng)點(xj, yj)移動經(jīng)過吸引子所在的垂直線（或水平線）時，λt（或ηt）便發(fā)生改變，隨之A（或B）也發(fā)生改變。因此可視參數(shù)A（或B）為關(guān)于矩形塊中心點坐標(biāo)xi（或yi）的階梯函數(shù)A(x)（或B(y)），且該階梯函數(shù)的間斷點的坐標(biāo)為各個吸引子坐標(biāo)x0t（或y0t）。

如圖8所示，若在布局空間內(nèi)任意放置3個吸引子，并畫出所有經(jīng)過吸引子點的水平線和垂直線，此時布局空間X方向被分為4個部分，分別命名為a、b、c和d，Y方向也被分為4個部分，分別命名為Ⅰ、Ⅱ、Ⅲ和Ⅳ，這樣布局空間就被分割為 4×4個小區(qū)域。在各個小區(qū)域中，參數(shù)A和B是根據(jù)其所在X和Y方向的部分所確定的。比如若矩形塊在X方向的a部分，

圖8 3個吸引子劃分的布局空間

若矩形塊在X方向的b部分，

若矩形塊在X方向的c部分，

若矩形塊在X方向的d部分，

若矩形塊在Y方向的Ⅰ部分，

若矩形塊在Y方向的Ⅱ部分，

若矩形塊在Y方向的Ⅲ部分，

若矩形塊在Y方向的Ⅳ部分，

圖中點C所在區(qū)域為X方向的b部分和Y方向的Ⅲ部分，因此其定位函數(shù)中

因吸引子參數(shù) αt,βt,ωt∈[0,1]，當(dāng)矩形塊中心點坐標(biāo)xi從 ? ∞到 + ∞時，布局參數(shù)A隨著一直增加且由負(fù)到正。故存在且只存在一個間斷點x0，當(dāng) xi＜ x0時，A＜0；當(dāng) xi＞ x0時，A≥0。易知

同理可知，存在且只存在一個間斷點y0，使得

由上述結(jié)論可知在整體空間內(nèi)存在一點 ),(00yx ，使得

而且空間內(nèi)其他點距該點越遠(yuǎn)，定位函數(shù)值越大?？梢娫擖c已成為整體空間內(nèi)的一個隱性吸引子。而這個現(xiàn)象就得出了吸引子法的一個重要性質(zhì)。

性質(zhì)5 無論使用多少個吸引子，吸引子如何布置，參數(shù)大小如何，其達(dá)到的效果都相當(dāng)于在整體空間內(nèi)設(shè)置了一個隱性吸引子的效果。

若該隱性吸引子在布局空間內(nèi)（包括布局空間邊界），矩形塊將環(huán)繞該隱性吸引子布局，如圖9所示；若該隱性吸引子在布局空間外，矩形塊會因受該隱性吸引子吸引而堆積在一個角上，如圖10所示。

圖9 隱性吸引子在空間中心的布局

當(dāng)4個吸引子布置在布局空間四角時，由于吸引子這種特殊的布置，無論吸引子參數(shù)如何，隱性吸引子都只存在于4個角點之中。矩形塊因受到存在于角上吸引子的吸引，而導(dǎo)致布局結(jié)果會出現(xiàn)眾矩形塊堆積在一個角上的效果。這也很好地解釋了用吸引子法解決二維矩形布局時為什么會出現(xiàn)趨角性，也進(jìn)一步說明，前面針對眾備選點所設(shè)定的特別規(guī)定并不影響吸引子法的趨角性。

4 結(jié) 論

以上推導(dǎo)出的性質(zhì)，都是由定位函數(shù)中的gt(xi,yi)=αt|xi?xot|+βt|yi?y0t|所決定的。這些性質(zhì)很好地保證了矩形塊貼邊占角的布局要求。這在一定程度上提高了布局空間的利用率。但矩形塊只堆積在一個角上的這個性質(zhì)，卻很容易將布局產(chǎn)生的間隙分散到其他3個角上，這樣有可能會降低布局空間的利用率。而這個問題的解決還有賴于定位函數(shù)中函數(shù) gt(xi,yi)的改進(jìn)。因此改進(jìn)原有的函數(shù) gt(xi,yi)或提出新的函數(shù)應(yīng)成為下一步的研究目標(biāo)。

[1] Imahori S, Yagiura M, Ibaraki T. Local search algorithms for the rectangle packing problem with general spatial costs [J]. Mathematical Programming, 2003, 97(3): 543-569.

[2] Lodi A, Martello S, Monaci M. Two-dimensional packing problems: a survey [J]. European Journal of Operational Research, 2002, 141: 241-252.

[3] Hopper E, Turton B C H. A review of the application of meta-heuristic algorithms to 2D strip packing problems [J]. Artificial Intelligence Review, 2001, 16: 257-300.

[4] 查建中, 唐曉君, 陸一平. 布局及布置設(shè)計問題求解自動化的理論與方法綜述[J]. 計算機輔助設(shè)計與圖形學(xué)學(xué)報, 2002, 14(8): 1-8.

[5] Burke E K, Hyde M, Kendall G, et al. A genetic programming hyper-heuristic approach for evolving 2-D strip packing heuristics [J]. IEEE Transaction on Evolutionary Computation, 2010, 14(6): 1-17.

[6] 王愛虎, 鄂明成, 查建中. 基于空間分解的二維布局問題的啟發(fā)式算法[J]. 天津大學(xué)學(xué)報, 1996, 29(6): 840-846.

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

[8] 朱艷華. 布局問題遺傳算法的研究[D]. 天津: 天津工程師范學(xué)院機械工程學(xué)院, 2009.

[9] 王金敏, 王保春, 朱艷華. 求解矩形布局問題的一種混合 SAGA算法[J]. 天津工程師范學(xué)院學(xué)報, 2010, 20(2): 5-9.

[10] 束金龍, 聞人凱. 線性規(guī)劃理論與模型應(yīng)用[M].北京: 科學(xué)出版社, 2003: 14-62.

Research on attractive factor approach in rectangular packing problem

Wang Jinmin, Qi Yang
( Tianjin Key Laboratory of High Speed Cutting & Precision Machining, TUTE, Tianjin 300222, China )

The attractive factor approach, which is one of the location function approach, has gotproduces better results in the packing problems. This paper researches the attractive factor approach and gets some basic properties of it as follows: Such as the 3D image of the location function is a plane, the points with equal values of the location function are on the same straight line, the rectangular items are piled in a corner by the attractive factor approach, and so on. In addition, a manual rapid-packing method is given by studying the geometry significance of the pack-in point. In the end, the property which is about the of being an invisible attractive factor is obtained by studying the effect of the position of the attractive factors.

packing problem; heuristic algorithms; location function; attractive factor approach

TP 391.72

A

2095-302X (2012)06-0038-07

2011-05-30；定稿日期：2011-07-19

國家自然科學(xué)基金資助項目（60975046）

王金敏（1963-），男，河南舞陽人，教授，博士，主要研究方向為智能布局、計算機圖形學(xué)。E-mail：wang_jin_min@163.com