三維矩形布局吸引子性質(zhì)的研究

王金敏

(天津職業(yè)技術(shù)師范大學(xué)，天津 300222)

三維矩形布局吸引子性質(zhì)的研究

王金敏

(天津職業(yè)技術(shù)師范大學(xué)，天津 300222)

吸引子法作為一種量化的定位規(guī)則，在解決三維布局問題時(shí)取得了較好的效果。對(duì)解決三維矩形布局問題的吸引子法進(jìn)行了研究，獲得了吸引子法的一些基本性質(zhì)，如最佳布入點(diǎn)、吸引子法的趨角性、隱性吸引子的“唯一”性以及位置的“動(dòng)態(tài)性”等，有利于吸引子法在三維矩形布局求解中得到更好地運(yùn)用。

矩形布局；啟發(fā)式算法；吸引子法；定位規(guī)則；定位函數(shù)

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

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

布局構(gòu)造啟發(fā)算法是最常見的一種啟發(fā)式算法。構(gòu)造算法主要由定序規(guī)則和定位規(guī)則所決定。確定量化的定序規(guī)則和定位規(guī)則即建立相關(guān)的定序函數(shù)和定位函數(shù)，可以將不同的布局算法綜合統(tǒng)一。吸引子法[9]是定位函數(shù)中的一種。吸引子法吸收了下臺(tái)階法、BL算法等許多定位規(guī)則的優(yōu)點(diǎn)，并且其可量化的特點(diǎn)使其易于計(jì)算。吸引子法利用定位函數(shù)中參數(shù)的不同取值可以獲得不同的布局求解算法；如果參數(shù)選擇得當(dāng)，則可得到較佳的求解算法。

以前的文獻(xiàn)多數(shù)注重對(duì)于吸引子法的應(yīng)用，如王金敏等[10]利用蜜蜂進(jìn)化型遺傳算法優(yōu)化吸引子函數(shù)中的參數(shù)來求解三維矩形布局問題。而對(duì)吸引子法性質(zhì)的研究?jī)H有文獻(xiàn)[11]對(duì)二維矩形布局的情況進(jìn)行了論述。

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

1 三維矩形布局問題

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

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

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

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

2 吸引子法簡(jiǎn)介

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

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

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

3 吸引子性質(zhì)

本文研究定位函數(shù)中參數(shù)αt、tβ、γt和ωt確定情況下，定位函數(shù)的變化情況。不失一般性，令布局塊的布入?yún)⒖键c(diǎn)為其幾何中心?，F(xiàn)將吸引子分別放在布局空間的 8個(gè)角點(diǎn)，并令布局空間的尺寸為L(zhǎng)×W×H，如圖1所示。

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

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

整理得：

其中，

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

性質(zhì)2. 最佳布入點(diǎn)一定為布局可行域中的凸點(diǎn)。

根據(jù)性質(zhì) 2可知，當(dāng)利用吸引子法作為定位函數(shù)進(jìn)行三維布局時(shí)，布局塊會(huì)趨向堆積在布局空間的一個(gè)“角點(diǎn)”上，根據(jù)A、B和C取值的不同，堆積的角點(diǎn)不同，堆積的狀態(tài)不同。這就是吸引子法的趨角性。

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

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

其中，當(dāng) x≥xt時(shí)，lt=1；否則，lt=-1。當(dāng) y≥yt時(shí)， mt=1；否則， mt=-1。當(dāng) z≥zt時(shí)， nt= 1；z＜zt時(shí)， nt=-1。

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

整理得：

其中，

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

性質(zhì)3. 當(dāng)布入點(diǎn)在某一空間內(nèi)，無論使用多少個(gè)吸引子，吸引子如何布置，參數(shù)大小如何設(shè)定，其達(dá)到的定位效果都相當(dāng)于對(duì)此空間設(shè)置了一個(gè)“隱性”吸引子的效果。

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

圖2 1個(gè)吸引子劃分空間的情況

性質(zhì)4. 在整體空間內(nèi)，“隱性”吸引子的位置既與所設(shè)吸引子數(shù)量和位置有關(guān)，也與布入點(diǎn)相對(duì)吸引子的位置有關(guān)。

當(dāng)吸引子布置在布局空間邊界上或外部時(shí)，“隱性”吸引子則可能在布局空間的角點(diǎn)、邊界線或邊界上，這時(shí)布局塊會(huì)受到該吸引子的吸引而產(chǎn)生趨角、貼面的效果，如圖3所示。

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

當(dāng)吸引子布置在布局空間內(nèi)時(shí)，“隱性”吸引子也在布局空間內(nèi)部，這時(shí)布局塊會(huì)受到吸引而趨向該吸引子，如圖4所示。

圖4 吸引子布置在布局空間內(nèi)

4 結(jié) 論

目前在布局研究領(lǐng)域出現(xiàn)了許多新型啟發(fā)式算法；吸引子法也為其中一種。吸引子法吸收了下臺(tái)階法、BL算法等許多定位規(guī)則的優(yōu)點(diǎn)，其通過確定優(yōu)化定位函數(shù)，來獲得滿意的布局結(jié)果。

本文通過分析推導(dǎo)，得出了三維布局吸引子法的一些基本性質(zhì)，揭示了吸引子的趨角性及“隱性”吸引子的動(dòng)態(tài)性，利于更好地應(yīng)用吸引子法解決布局問題。

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

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

[11] 王金敏, 齊 楊. 矩形布局問題吸引子法研究[J]. 圖學(xué)學(xué)報(bào), 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

國(guó)家自然科學(xué)基金項(xiàng)目(60975046)；天津職業(yè)技術(shù)師范大學(xué)科研發(fā)展基金項(xiàng)目(KJ14-64)

王金敏(1963–)，男，河南舞陽人，教授，博士。主要研究方向?yàn)橹悄懿季?、?jì)算機(jī)輔助設(shè)計(jì)及圖形學(xué)。E-mail：wang_jin_m in@163.com