三維矩形布局吸引子性質的研究

王金敏

(天津職業技術師范大學，天津 300222)

三維矩形布局吸引子性質的研究

王金敏

(天津職業技術師范大學，天津 300222)

吸引子法作為一種量化的定位規則，在解決三維布局問題時取得了較好的效果。對解決三維矩形布局問題的吸引子法進行了研究，獲得了吸引子法的一些基本性質，如最佳布入點、吸引子法的趨角性、隱性吸引子的“唯一”性以及位置的“動態性”等，有利于吸引子法在三維矩形布局求解中得到更好地運用。

矩形布局；啟發式算法；吸引子法；定位規則；定位函數

三維矩形布局問題[1-2]廣泛存在于現代生產及生活中，如集裝箱內貨物箱子的擺放、儀器艙內各種儀器的布局、生產車間內設備的布置等。布局問題已被證明為NP難問題。三維矩形布局問題的求解算法[3]，主要有優化算法和啟發式算法。優化算法只能解決小規模問題，并且解的質量往往依賴于初始解的選擇。啟發式算法[4-5]是基于直觀或經驗構造的算法，其在可接受的計算時間和空間內給出待解決問題的一個可行滿意解。

近些年來，隨著啟發式算法種類的增多和研究者對前人布局智慧的總結，在布局問題的研究領域出現了許多新型啟發式算法。如 Zhang等[6]采用分層思想，分別利用深度和廣度優先搜索方法來解決布局問題；Wei等[7]基于三維矩形布局的極限點提出了塊構建啟發方法，并融合到一個使用迭代構建策略的樹搜索算法中；Cui等[8]利用不同模式的組合提出一種基于序列值的啟發式算法解決二維切割問題。

布局構造啟發算法是最常見的一種啟發式算法。構造算法主要由定序規則和定位規則所決定。確定量化的定序規則和定位規則即建立相關的定序函數和定位函數，可以將不同的布局算法綜合統一。吸引子法[9]是定位函數中的一種。吸引子法吸收了下臺階法、BL算法等許多定位規則的優點，并且其可量化的特點使其易于計算。吸引子法利用定位函數中參數的不同取值可以獲得不同的布局求解算法；如果參數選擇得當，則可得到較佳的求解算法。

以前的文獻多數注重對于吸引子法的應用，如王金敏等[10]利用蜜蜂進化型遺傳算法優化吸引子函數中的參數來求解三維矩形布局問題。而對吸引子法性質的研究僅有文獻[11]對二維矩形布局的情況進行了論述。

本文對解決三維矩形布局問題的吸引子法進行研究，得出了吸引子法的一些基本性質，利于吸引子法在三維矩形布局問題求解中得到更好地運用。

1 三維矩形布局問題

三維矩形布局問題是指將若干個尺寸不同或者相同的長方體(或正方體)布局塊，放置在一個長方體(或正方體)的布局空間內，要求布局空間的利用率盡可能大，且滿足：

(1) 布局塊完全放置在布局空間內；

(2) 布局塊之間不能發生干涉；

(3) 布局塊的表面分別與布局空間表面平行或垂直。

2 吸引子法簡介

在布局空間內設置k個吸引子，其中吸引子t的坐標為(xt, yt, zt)，則布局塊b在(x, y, z)處的定位函數為：

其中，tω為吸引子參數，且為權重因子，且αt+βt+γt= 1；ωt、αt、βt、γt∈[0,1]。

在布局時吸引子t吸引布局物體向其移動或靠近，從而達到布局定位的效果。吸引子布局可分為靜態和動態 2種方式。靜態方式是指定位函數的各個權重因子數值(強度)和吸引子位置在布局過程中始終保持不變；動態方式是指吸引子位置在布局過程中隨著布局條件而變化，或吸引子位置不變但權重因子數值發生變化。本文主要對靜態方式進行研究。

3 吸引子性質

本文研究定位函數中參數αt、tβ、γt和ωt確定情況下，定位函數的變化情況。不失一般性，令布局塊的布入參考點為其幾何中心。現將吸引子分別放在布局空間的 8個角點，并令布局空間的尺寸為L×W×H，如圖1所示。

圖1 布局空間及吸引子分布

布局塊b在(x, y, z)處的定位函數為：

整理得：

其中，

根據吸引子法的定義，布局塊 b在布局空間的最佳布入點(x, y, z)應滿足：

其中，(x,y,z)∈I，I為布局可行域。

當αt、βt、γt和ωt確定時，A、B、C和D為常數，根據吸引子定位函數的定義有 G(x,y,z)≥0，因此，理論上有Min G(x,y,z)= 0，即：

也就是最佳布入點應在一平面上。又由于布入點(x, y, z)應處在布局可行域內，因此布局塊 b在布局空間的最佳布入點(x, y, z)處在法向為(A, B, C)的平面上。由此得以下性質：

性質1. 在三維矩形布局空間內，定位函數值相同的點在同一個平面上，該平面的法矢量為(A, B, C)。

由于布入點(x, y, z)應處在布局可行域內，又處在法向為(A, B, C)的平面族上，因此，最佳布入點一定在布局可行域的邊界上即可行域頂點上。顯然，頂點可分為凸點和凹點。不妨令p1(x, y, z)為定位函數值最小的凹點，且布局可行域邊界上與P1相鄰的凸點為p(x+Δx,y+Δy,z+Δz )，則：

下面根據 A、B、C的不同取值分別討論當G(x+Δx,y+Δy,z+Δz)≤G(x,y,z)時，凸點p是否存在的情況。

(1)A≥0,B≥0,C≥0。此時在布局可行域邊界上一定存在凸點p，使Δx≤0,Δy≤0,Δz≤0成立。此時最佳布入點應為左、前、下的凸點即圖1 中1點方位。

(2)A≥0,B≥0,C≤0。此時存在凸點p，使Δx≤0,Δy ≤0,Δz≥0成立；因此，最佳布入點應為左、前、上的凸點即圖1中5點方位。

(3)A≥0,B≤0,C≥0。存在凸點p，使Δx≤0,Δy≥0,Δz≤0；最佳布入點應為左、后、下的凸點即圖1中4點方位。

(4)A≥0,B≤0,C≤0。存在凸點p，使Δx≤0,Δy≥0,Δz≥0；最佳布入點應為左、后、上的凸點即圖1中8點方位。

(5)A≤0,B≥0,C≥0。存在凸點p，使Δx≥0,Δy≥0,Δz≤0；最佳布入點應為右、前、下的凸點即圖1中2點方位。

(6)A≤0,B≥0,C≤0。存在凸點p，使Δx≥0,Δy≤0,Δz≥0；最佳布入點應為右、前、上的凸點即圖1中6點方位。

(7)A≤0,B≤0,C≥0。存在凸點p，使Δx≥0,Δy≥0,Δz≤0；最佳布入點應為右、后、下的凸點即圖1中3點方位。

(8)A≤0,B≤0,C≤0。存在凸點p，使Δx≥0,Δy≥0,Δz≥0；最佳布入點應為右、后、上的凸點即圖1中7點方位。

性質2. 最佳布入點一定為布局可行域中的凸點。

根據性質 2可知，當利用吸引子法作為定位函數進行三維布局時，布局塊會趨向堆積在布局空間的一個“角點”上，根據A、B和C取值的不同，堆積的角點不同，堆積的狀態不同。這就是吸引子法的趨角性。

布局空間只是整體空間的一部分，布局塊只能放置于布局空間內，在整體空間內任意放置若干吸引子，且放置位置不受布局空間限制的情況如下：

令布局塊b在布入點(x, y, z)對位于(xt, yt, zt)的吸引子t的定位函數為：

其中，當 x≥xt時，lt=1；否則，lt=-1。當 y≥yt時， mt=1；否則， mt=-1。當 z≥zt時， nt= 1；z＜zt時， nt=-1。

因此，布局塊b在布入點(x, y, z)對位于(xt, yt, zt)的吸引子t的定位函數為：

整理得：

其中，

當參數ωt、αt、βt、γt為定值，吸引子個數k和位置(xt, yt, zt)確定時，參數lt、mt、nt也為定值，則A、B、C、D為定值。如果A=B=C=0，此時G(x, y, z)=D，即定位函數為定值，吸引子不產生“效果”。因此，使用吸引子法布局時，應避免此種情況。對這種情況，可認為任意一點皆可為吸引子。當參數A、B和C中有一個不為零時，不失一般性令A不為零，可得 G(x,y,z) = A(x + D/A) +By+Cz+D 。由此可知無論使用多少個吸引子，吸引子如何布置，參數大小如何，布局塊b在布入點(x, y, z)的定位函數都相當于在空間內設置了“一個”吸引子的定位函數。

性質3. 當布入點在某一空間內，無論使用多少個吸引子，吸引子如何布置，參數大小如何設定，其達到的定位效果都相當于對此空間設置了一個“隱性”吸引子的效果。

通常，k個吸引子可將整體空間劃分為(k+1)3個子空間，圖2所示為1個吸引子劃分子空間的情況。在每個子空間性質3均成立。

圖2 1個吸引子劃分空間的情況

性質4. 在整體空間內，“隱性”吸引子的位置既與所設吸引子數量和位置有關，也與布入點相對吸引子的位置有關。

當吸引子布置在布局空間邊界上或外部時，“隱性”吸引子則可能在布局空間的角點、邊界線或邊界上，這時布局塊會受到該吸引子的吸引而產生趨角、貼面的效果，如圖3所示。

圖3 吸引子布置在布局空間邊界上

當吸引子布置在布局空間內時，“隱性”吸引子也在布局空間內部，這時布局塊會受到吸引而趨向該吸引子，如圖4所示。

圖4 吸引子布置在布局空間內

4 結 論

目前在布局研究領域出現了許多新型啟發式算法；吸引子法也為其中一種。吸引子法吸收了下臺階法、BL算法等許多定位規則的優點，其通過確定優化定位函數，來獲得滿意的布局結果。

本文通過分析推導，得出了三維布局吸引子法的一些基本性質，揭示了吸引子的趨角性及“隱性”吸引子的動態性，利于更好地應用吸引子法解決布局問題。

[1] Dyckhoff H. A typology of cutting and packing problems [J]. European Journal of Operational Research, 1990, 44(2): 145-159.

[2] Wascher G, HauBner H, Schumann H. An improved typology of cutting and packing problems [J]. European Journal of Operational Research, 2007, 183(3): 1109-1130.

[3] Cagan J, Shinada K, Yin S. A survey of computational approaches to three-dimensional layout problems [J]. Computer-Aided Design, 2002, 34(8): 597-611.

[4] Egeblad J, Pisinger D. Heuristic approaches for the twoand three-dimensional knapsack packing problem [J]. Computer & Operations Research, 2009, 36(4): 1026-1049.

[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] Zhang D F, Yu P, Leung S C H. A heuristic block-loading algorithm based on multi-layer search for the container loading problem [J]. Computers & Operations Research, 2012, 39(10): 2267-2276.

[7] Wei L J, Oon W C, Zhu W B, et al. A reference length approach for the 3D strip packing problem [J]. European Journal of Operational Research, 2012, 220(1): 37-47.

[8] Cui Y P , Cui Y D, Tang T B. Sequential heuristic for the two-dimensional bin-packing problem [J]. European Journal of Operational Research, 2015, 240(1): 43-53.

[9] 王金敏, 楊維嘉. 動態吸引子在布局求解中的應用[J].計算機輔助設計與圖形學學報, 2005, 17(8): 1725-1729.

[10] 王金敏, 朱麗萍, 甄士剛. 一種基于蜜蜂進化選擇算子的布局遺傳算法[J]. 圖學學報, 2014, 35(5): 690-696.

[11] 王金敏, 齊 楊. 矩形布局問題吸引子法研究[J]. 圖學學報, 2012, 33(6): 38-44.

Research on the Property of Attractive Factor in Three Dimensional Rectangular Packing Problem s

Wang Jinm in

(Tianjin University of Technology and Education, Tianjin 300222, China)

The attractive factor approach, which is one of the quantitative positioning rules, has got satisfactory effects in solving three-dimensional packing problems. The paper studies the attractive factor approach and gets some properties as follows: best fit packing point, taxis to convex and corner point, uniqueness of invisible attractor factor and the “dynam ic” of location. It w ill be conducive to enable the better usage of attractor factor approach in solving three-dimensional rectangular packing problems.

rectangular packing problems; heuristic algorithm; attractor factor approach; positioning rule; positioning function

TP 391

10.11996/JG.j.2095-302X.2016030355

A

2095-302X(2016)03-0355-04

2015-11-28；定稿日期：2015-12-20

國家自然科學基金項目(60975046)；天津職業技術師范大學科研發展基金項目(KJ14-64)

王金敏(1963–)，男，河南舞陽人，教授，博士。主要研究方向為智能布局、計算機輔助設計及圖形學。E-mail：wang_jin_m in@163.com