求解矩形布局問題的自適應算法

王金敏， 王保春， 朱艷華

（1．天津職業技術師范大學天津市高速切削與精密加工重點實驗室，天津 300222；2．山東英才學院，山東 濟南 250104）

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

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

與已有研究側重優化布局定序規則不同，本文針對二維矩形布局問題，基于動態吸引子[8]，以定位參數的優化為依據，提出了一種將遺傳算法和模擬退火算法相結合的自適應算法。

1 問題描述

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

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

其中，m為布入的矩形塊數，f值的大小可用來衡量布局結果的優劣。

矩形布局問題的數學模型為

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

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

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

矩形塊i的定位函數具體形式為

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

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

2 自適應算法

2.1 算法原理

本文所說的自適應主要是指算法根據不同的布局容器和待布入矩形以及搜索過程，自動的調整算法的遺傳、交叉、變異概率及系統接收劣質解的概率，使算法向著最優解的方向改變。

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

2.2 基本操作

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

式中，t為進化代數，k∈[1, m]且為整數，m為種群數。

適應度函數 本文的適應度函數為容器的面積利用率 f。顯然，適應度值越大，也就是布局容器的面積利用率越大，個體的性能越好。

初始種群 在初始種群確定以前，為了得到較好的結果并提高算法的整體計算效率，以隨機的方式生成一個規模遠遠大于初始種群數的種群V。在確定初始種群數后，把種群V中個體適應度較大的個體復制到初始種群中。這樣做，雖然剛開始時間增長，但是整體優化算法的代數將可以大大減少，從而提高了算法的計算效率。

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

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

2）采用預先設定固定數值的方法確定出種群數。

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

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

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

交叉概率通過下式求出

式中，Pc1為劣質個體的交叉概率，Pc2為種群中最大適應度值的個體的交叉概率。fmax為當前群體最大適應度，favg為群體的平均適應度，f’為要交叉的兩個個體中較大的適應度值。

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

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

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

對于個體GK和個體GL，令和分別對應他們的第i個分量，那么通過公式

計算所得到的變量H就是種群中個體GK和GL的差異值。

對當前種群中個體進行變異操作，是產生新解和維持種群多樣性的有效手段，但較大的變異概率及較小的變異概率都不利于算法的收斂。本文中變異率是隨著遺傳進程的變化而自適應變化的。

設Pm1為劣質個體的變異概率，Pm2為種群中最大適應度值的個體的變異概率；fmax為群體最大的適應度，favg為群體的平均適應度，f為選定變異個體的適應度值。變異概率Pm為

變異操作過程：假設選擇個體Gi對其進行變異操作，首先根據變異概率Pm找出將要發生變異的分量，然后，按照以下公式進行操作，產生新的分量算子，從而產生新的個體。

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

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

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

其中，n為群體中個體數量，fi為個體i的適應度，favg為群體平均適應度。

在遺傳算法的初期，個體間差異很大，此時T也比較大，接收劣質解的概率q也很大，可以加速遺傳算法的收斂過程；當到算法的后期時，T就會變的很小，可以防止遺傳算法的過早收斂。

2.3 算法流程

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

1）初始種群生成；

2）計算種群中每個個體的適應度，并計算平均適應度；

3）判斷是否滿足終止條件，不滿足執行4)，否則輸出最優解，程序結束；

4）進行選擇操作；5）進行交叉操作；6）進行變異操作；

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

3 算例分析

在Celeron(R) CPU 2.93GHz，512MB內存的計算機上，對本文的自適應混合算法用VC++編程實現，并進行了算例的計算。

1）為了驗證算法的可行性，以及定位函數中各參數的作用，對文獻[10]的算例1進行求解。布局空間為40×15，待布局矩形塊數為25。經計算，布入物體所占面積為546.3，容器的面積利用率為91.05%，而文獻[10]的結果為88.86%?？梢钥闯觯疚牡牟季纸Y果優于文獻[10]中的結果。此時，定位函數各參數值分別為：

2）采用本文的自適應算法，對文獻[11]中名為BENG1-BENG10的10個算例進行求解計算，可以得到如表1所示的布局結果。

表1 對比結果

從表1中可以看出，采用本文算法對文獻[11]中的問題進行求解，所有問題的求解結果均優于文獻[11]中的結果，其中有6個問題的布局結果為100%，最差的布局結果為96.80%。

3）采用文獻[12]中的待布矩形塊數和布局容器都不相同的6個實例（如表2所示），對本文中兩種初始種群群體規模的確定方式進行了分析比較，結果如表3所示。

表2 布局數據

表3 兩種確定種群數方式的比較

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

4 結 論

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

[1]唐曉君, 查建中, 陸一平. 布局問題的復雜性和建模方法[J]. 北方交通大學學報, 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]. 計算機科學, 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]郭乙運, 劉天亮, 袁 立. 矩形物體布局問題的實用求解算法[J]. 物流科技, 2005, 28(119): 75-78.

[8]王金敏, 楊維嘉. 動態吸引子在布局求解中的應用[J]. 計算機輔助設計與圖形學學報, 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]李 明, 黃平捷, 周澤魁. 基于小生境遺傳算法的矩形件優化排樣[J]. 湖南大學學報(自然科學版),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.