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

武漢理工大學(xué)機(jī)電工程學(xué)院 武漢 430070

隨著我國(guó)科學(xué)技術(shù)的發(fā)展，機(jī)械制造加工業(yè)也快速發(fā)展，鋼結(jié)構(gòu)產(chǎn)品應(yīng)用廣泛，作為原材料鋼材的消耗量日益增加。對(duì)于以鋼結(jié)構(gòu)產(chǎn)品為主要生產(chǎn)對(duì)象的建材裝備企業(yè)來說，鋼材的費(fèi)用在生產(chǎn)成本中占了很大的比重，因此，企業(yè)在生產(chǎn)下料時(shí)，合理優(yōu)化矩形件排樣、提高板材利用率、降低生產(chǎn)加工成本是提升企業(yè)競(jìng)爭(zhēng)力的重要方式之一。

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

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

1 矩形件下料優(yōu)化問題數(shù)學(xué)模型

1.1 問題描述

矩形件下料優(yōu)化問題主要指以板材利用率最高作為目標(biāo)函數(shù)，即在給定長(zhǎng)、寬的矩形板材上以最優(yōu)方式切割出所需矩形零件[8]。某鋼結(jié)構(gòu)產(chǎn)品需要n種同材質(zhì)同厚度的矩形零件 Ri（i=1，2，...，n），其中矩形零件的面積表示為li×wi，每種零件所需個(gè)數(shù)為ai?，F(xiàn)設(shè)定矩形板材的寬度為W，長(zhǎng)度為L(zhǎng)，同時(shí)Ri、Rj互不重疊，i≠j，i、j=1、2、...、n；Ri、Rj必須放在板材內(nèi)。

1.2 數(shù)學(xué)模型

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

2 優(yōu)化模型求解

2.1 遺傳算法實(shí)現(xiàn)的基本要素

2.1.1 基因編碼策略

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

2.1.2 初始化種群

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

2.1.3 適應(yīng)度函數(shù)

遺傳算法中每個(gè)染色體質(zhì)量的優(yōu)劣是利用適應(yīng)度函數(shù)進(jìn)行評(píng)價(jià)的，染色體適應(yīng)度值越大，則其質(zhì)量越好。筆者主要考慮廢料再利用來定義適應(yīng)度函數(shù)F（P），即盡可能降低所需板材的最大高度，使其剩余原材料的高度仍在可利用范圍之內(nèi)，盡可能提高可再利用廢料的利用率。

2.1.4 遺傳算子

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

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

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

2.1.5 終止準(zhǔn)則

整個(gè)算法在解空間進(jìn)行搜索的過程中呈現(xiàn)收斂的趨勢(shì)，設(shè)定的終止準(zhǔn)則為：設(shè)定期望的板材利用率，如果在求解過程中，達(dá)到了預(yù)先設(shè)定值，則算法終止；否則當(dāng)遺傳代數(shù)達(dá)到預(yù)先設(shè)定迭代次數(shù)值時(shí)，算法終止。整個(gè)運(yùn)算過程中，適應(yīng)度值最大的染色體所對(duì)應(yīng)的排樣方案即為矩形件下料優(yōu)化的最優(yōu)解。

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

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

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

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

2.3 算法流程圖

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

3 計(jì)算實(shí)例

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

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

筆者選取了最優(yōu)排樣方案的收斂曲線和零件排放序列，板材利用率為95.73%，收斂曲線如圖3所示。根據(jù)得到的最大板材利用率的排樣順序，對(duì)其進(jìn)行自動(dòng)排樣，得到的排樣圖如圖4所示。

4 結(jié)束語(yǔ)

表1 零件數(shù)據(jù)

▲圖2 算法流程圖

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

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

▲圖4 優(yōu)化下料

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

[2]李波，王石，施松新，等.基于啟發(fā)式動(dòng)態(tài)分解算法的矩形件優(yōu)化排樣[J].計(jì)算機(jī)應(yīng)用，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]許繼影.矩形件優(yōu)化排樣的混合啟發(fā)式方法[J].計(jì)算機(jī)工程與應(yīng)用，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ìn)遺傳算法的矩形件排樣優(yōu)化算法[J].制造業(yè)自動(dòng)化，2013（19）：55-58.

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

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

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

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

[11]隗平平，劉斌.基于并行遺傳算法的矩形件排樣優(yōu)化[J].組合機(jī)床與自動(dòng)化加工技術(shù)，2011（3）：78-82.

[12]王竹婷，劉林，程浩，等.改進(jìn)的最低水平線搜索算法求解矩形排樣問題[J].工程設(shè)計(jì)學(xué)報(bào)，2009（2）：98-102.