基于改進遺傳算法的矩形件下料優化方法研究*

□ 劉淑偉 □ 郭順生 □ 郭 鈞 □ 杜百崗 □ 李西興

武漢理工大學機電工程學院 武漢 430070

隨著我國科學技術的發展，機械制造加工業也快速發展，鋼結構產品應用廣泛，作為原材料鋼材的消耗量日益增加。對于以鋼結構產品為主要生產對象的建材裝備企業來說，鋼材的費用在生產成本中占了很大的比重，因此，企業在生產下料時，合理優化矩形件排樣、提高板材利用率、降低生產加工成本是提升企業競爭力的重要方式之一。

矩形件優化排樣問題是指在給定的矩形板材上，將一系列矩形零件以板材利用率最大為目標，按最優方式進行排布。針對該問題，近幾十年來眾多國內外學者對其展開研究并提出了多種合理的、有效的求解算法和模型[1-3]。由于搜索空間隨問題規模的增大而急速增大，所以很多學者利用遺傳算法作為基礎算法并結合其它優化算法，構建組合算法來解決該問題模型。如文獻[4]中結合啟發式遞歸算法與遺傳算法，文獻[5]提出基于遺傳算法的混合元啟發式算法，文獻[6]基于對傳統遺傳算法的改進，主要引入分階段調整遺傳算子的策略，文獻[7]提出基于小生境技術的自適應遺傳模擬退火算法。以上算法對傳統的方法進行改進，在很多情況下可以得到較好的板材利用率和計算效率，但在實例應用中仍存在效果不佳的現象。

基于此，筆者采用基于遺傳算法和最低水平線法相結合來求解矩形件優化排樣問題，并引入不同階段不同遺傳算子，以避免在遺傳算子操作過程中出現優良基因的缺失。

1 矩形件下料優化問題數學模型

1.1 問題描述

矩形件下料優化問題主要指以板材利用率最高作為目標函數，即在給定長、寬的矩形板材上以最優方式切割出所需矩形零件[8]。某鋼結構產品需要n種同材質同厚度的矩形零件 Ri（i=1，2，...，n），其中矩形零件的面積表示為li×wi，每種零件所需個數為ai。現設定矩形板材的寬度為W，長度為L，同時Ri、Rj互不重疊，i≠j，i、j=1、2、...、n；Ri、Rj必須放在板材內。

1.2 數學模型

將所有矩形零件進行編碼處理，形成編碼集Ri、i∈N，N=｛1，2，...，n｝；L、W 為所用原材料的長度和寬度；li、wi為矩形件 Ri的長度和寬度；（xi、yi） 為 Ri的左下角點坐標；（xi′、yi′） 為 Ri的右上角點坐標；3 個二進制邏輯變量，ri=0或1，當零件Ri橫放時取1，反之取0；lij=0 或 1，當零件 Ri置于 Rj左側時取 1，反之取 0；bij=0或 1，當零件 Ri置于 Rj下側時取 1，反之取 0；H為所利用矩形板材的最大高度；F為原材料的利用率。目標函數：

2 優化模型求解

2.1 遺傳算法實現的基本要素

2.1.1 基因編碼策略

采用十進制編碼方法[9-10]，即將每一待排矩形零件進行整數編號，i=1、2、...、n，將 n 個 Ri的編號按照一定的順序排列， 即構成一個個體 P=｛p1，p2，...，pn｝，1≤|pi|≤n，即問題的一個解。每個基因代表一個Ri，并有正負之分，正號表示Ri橫放，即矩形零件的長度和板材的長度方向平行；負號則反之。如排列順序為（5、-1、3、2、-4），則對應染色體為｛5，-1，3，2，-4｝，此序列表示首先排5號零件，零件橫排；然后排1號零件，零件豎排；并以此類推，得到最終排樣圖。

2.1.2 初始化種群

在種群染色體初始化過程中，給定n個零件，隨機產生 m 條染色體 p1、p2、...、pm構成初始種群，筆者采用MATLAB中的Randperm（）函數和Rand（）函數結合來產生隨機序列，這樣既可以產生負數序列，也可避免非法子串的產生。針對文中的條件，經過多次測驗，在采用種群規模為40時，既能保證較高計算速率，也可以得到很好的板材利用率。

2.1.3 適應度函數

遺傳算法中每個染色體質量的優劣是利用適應度函數進行評價的，染色體適應度值越大，則其質量越好。筆者主要考慮廢料再利用來定義適應度函數F（P），即盡可能降低所需板材的最大高度，使其剩余原材料的高度仍在可利用范圍之內，盡可能提高可再利用廢料的利用率。

2.1.4 遺傳算子

（1）選擇算子。所采用的選擇算子為隨機聯賽選擇方法，即基于個體適應度值大小關系的選擇方法，通過對個體間的交叉、變異等不斷地產生新個體。雖然在這個過程中隨著種群的進化會產生更多優良個體，但由于過程中選擇、交叉、變異是隨機的，會造成部分最優個體的破壞，使適應度值下降，對算法的運行效率和收斂性造成影響，所以筆者采用精英保留策略來設定選擇算子。

（2）交叉算子。在遺傳算法中，交叉算子主要產生新個體，并決定了遺傳算法全局搜索的能力。采用順序交叉操作產生新的個體，此方法可將父代的基因順序重組，并且不會產生非法個體。以兩個父代染色體為例進行交叉操作， 詳細闡述順序交叉操作，P1：｛4，-3，9，7，-2，6，-8，5，1｝，P2：｛-5，7，2，-6，4，9，1，-3，-8｝。 首先，在1-9之間隨機產生兩個交叉點，如交叉點為3和6， 將父代分為 3 個部分， 即 P1：｛4，-3，9|7，-2，6|-8，5，1｝和 P2：｛-5，7，2|-6，4，9|1，-3，-8｝，交叉點之間的中間段保持不變， 得到：P1：｛x，x，x|7，-2，6|x，x，x｝ 和 P2：｛x，x，x|-6，4，9|x，x，x｝。 然后，記取父個體 2 從第二個交叉點開始的矩形件序號排列順序，當到達基因末尾時，返回染色體初始位置繼續記錄矩形件序號，直到第二個交叉點結束，這樣便得到了父個體2從第二個交叉點開始的矩形件序號排列順序為 （1、-3、-8、-5、7、2、-6、4、9）。 對于父個體 1 而言，已有零件 7、-2、6，將它們從父個體2的排列順序中去掉，得到排列順序（1、-3、-8、-5、4、9）， 再將這個排列順序復制給父個體 1，復制的起點也是從第二個交叉點開始，從而得到子個體1對應的整數串，這樣子個體1的排列順序為C1=｛-5，4，9|7，-2，6|1，-3，-8｝，同樣子個體 2 的排列順序為：C2=｛-3，7，-2|-6，4，9|-8，5，1｝。

（3）變異算子。采用旋轉變異，假設待排零件的總數為n，旋轉變異操作是在[1，n]之間產生一個隨機數b，將b位置上的零件序號轉換為其相反數，即將橫放矩形件轉換為豎放。

2.1.5 終止準則

整個算法在解空間進行搜索的過程中呈現收斂的趨勢，設定的終止準則為：設定期望的板材利用率，如果在求解過程中，達到了預先設定值，則算法終止；否則當遺傳代數達到預先設定迭代次數值時，算法終止。整個運算過程中，適應度值最大的染色體所對應的排樣方案即為矩形件下料優化的最優解。

2.2 基于最低水平線的搜索算法

在上述遺傳算法運行的過程中，首先進行種群初始化，產生一系列整數串，然后對每個個體的適應度值進行評價，在評價時需要將最初產生的染色體，即一串基因編碼，轉化成板材上的矩形零件，從而形成排樣圖，得到矩形零件所占板材的總面積，再進行比較優化。為了實現這一轉化，需要按照一定的啟發式算法將矩形零件進行排列，如BL算法、下臺階算法、最低水平線算法。BL算法擁有一定的局限性且易出現板材左側偏高的現象，而下臺階算法則容易導致板材右側偏高，相比之下，最低水平線算法可以有效地解決以上兩種算法存在的缺陷，在一定程度上實現板材利用率的提高[11]。但最低水平線法容易出現部分排樣高度偏高情況，造成板材最低水平線以上板料的浪費[12]。因此，提出在算法處理時首先向后搜索，將后面未排零件中選取寬度小于或等于最低水平線寬度的零件，與當前零件互換并進行排放，將最低水平線搜索算法嵌套在遺傳算法的適應度值函數中。設定最高輪廓線矩陣，記錄每次排放矩形件時的最高輪廓線，在適應度函數中嵌套排樣函數，當所有矩形零件按照排樣函數排放完畢后，按照最高輪廓錢矩陣中記錄的最大尺寸，即可求得板材的利用率。

▲圖1 基于最低水平線的搜索算法

對于給定排放序列（1，-2，3，-4｝的基于最低水平線搜索算法的排放過程如圖1所示，排放結束后，序列更新為｛1，-2，-4，3｝。

2.3 算法流程圖

結合上述遺傳算法和基于最低水平線搜索算法的過程，其算法總流程圖如圖2所示，其中FP為設定的期望板材率用率，gen為迭代次數，Gen為設定的迭代次數。

3 計算實例

為了驗證論文中所提出的矩形件下料優化算法的有效性，選取了某建材裝備企業某生產部件所需的矩形零件進行排樣計算。算法的參數設置為：種群規模Popsize=40，迭代次數Gen=200，交叉概率Pc=0.60，變異概率Pm=0.001。選取的排樣板材的長度L=2 000 mm，板材的寬度W=1 500 mm，待排矩形零件的尺寸數據見表1。

在上述算法參數設置的前提下，將算法重復運行10次。在10次運算過程中，遺傳算法所得到的排列順序和排樣圖都不同，重復運行10次的板材利用率平均值為94.63%。在10次運算結果中，94.26%出現3次，94.02%出現2次，95.73%出現2次，95.48%出現2次，93.06%出現1次。由上述結果可知，板材利用率最高值為95.73%。雖然在運算過程中，板材利用率出現相同現象，但零件排放序列卻是不同的。在實際應用算法運行時，可多次運行選取最優結果。

筆者選取了最優排樣方案的收斂曲線和零件排放序列，板材利用率為95.73%，收斂曲線如圖3所示。根據得到的最大板材利用率的排樣順序，對其進行自動排樣，得到的排樣圖如圖4所示。

4 結束語

表1 零件數據

▲圖2 算法流程圖

▲圖3 板材利用率收斂曲線

筆者以企業鋼結構件的下料過程為背景，建立矩形件下料優化數學模型，結合遺傳算法和基于最低水平線的搜索算法，對矩形件下料優化數學模型進行求解，獲得最優解，實現零件在原材料上的合理排樣，降低板材的浪費，提高板材利用率。在遺傳算法中，采用不同的合適的遺傳算子操作相結合的方法，進行個體的選擇、交叉和變異，在選擇操作中采用精英保留策略以避免優秀個體的缺失，然后利用適應度函數對每代的每個個體進行適應度值計算，多次迭代，直到算法終止，得到個體最優排布和板材的利用率，并自動繪制板材的排樣圖。提出的算法可以有效地提高板材的利用率，降低板材的消耗和生產成本，顯著提高企業的經濟效益和競爭力，具有重要的利用價值。

▲圖4 優化下料

[1]童科，毛力.基于蟻群優化算法求解矩形件排樣問題[J].計算機工程與科學，2011（7）：158-162.

[2]李波，王石，施松新，等.基于啟發式動態分解算法的矩形件優化排樣[J].計算機應用，2013（7）：1908-1911.

[3]Cui Yaodong，Lu Yiping.Heuristic Algorithm for a Cutting Stock Problem in the SteelBridge Construction [J].Computers and Operations Research，2009，36（2）：612-622.

[4]許繼影.矩形件優化排樣的混合啟發式方法[J].計算機工程與應用，2012（13）：234-239.

[5]Carlos G，Carlos A，Luis G.A Hybrid Approach Based on Genetic Algorithms to Solve the Problem ofCutting Structural Beams in a Metalwork Company [J].Journal of Heuristics，2013，19（2）：253-273.

[6]吳忻生，吳超成，劉海明.基于改進遺傳算法的矩形件排樣優化算法[J].制造業自動化，2013（19）：55-58.

[7]董德威，顏云輝，張堯，等.矩形件優化排樣的自適應遺傳模擬退火算法[J].中國機械工程，2013（18）：2499-2504.

[8]王淑青，雷蕾，曾仕琦，等.基于改進遺傳算法的二維圖形優化排樣方法[J].工業控制計算機，2012（12）：51-53.

[9]劉瓊，張超勇，饒運清，等.改進遺傳算法解決柔性作業車間調度問題[J].工業工程與管理，2009（2）：59-66.

[10]李明，黃平捷，周澤魁.基于小生境遺傳算法的矩形件優化排樣[J].湖南大學學報（自然科學版），2009（1）：46-49.

[11]隗平平，劉斌.基于并行遺傳算法的矩形件排樣優化[J].組合機床與自動化加工技術，2011（3）：78-82.

[12]王竹婷，劉林，程浩，等.改進的最低水平線搜索算法求解矩形排樣問題[J].工程設計學報，2009（2）：98-102.