基于自適應遺傳算法的矩形排樣方法研究*

單宇晗

（哈爾濱工程大學自動化學院 哈爾濱 150001）

1 引言

矩形排樣問題是二維排樣問題的一種，其目的是將一定數量的不同大小的矩形互不重疊的放置于一個矩形排樣空間內，求得一種排樣方案，使得排樣空間的空間利用率最大［1］。排樣問題被廣泛應用于板材切割和布匹裁剪等制造業領域，通過計算機自動排樣算法，能夠較人工排樣顯著提高材料利用率，從而節約大量的成本［2～4］。

排樣問題是非確定型多項式（Nondeterministic Polynomial，NP）問題的一種，理論上不能在多項式時間內得出一種解決方案［5～6］。NP 問題目前在研究領域并沒有一種高效的算法可以求得其最優解，在實際中一般利用智能優化算法求出一個近似最優解。排樣問題在研究領域一般從新的優化算法和新的排樣模型兩個方向進行研究。

本文首先建立矩形排樣問題模型，應用最低水平線法放置矩形，將排樣問題轉化為求解矩形最優放置順序問題。而后應用遺傳算法求解矩形排樣的最優排樣方案，并使用改進自適應策略在基本遺傳算法的基礎上進行改進，以優化算法的性能。

2 矩形排樣問題模型

2.1 問題模型

對于矩形件排樣問題，可以設置矩形排樣空間為P，長為L，寬度為W，同時存在n 個待排樣矩形{Pi，i=1…n}，長度和寬度分別為li和wi，假設矩形的數量足夠填滿整個排樣空間。根據排樣問題的定義，不同矩形之間不能重疊。這時求解一種矩形的排列方式，要求放置后矩形在排樣空間內所占面積最大，即為空間利用率最高。

定義排樣空間的左下角為原點O（0，0），則左上角為(0，L)，右下角為(W，0)。矩形Pi的左上角頂點是，右下角頂點的坐標是(xi1+wi，yi1-li)。則根據定義可以得到矩形排樣的模型如下：

約束條件：

目標函數：

2.2 最低水平線算法

對所有的矩形進行編號以后，通過最低水平線法確定待排樣矩形的放置規律，能夠將任何一種布列的方案都唯一表示為n個矩形{Pi，i=1…n}的一種排列組合［7～9］。

最低水平線法算法放置矩形的過程如下：

Step1：在開始時將最初的最高輪廓線設置為排樣空間的下邊界。

Step2：在每次放置一個矩形時，在最高輪廓線中選擇高度最低的一段水平線，如果有不止一段最低，就選擇最左邊的水平線。判斷這一段最低水平線的寬度是否大于或等于待放置的矩形的寬度，并執行以下操作：

1）如果這一段最低水平線的寬度大于或等于待放置的矩形的寬度，就將待放置的矩形放置在這個水平線的最左側，并且更新矩形最高輪廓線。

2）如果不是，選擇最低水平線兩側的兩段水平線，將最低水平線設置為高度較低的一段水平線，并且更新最高輪廓線。

3）轉到1），直到找到位置放置待放置的矩形。

Step3：轉到Step2，直至所有的矩形放置結束。

算法的前四個矩形的放置過程如圖1所示。

圖1 最低水平線算法前四個矩形放置示意圖

圖1 （a）：放置1號矩形，放置在左下角。

圖1（b）：放置2 號矩形，此時最低水平線為圖中加粗線段A，可以放置2號矩形，則將其放在最低水平的最左側。

圖1（c）：放置3 號矩形，此時最低水平線為圖中加粗線段B，3號矩形無法放入，則最低水平線移動至左側加粗線段C，3號矩形長度比其長，最低水平線繼續移動至加粗線段D，可以放入，則放在最低水平的最左側。

圖1（d）：放置4 號矩形，同理最初的最低水平線無法放入則最低水平線移動至其兩側較低的水平線，以此類推。

3 普通遺傳算法

3.1 遺傳算法

遺傳算法（Genetic Algorithm，GA），是由美國密歇根大學的Holland 在1975 年提出的，遺傳算法通過模擬自然選擇進化過程和自然遺傳機制尋找一個最優解，特點是不需要任何先驗知識，不易落入局部極值［10～11］。

在遺傳算法中解的集合稱為“種群”，其中的解稱為“個體”。將解通過一定方式進行編碼，這種編碼稱為“染色體”，每個個體對應一個獨特的染色體。解中的每一個分量的特征稱為基因，這些基因構成染色體。進化過程在算法里體現在在每次迭代過程中，通過個體的適應度函數的值選擇個體，并對這些個體的染色體進行“交叉”和“變異”操作，由舊種群產生新種群。種群中每個個體按照“適者生存”規則，在通過多次迭代，最后產生最優的近似解。

1）編碼。在前文中將其轉化為矩形在排樣空間中的組合優化問題。這樣以矩形的編號序列作為遺傳算法的編碼，并采用十進制形式的編碼，即每個數字對應一個矩形的十進制編號［12］。例如矩形的放置順序為{1，5，2，6，3，4}，表示的意義是矩形按照編號1，5，2，6，3，4 的順序進行放置。

2）適應度函數。優化問題的目標函數代表問題的期望優化結果，排樣問題的優化目標是排樣空間的剩余空間最小，這里可以使用排樣空間剩余面積占總面積的比例，即排樣空間未利用率作為適應度函數的數值。

3）選擇操作。模擬自然界中的“適者生存”的選擇過程，在計算過程中一般以個體的適應度的大小為標準，適應度高的進入一代的幾率較高，適應度小的進入下一的幾率較小。在本文中使用輪盤賭法進行選擇，對于布列問題設一共有n 個矩形，第i 個矩形的適應度大小為fi，則這個矩形被選擇的概率Pi：

4）交叉操作。模擬自然界中的染色體基因重組的過程，是生成新個體的主要方式。交叉是將父代的基因進行替換重組的過程，代表著遺傳算法的全局搜索能力。在本文中使用順序交叉法，其實現步驟如下：

圖2 選擇交叉部分示意圖

圖3 生成第一個子代個體示意圖

圖4 生成第二個子代個體示意圖

Step1：隨機選擇第一父染色體上的交叉部分。

(1)旱情監測數據快速處理技術。旱情遙感監測系統每天處理大量的衛星遙感數據，完成數據的自動入庫。如何保證高效、穩定、自動的數據接收是系統實現的基礎，海量衛星圖像的快速、自動化的數據處理是系統實現的關鍵。實現旱情數據無人值守入庫、多源數據快速處理，主要包括多機并行自動化入庫、基于數據模型的質檢、基于規則的數據目錄動態創建、分布式并行全流程運行管理體系的引入、旱情監測數據再處理研發和數據綜匯和制圖表達等技術。

Step2：將第二個父染色體上和第一個染色體相同的基因去除，并將剩余基因按照原來的順序排列。

Step3：將第二父染色體的剩余部分同第一個父染色體的交叉部分按照原來的順便拼接成子染色體。

Step4：使用同樣的方式獲得第二個子染色體。

5）變異操作。變異操作模仿的是基因突變的過程，目的是增強基因的多樣性同時發生變異的個體也有可能因此適應度降低過早被淘汰。在本文中實現具體表現為：隨機選取染色體上的兩個不同的基因進行交換。

圖5 變異操作示意圖

6）結束條件。在本文中使用設定最大迭代次數作為算法的終止條件。

3.2 遺傳算法實現步驟

普通遺傳算法的實現過程如下

Step1：開始算法，初始化遺傳算法參數：最大迭代次數、初始種群大小、交叉概率、變異概率。

Step3：計算本代種群中所有的個體的適應度，并求得種群的平均適應度值和最優個體的適應度值。

Step3：判斷是否達到最大迭代數，如果達到則轉到Step5。

Step4：進行遺傳操作：選擇、交叉、變異。產生下一代種群，并轉到Step3。

Step5：對最后一代種群中的最優個體進行解碼，得到矩形排樣的最優方案。

4 改進自適應遺傳算法

普通遺傳算法的交叉概率和變異概率的選擇會影響算法的收斂速度和解的優秀程度。交叉概率較高會增強算法的搜索能力，但是容易使種群產生退化；較低會使算法易陷入局部最優。變異概率的存在能夠保證種群的多樣性，但是較高的變異概率會導致算法趨近于隨機搜索。當算法中個體之間的適應度相差較大時，較低的交叉和變異概率能夠保證優秀個體不被破壞；當算法趨于收斂時，種群中個體的適應度相差不明顯，較高的交叉和變異概率能夠提高算法的搜索能力［13］。所以通過改變算法的交叉和變異概率可以提高遺傳算法的搜索能力，提高算法的性能。

自適應遺傳算法相對于普通遺傳算法，在執行變異和變異操作之前增加了自適應改變交叉和變異概率的過程，參與交叉或變異的個體越為優秀，其交叉和變異概率越低。但是在算法運算前期存在一定數量的優秀個體不會發生交叉或變異，會導致算法的種群多樣性降低，影響算法的搜索能力［14～15］。

可以將整個運算過程分為兩個部分：在第i 代之前執行固定的交叉概率m1和變異概率m2，這樣保證存在足夠多的個體發生交叉和變異，從而保證種群的多樣性；在第i 代之后執行自適應交叉概率Pc和變異概率Pm，這樣能夠根據當前種群的實際環境自適應調節概率，從而提高算法的性能。

對于自適應策略，根據當前種群平均適應度favg、最大適應度fmax和每個個體的適應度fi計算自適應交叉和變異概率，其公式如下：

自適應交叉概率Pc：

其中fc為發生交叉的兩個個體適應度較高的適應度的大小，k1和k2為0～1的常數，且k1≥k2。

自適應變異概率Pm：

其中fm為當前變異個體的適應度的大小，k3和k4為0～1的常數，且k3≥k4。

5 仿真和結果分析

應用自適應遺傳算法求解矩形排樣，在Mat?lab2012a環境下進行仿真，并進行結果分析。

在仿真中需要根據排樣空間面積需要提供足夠數量的待排樣矩形以布滿整個排樣空間。這里使用六種型號的矩形參與排樣。設置參與排樣的不同型號矩形的尺寸如表1所示。

表1 排樣用矩形尺寸

5.1 普通遺傳算法和改進自適應遺傳算法仿真

設置遺傳算法的種群大小為100，最大迭代次數為100 代，固定交叉概率m1取值為0.9，固定變異概率m2取值為為0.1；自適應遺傳算法的i 取值為40代，k1和k2取值為0.95，k3和k4的取值為0.2。

表2 排樣空間尺寸和適應度對比

普通遺傳算法和自適應遺傳算法的排樣方案圖和適應度收斂曲線分別如圖6～9。

圖6 普通遺傳算法排樣方案

圖7 自適應遺傳算法排樣方案

圖8 普通遺傳算法收斂曲線

圖9 改進自適應遺傳算法收斂曲線

從仿真結果可以看到兩種算法都能夠得到一個較為優秀的排樣方案。改進自適應遺傳算法的排樣空間未利用率為0.0162 較普通遺傳算法的0.0201 低，即自適應遺傳算法得解較為優秀，可以證明應用改進自適應策略能夠提高遺傳算法的性能，即其對應的排樣方案的空間未利用率更低。

5.2 改進自適應遺傳算法的其它算例

表3 兩種算例的排樣空間尺寸和適應度

圖10 算例一排樣方案

圖11 算例二排樣方案

從以上的仿真可以看到本文中求解矩形排樣的方案能夠有效地求解不同尺寸排樣空間情況下的最優排樣方案，可以證明本文中方法的可行性和普遍適用性。

6 結語

本文提出了一種將自適應遺傳算法應用于求解矩形排樣問題的方法，提供了一種可行的高性能的求解方法，能夠求得一種排樣空間面積利用率最高的排樣方案。通過仿真可以證明，將改進自適應遺傳算法應用于矩形排樣問題的求解，能夠較普通遺傳算法得到一種更優秀的解，最終的排樣方案的空間未利用率能夠達到較低的水平。通過對不同的算例進行仿真，可以證明本文中求解矩形排樣的方案的可行性和普遍適用性。本文通過將改進自適應策略應用于遺傳算法，增強了算法全局搜索能力，使其在優化性能上得到提升，但是并未改變遺傳算法計算量較大，計算時間較長的缺點。在今后的研究中，需要在算法計算速度方面進行改進，以改善算法的計算效率。