王金敏， 王保春， 朱艷華

（1．天津職業(yè)技術(shù)師范大學(xué)天津市高速切削與精密加工重點(diǎn)實(shí)驗(yàn)室，天津 300222；2．山東英才學(xué)院，山東 濟(jì)南 250104）

布局問題[1]是指滿足必要的約束條件下，在布局容器中通過有效合理的方法放入若干個(gè)待布物體，并且達(dá)到某種最優(yōu)指標(biāo)。布局問題廣泛應(yīng)用于機(jī)械制造、皮革服裝、造船、交通運(yùn)輸、航空航天等諸多領(lǐng)域。好的布局方案，可以提高產(chǎn)品的性能，減少其制造及運(yùn)輸成本，對(duì)于企業(yè)的發(fā)展是至關(guān)重要的。從理論上講，布局問題屬于NP-Hard問題，是一種復(fù)雜的組合優(yōu)化問題。

隨著計(jì)算機(jī)技術(shù)的不斷發(fā)展，國內(nèi)外的專家學(xué)者對(duì)矩形布局問題進(jìn)行了研究并取得了一定的成果。如Dagli[2]結(jié)合人工智能與運(yùn)籌學(xué)方法，提出了基于知識(shí)求解矩形件、異形件布局問題的系統(tǒng)概念模型。Leung T W和Yung C H等[3]分別把遺傳算法和模擬退火算法這兩種啟發(fā)式方法運(yùn)用到二維無約束一刀切問題的求解中，并通過大量的算例進(jìn)行了比較。Loris F[4]利用模擬退火算法對(duì)無約束一刀切問題和約束一刀切問題分別進(jìn)行了討論。黃文奇，陳端兵[5]利用擬物擬人的思想策略，提出了基于最大穴度優(yōu)先的擬物擬人矩形布局算法，并經(jīng)過測試證明了其算法的高效性。Fang Hui等[6]針對(duì)矩形切割問題設(shè)計(jì)出一種改進(jìn)的遺傳算法，并通過實(shí)驗(yàn)認(rèn)為該方法在很短的時(shí)間內(nèi)便可以找出較好的布局結(jié)果。此外，還有很多人采用各種啟發(fā)式算法，如郭乙運(yùn)，劉天亮等[7]的矩形物體布局問題的實(shí)用算法中采用定序規(guī)則、擺放規(guī)則、定位規(guī)則和空間合并的策略，提出了一種基于空間分解的二維矩形物體布局的啟發(fā)式算法。

與已有研究側(cè)重優(yōu)化布局定序規(guī)則不同，本文針對(duì)二維矩形布局問題，基于動(dòng)態(tài)吸引子[8]，以定位參數(shù)的優(yōu)化為依據(jù)，提出了一種將遺傳算法和模擬退火算法相結(jié)合的自適應(yīng)算法。

1 問題描述

矩形布局問題描述：對(duì)于已知大小的矩形布局容器B和n個(gè)已知大小的待布矩形，通過一種有效合理的方法把這n個(gè)矩形盡可能多的放入到容器B中，并使容器的面積利用率盡可能的大，且要求任意兩塊放入容器的矩形塊相互不能發(fā)生干涉。

若布局容器的面積為S，第i個(gè)布入的矩形塊的寬和高分別為wi和hi，布局容器的面積利用率設(shè)為 f，則有

其中，m為布入的矩形塊數(shù)，f值的大小可用來衡量布局結(jié)果的優(yōu)劣。

矩形布局問題的數(shù)學(xué)模型為

式中，W和H分別為布局容器的寬和高；(xi, yi)和(xj, yj)分別為第i個(gè)和第j個(gè)布入矩形的中心點(diǎn)坐標(biāo)且i≠j，這里令布局容器的左下角為坐標(biāo)原點(diǎn)(0, 0)；wi與hi和wj與hj分別為第i個(gè)和第j個(gè)布入矩形的寬與高。式(1)和式(2)說明布局物體需要完全布入到容器中，式(3)和式(4)說明兩布局物體之間不能發(fā)生干涉現(xiàn)象。

布局求解的構(gòu)造法主要是由定序規(guī)則和定位規(guī)則所決定的，定序規(guī)則和定位規(guī)則的不同可以產(chǎn)生出不同的構(gòu)造布局算法。本文按照待布矩形的面積從大到小的順序來確定待布矩形布入布局容器的先后順序，若面積相等則按長邊從大到小來確定布入的先后順序。

本文采用“吸引子”的方法[8]來確定矩形塊的擺放位置，即定位規(guī)則。

矩形塊i的定位函數(shù)具體形式為

gt(xi, yi)為關(guān)于各個(gè)吸引子的定位函數(shù)，p為吸引子的個(gè)數(shù)。(xi, yi)為矩形塊基點(diǎn)的坐標(biāo)，(x0t,y0t)為第t個(gè)布局吸引子的坐標(biāo)，αt, βt, ωt為權(quán)重因子，αt+βt=1, ω1+ω2+ω3+ω4=1。這里t =1、2、3和4且分別表示吸引子位于布局容器的左下、右下、右上和左上4個(gè)角點(diǎn)。

由于定位函數(shù)中參數(shù)值的不同選取將決定布入矩形的擺放位置，因此問題已轉(zhuǎn)化為多參數(shù)的優(yōu)化問題。本文對(duì)4個(gè)吸引子的情況進(jìn)行研究，而對(duì)于其他情況，可以由4個(gè)吸引子的情況轉(zhuǎn)化得到。此時(shí)，需要對(duì)定位函數(shù)中的α1、α2、α3、α4、β1、β2、β3、β4、ω1、ω2、ω3、ω4共12個(gè)參數(shù)進(jìn)行優(yōu)化，但由于各權(quán)重因子之間的關(guān)聯(lián)關(guān)系，故實(shí)際上只需要對(duì)定位函數(shù)中α1、α2、α3、α4、ω1、ω2和ω3這7個(gè)參數(shù)進(jìn)行優(yōu)化。

2 自適應(yīng)算法

2.1 算法原理

本文所說的自適應(yīng)主要是指算法根據(jù)不同的布局容器和待布入矩形以及搜索過程，自動(dòng)的調(diào)整算法的遺傳、交叉、變異概率及系統(tǒng)接收劣質(zhì)解的概率，使算法向著最優(yōu)解的方向改變。

通常對(duì)于遺傳算法，初始種群中個(gè)體數(shù)量的確定，交叉概率和變異概率的確定等對(duì)算法的性能是至關(guān)重要的。而對(duì)于模擬退火算法，初始溫度的選擇和降溫策略以及接受劣質(zhì)解的概率，同樣具有關(guān)鍵的作用。若對(duì)這些操作選擇不當(dāng)，將不可避免的引起局部最優(yōu)問題和延長搜索的時(shí)間，從而限制算法的性能。自適應(yīng)的混合算法將根據(jù)問題規(guī)模的不同，對(duì)算法的種群數(shù)進(jìn)行調(diào)整。當(dāng)問題規(guī)模較小時(shí)，種群也較少，從而縮短搜索時(shí)間，加快求解的速度。在本文中，交叉、變異概率均采用自適應(yīng)的方式，這樣將有利于提高算法的收斂速度。同時(shí)，模擬退火算法中接收劣質(zhì)解的概率也將采用自適應(yīng)的方法進(jìn)行確定。

2.2 基本操作

編 碼 本文采用實(shí)數(shù)編碼的方式，變量為七維的解向量，并且每一個(gè)分量都在有限的區(qū)間上定義，編碼向量表示為

式中，t為進(jìn)化代數(shù)，k∈[1, m]且為整數(shù)，m為種群數(shù)。

適應(yīng)度函數(shù) 本文的適應(yīng)度函數(shù)為容器的面積利用率 f。顯然，適應(yīng)度值越大，也就是布局容器的面積利用率越大，個(gè)體的性能越好。

初始種群 在初始種群確定以前，為了得到較好的結(jié)果并提高算法的整體計(jì)算效率，以隨機(jī)的方式生成一個(gè)規(guī)模遠(yuǎn)遠(yuǎn)大于初始種群數(shù)的種群V。在確定初始種群數(shù)后，把種群V中個(gè)體適應(yīng)度較大的個(gè)體復(fù)制到初始種群中。這樣做，雖然剛開始時(shí)間增長，但是整體優(yōu)化算法的代數(shù)將可以大大減少，從而提高了算法的計(jì)算效率。

在本文中，初始種群的個(gè)體數(shù)量將采用以下兩種方式得到：

1）根據(jù)問題的規(guī)模大小，假設(shè)待布矩形的個(gè)數(shù)為n，那么種群中個(gè)體數(shù)量T 將由 n取整得到。這樣做的好處在于當(dāng)問題規(guī)模較小時(shí)，種群數(shù)也將不需要很大的值，從而提高算法的搜索效率。

2）采用預(yù)先設(shè)定固定數(shù)值的方法確定出種群數(shù)。

操作 操作是指選擇操作、交叉操作、變異操作、溫度的設(shè)定和Boltzmann概率等。

在進(jìn)行交叉操作之前，首先對(duì)當(dāng)前種群中適應(yīng)度最大的個(gè)體進(jìn)行保留操作，也就是在不進(jìn)行任何操作的情況下，讓適應(yīng)度最大的個(gè)體直接進(jìn)入下一代。這樣做的主要目的是為了保證種群中的優(yōu)良個(gè)體不被破壞，同時(shí)也保持了種群的多樣性。接下來采用輪盤賭的概率選擇法根據(jù)將要進(jìn)行交叉的個(gè)體數(shù)目，選擇出需要進(jìn)行交叉操作的個(gè)體。

在通常的交叉操作中，由于算法具有很強(qiáng)的隨機(jī)性，從而降低了本身的效率。本文將采用自適應(yīng)的交叉概率來進(jìn)行交叉操作。

交叉概率通過下式求出

式中，Pc1為劣質(zhì)個(gè)體的交叉概率，Pc2為種群中最大適應(yīng)度值的個(gè)體的交叉概率。fmax為當(dāng)前群體最大適應(yīng)度，favg為群體的平均適應(yīng)度，f’為要交叉的兩個(gè)個(gè)體中較大的適應(yīng)度值。

交叉操作的具體過程如下：

其中，α為(0, 1)之間的隨機(jī)數(shù)。

由于種群中個(gè)體是向著最優(yōu)解的方向進(jìn)化的，在進(jìn)化了一定代數(shù)后，可能會(huì)出現(xiàn)兩個(gè)個(gè)體較為相似甚至相同的情況。此時(shí)，若再對(duì)他們進(jìn)行交叉操作，將很難產(chǎn)生新的子代個(gè)體，為此在算法進(jìn)化了一定代數(shù)后，將根據(jù)兩個(gè)體之間的差異性，找出差異性最大的兩個(gè)體進(jìn)行交叉操作，這樣做將有益于保持種群的多樣性。

對(duì)于個(gè)體GK和個(gè)體GL，令和分別對(duì)應(yīng)他們的第i個(gè)分量，那么通過公式

計(jì)算所得到的變量H就是種群中個(gè)體GK和GL的差異值。

對(duì)當(dāng)前種群中個(gè)體進(jìn)行變異操作，是產(chǎn)生新解和維持種群多樣性的有效手段，但較大的變異概率及較小的變異概率都不利于算法的收斂。本文中變異率是隨著遺傳進(jìn)程的變化而自適應(yīng)變化的。

設(shè)Pm1為劣質(zhì)個(gè)體的變異概率，Pm2為種群中最大適應(yīng)度值的個(gè)體的變異概率；fmax為群體最大的適應(yīng)度，favg為群體的平均適應(yīng)度，f為選定變異個(gè)體的適應(yīng)度值。變異概率Pm為

變異操作過程：假設(shè)選擇個(gè)體Gi對(duì)其進(jìn)行變異操作，首先根據(jù)變異概率Pm找出將要發(fā)生變異的分量，然后，按照以下公式進(jìn)行操作，產(chǎn)生新的分量算子，從而產(chǎn)生新的個(gè)體。

式中，Xi(k)表示個(gè)體i的第k個(gè)分量，X’i(k)為變異后新個(gè)體的第k個(gè)分量，β為在整數(shù)1附近的隨機(jī)數(shù)。

在遺傳算法中，既要保證種群的多樣性，又要使遺傳算法向最優(yōu)解的方向快速收斂。單一不變的群體更新方式難以兼顧遺傳算法在不同階段對(duì)多樣性和收斂性的不同要求。因此，本文將模擬退火算法的Boltzmann更新機(jī)制融入到遺傳算法中。

在算法搜索過程中，當(dāng)子個(gè)體的適應(yīng)度大于父個(gè)體的適應(yīng)度時(shí)，用子個(gè)體代替父個(gè)體；否則，通過公式 q=exp(-k×△f/T) 計(jì)算出接受劣質(zhì)解的概率，令C為在0和1之間的隨機(jī)數(shù)，若C

其中，n為群體中個(gè)體數(shù)量，fi為個(gè)體i的適應(yīng)度，favg為群體平均適應(yīng)度。

在遺傳算法的初期，個(gè)體間差異很大，此時(shí)T也比較大，接收劣質(zhì)解的概率q也很大，可以加速遺傳算法的收斂過程；當(dāng)?shù)剿惴ǖ暮笃跁r(shí)，T就會(huì)變的很小，可以防止遺傳算法的過早收斂。

2.3 算法流程

以遺傳算法為主流程，并融入模擬退火算法的Boltzmann更新機(jī)制，對(duì)定位函數(shù)中的參數(shù)進(jìn)行優(yōu)化。算法以布局容器的利用率和遺傳進(jìn)化代數(shù)作為終止判斷條件。主要流程如下：

1）初始種群生成；

2）計(jì)算種群中每個(gè)個(gè)體的適應(yīng)度，并計(jì)算平均適應(yīng)度；

3）判斷是否滿足終止條件，不滿足執(zhí)行4)，否則輸出最優(yōu)解，程序結(jié)束；

4）進(jìn)行選擇操作；5）進(jìn)行交叉操作；6）進(jìn)行變異操作；

8）產(chǎn)生新一代種群，返回到步驟2)。

3 算例分析

在Celeron(R) CPU 2.93GHz，512MB內(nèi)存的計(jì)算機(jī)上，對(duì)本文的自適應(yīng)混合算法用VC++編程實(shí)現(xiàn)，并進(jìn)行了算例的計(jì)算。

1）為了驗(yàn)證算法的可行性，以及定位函數(shù)中各參數(shù)的作用，對(duì)文獻(xiàn)[10]的算例1進(jìn)行求解。布局空間為40×15，待布局矩形塊數(shù)為25。經(jīng)計(jì)算，布入物體所占面積為546.3，容器的面積利用率為91.05%，而文獻(xiàn)[10]的結(jié)果為88.86%?？梢钥闯?，本文的布局結(jié)果優(yōu)于文獻(xiàn)[10]中的結(jié)果。此時(shí)，定位函數(shù)各參數(shù)值分別為：

2）采用本文的自適應(yīng)算法，對(duì)文獻(xiàn)[11]中名為BENG1-BENG10的10個(gè)算例進(jìn)行求解計(jì)算，可以得到如表1所示的布局結(jié)果。

表1 對(duì)比結(jié)果

從表1中可以看出，采用本文算法對(duì)文獻(xiàn)[11]中的問題進(jìn)行求解，所有問題的求解結(jié)果均優(yōu)于文獻(xiàn)[11]中的結(jié)果，其中有6個(gè)問題的布局結(jié)果為100%，最差的布局結(jié)果為96.80%。

3）采用文獻(xiàn)[12]中的待布矩形塊數(shù)和布局容器都不相同的6個(gè)實(shí)例（如表2所示），對(duì)本文中兩種初始種群群體規(guī)模的確定方式進(jìn)行了分析比較，結(jié)果如表3所示。

表2 布局?jǐn)?shù)據(jù)

表3 兩種確定種群數(shù)方式的比較

表3方式1中種群的個(gè)數(shù)是根據(jù)問題的規(guī)模大小，對(duì)待布局矩形塊個(gè)數(shù)開二次方并取整得到的，方式2中種群數(shù)采用預(yù)先設(shè)定的方法定為25。從表中可以看出，采用方式1得到的種群數(shù)較方式2得到的少，在其他條件都相同的情況下采用方式2得出的容器面積利用率要高于方式1。

4 結(jié) 論

本文以動(dòng)態(tài)吸引子定位函數(shù)為依據(jù)，采用自適應(yīng)的方式對(duì)定位函數(shù)中各個(gè)參數(shù)進(jìn)行了優(yōu)化。關(guān)于二維矩形布局問題中定位函數(shù)參數(shù)優(yōu)化的自適應(yīng)混合算法，是模擬退火算法和遺傳算法的有效相結(jié)合，采用大面積優(yōu)先的定序原則，對(duì)待布矩形在布局空間中的位置進(jìn)行了定位計(jì)算。通過算例分析，采用該方法對(duì)定位函數(shù)進(jìn)行優(yōu)化，是一種行之有效的方法。由于問題的復(fù)雜性，本算法還需要進(jìn)一步的研究和改進(jìn)，以期得到更好的布局效果。

[1]唐曉君, 查建中, 陸一平. 布局問題的復(fù)雜性和建模方法[J]. 北方交通大學(xué)學(xué)報(bào), 2003, 27(1): 12-15.

[2]Dagli C H. Knowledge-based systems for cutting stock problems [J]. European Journal of Operational Research, 1990, 44(2): 160-166.

[3]Leung T W, Yung C H. Marvin D T. Applications of genetic search and simulated annealing to the two-dimensional non-guillotine cutting stock problem [J].Computers & Industrial Engineering, 2001, 40(3):201-214.

[4]Faina L. An application of simulated annealing to the cutting stock problem [J]. European Journal of Operational Research, 1999, 114: 542-556.

[5]黃文奇, 陳端兵. 一種求解矩形塊布局問題的擬物擬人算法[J]. 計(jì)算機(jī)科學(xué), 2005, 32(10): 182-186.

[6]Fang Hui, Yin Guofu, Li Haiqing, et al. Application of integer coding accelerating genetic algorithm in rectangular cutting stock problem [J]. Chinese Journal of Mechanical Engineering, 2006, 19(3): 335-339.

[7]郭乙運(yùn), 劉天亮, 袁 立. 矩形物體布局問題的實(shí)用求解算法[J]. 物流科技, 2005, 28(119): 75-78.

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

[9]Gilmore P C, Gomory R E. A linear programming approach to the cutting stock problem [J]. Operational Research, 1961, (9): 848-859.

[10]李 明, 黃平捷, 周澤魁. 基于小生境遺傳算法的矩形件優(yōu)化排樣[J]. 湖南大學(xué)學(xué)報(bào)(自然科學(xué)版),2009, 36(1): 46-49.

[11]Martello S, Monaci M, Vigo D. An exact approach to the strip-packing problem [J]. Journal on Computing,2003, 15(3): 310-319.

[12]Hopper E, Turton B. An empirical investigation of meta-heuristic and heuristic algorithm for a 2D packing problem [J]. European Journal of Operational Research, 2001, 128(1): 34-57.