基于自適應(yīng)遺傳算法的矩形排樣方法研究*

單宇晗

（哈爾濱工程大學(xué)自動化學(xué)院 哈爾濱 150001）

1 引言

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

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

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

2 矩形排樣問題模型

2.1 問題模型

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

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

約束條件：

目標(biāo)函數(shù)：

2.2 最低水平線算法

對所有的矩形進(jìn)行編號以后，通過最低水平線法確定待排樣矩形的放置規(guī)律，能夠?qū)⑷魏我环N布列的方案都唯一表示為n個矩形{Pi，i=1…n}的一種排列組合［7～9］。

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

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

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

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

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

3）轉(zhuǎn)到1），直到找到位置放置待放置的矩形。

Step3：轉(zhuǎn)到Step2，直至所有的矩形放置結(jié)束。

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

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

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

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

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

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

3 普通遺傳算法

3.1 遺傳算法

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

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

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

2）適應(yīng)度函數(shù)。優(yōu)化問題的目標(biāo)函數(shù)代表問題的期望優(yōu)化結(jié)果，排樣問題的優(yōu)化目標(biāo)是排樣空間的剩余空間最小，這里可以使用排樣空間剩余面積占總面積的比例，即排樣空間未利用率作為適應(yīng)度函數(shù)的數(shù)值。

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

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

圖2 選擇交叉部分示意圖

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

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

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

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

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

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

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

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

圖5 變異操作示意圖

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

3.2 遺傳算法實現(xiàn)步驟

普通遺傳算法的實現(xiàn)過程如下

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

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

Step3：判斷是否達(dá)到最大迭代數(shù)，如果達(dá)到則轉(zhuǎn)到Step5。

Step4：進(jìn)行遺傳操作：選擇、交叉、變異。產(chǎn)生下一代種群，并轉(zhuǎn)到Step3。

Step5：對最后一代種群中的最優(yōu)個體進(jìn)行解碼，得到矩形排樣的最優(yōu)方案。

4 改進(jìn)自適應(yīng)遺傳算法

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

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

可以將整個運算過程分為兩個部分：在第i 代之前執(zhí)行固定的交叉概率m1和變異概率m2，這樣保證存在足夠多的個體發(fā)生交叉和變異，從而保證種群的多樣性；在第i 代之后執(zhí)行自適應(yīng)交叉概率Pc和變異概率Pm，這樣能夠根據(jù)當(dāng)前種群的實際環(huán)境自適應(yīng)調(diào)節(jié)概率，從而提高算法的性能。

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

自適應(yīng)交叉概率Pc：

其中fc為發(fā)生交叉的兩個個體適應(yīng)度較高的適應(yīng)度的大小，k1和k2為0～1的常數(shù)，且k1≥k2。

自適應(yīng)變異概率Pm：

其中fm為當(dāng)前變異個體的適應(yīng)度的大小，k3和k4為0～1的常數(shù)，且k3≥k4。

5 仿真和結(jié)果分析

應(yīng)用自適應(yīng)遺傳算法求解矩形排樣，在Mat?lab2012a環(huán)境下進(jìn)行仿真，并進(jìn)行結(jié)果分析。

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

表1 排樣用矩形尺寸

5.1 普通遺傳算法和改進(jìn)自適應(yīng)遺傳算法仿真

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

表2 排樣空間尺寸和適應(yīng)度對比

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

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

圖7 自適應(yīng)遺傳算法排樣方案

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

圖9 改進(jìn)自適應(yīng)遺傳算法收斂曲線

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

5.2 改進(jìn)自適應(yīng)遺傳算法的其它算例

表3 兩種算例的排樣空間尺寸和適應(yīng)度

圖10 算例一排樣方案

圖11 算例二排樣方案

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

6 結(jié)語

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