摘  要： 采用遺傳算法解決不規(guī)則區(qū)域的矩形件帶排樣問題，用有序的帶符號整數(shù)串作為初始種群個體，改善了初始個體解的質(zhì)量。提出基于最低水平線的擇優(yōu)插入算法，同時考慮不規(guī)則區(qū)域的左右兩端區(qū)域，選取最適合的零件進行填充，使零件排放緊湊，提高了材料的利用率。
關鍵詞： 遺傳算法；排樣；最低水平線

　矩形件帶排樣問題(RSPP)是在不規(guī)則板材上布置多個大小不同的矩形零件，并滿足以下約束條件：(1)零件排放在板材內(nèi)部；(2)各零件之間互不重疊；(3)滿足一定的工藝要求。其優(yōu)化目標是尋求一個零件布局方案，使得浪費的板材面積最小，亦材料的利用率最大。排樣問題對造船、服裝、模具等材料加工行業(yè)有重要意義，材料利用率的提高可直接降低材料浪費，提高經(jīng)濟效益，也符合當今創(chuàng)建節(jié)約型社會的需求。
與參考文獻[1]中的矩形件帶排樣相比，不規(guī)則區(qū)域的排樣增加了對板材兩端空洞的利用，實際上增加了兩端空洞排樣時的搜索，所以不規(guī)則區(qū)域的排樣問題在幾何計算方面的復雜度較高。在滿足約束條件的情況下，矩形排樣的最低最左原則或最低水平線原則在不規(guī)則區(qū)域排樣的情況下已不能滿足需要，最低最左等傳統(tǒng)放置方法將導致較大的空白區(qū)域無法利用。
　最大限度地節(jié)約材料、提高材料利用率是生產(chǎn)中提高效益的一個重要手段。由于排樣問題的廣泛存在，如板金下料、報刊排版、服裝裁剪等，都需要在可接受的時間里得到最優(yōu)或近似解。
參考文獻[1-3]中提到的利用遺傳算法求解的矩形件排樣問題，均采用遺傳算法和改進的最低水平算法進行計算，利用此方式對不規(guī)則區(qū)域排樣，得到的排樣圖出現(xiàn)明顯的空洞。本文提出一種新方法，通過對板材兩端空洞的利用，提高板材的利用率。
1 算法描述
1.1 本文改進遺傳算法流程圖
　本文采用十進制的編碼方式對每一個矩形零件進行編碼，將每一個矩形編號，i=1，2，…，n，零件編號構(gòu)成一個整數(shù)串P={p1，p2，…，pn}，1≤Pi≤n，表示了一種排樣圖(即一個個體)。
初始種群的好壞對遺傳算法的收斂速度和求解質(zhì)量有較大的影響。本文在初始種群時，分析了矩形零件的數(shù)據(jù)特點，采用經(jīng)驗選擇與隨機生成相結(jié)合的初始方法，大矩形件排放完后再排小矩形，材料利用率不會太低。
　算法開始，首先將零件根據(jù)面積降序排列，面積相等時根據(jù)長度降序排列，產(chǎn)生一個有序整數(shù)串，再隨機產(chǎn)生m個個體，構(gòu)成初始種群。利用每個個體排列所得排樣圖的高度計算得出該個體的適應度值，進行選擇、交叉和變異之后，再判斷是否達到了計算次數(shù)或得到了滿意的結(jié)果。如果沒有達到，則返回重新計算每個個體的適應度值；否則，算法就結(jié)束。算法流程如圖1所示。

1.2 基于最低水平線的算法
　由遺傳算法產(chǎn)生一個個體編碼后，只有將此個體對應的零件固定序列快速地求出其對應的排樣圖，得到所需要占據(jù)的板材高度，才能計算其適應度值，從而對該個體進行評價。本文在文獻[1]方法的基礎上提出一種基于最低水平線的擇優(yōu)插入算法，對給定的零件固定序列進行優(yōu)化排樣，降低排樣高度，使零件排放緊湊，提高材料利用率。
　針對不規(guī)則區(qū)域的排樣時，利用此算法的搜索策略有兩種方案：一種是向后搜索到一個可以放下的零件時馬上停止搜索；另一種是向后搜索所有可以放下的零件，再從中選擇一個寬度最大的，使空間得到較為有效的利用。本文采用第二種方案。
　當搜索到最優(yōu)零件后，參考文獻[2]中采用的是“互換”兩個零件位置的方式。如果最優(yōu)零件位置比較靠后，且最優(yōu)零件小于當前排放零件面積，則當前面積較大的零件就會調(diào)整到后面的位置。如此多次搜索、互換零件位置可能造成在排樣的前期將較小尺寸的零件全部利用掉，后期剩下的都是大尺寸零件；而較大尺寸的零件對排樣高度的影響較大，這樣可能會出現(xiàn)即使前期得到的排樣圖零件緊湊、空洞較小，但后期總體排樣高度驟增的情況，導致得不到高質(zhì)量的排樣圖。
　此時采用文中的插入策略，將此時搜索到的最優(yōu)零件直接插入到當前的零件之前。
在零件排放過程中會出現(xiàn)多段最高輪廓線，如圖2所示，最低水平線為當前所有輪廓線中最低的一段。如有數(shù)段，選擇最左的一段，其位置和長度在整個排樣的過程中不斷變化，如圖2所示。本文提出了一種基于最低水平線搜索算法，步驟如下：

　(1)設置初始最高輪廓線為板材的最下面的邊(板材在豎直方向無限高)。
　(2)當前要排入的零件為Pi，當前最低水平線為Llowest，比較是否大于或等于Pi。若大于，則將Pi在Llowest上排放，更新最高輪廓線；否則，在序列中從Pi位置開始向后搜索一個可以排放的零件，同時互換這兩個零件的位置；如果沒有搜索到，則將Llowest提升至與其相鄰且高度較低的一段平齊，更新最高輪廓線。
重復(2)，直至所有零件排放完畢。
　其中水平線屬性為：
　class line{double left；//水平線左端點的橫坐標
　double wide；//水平線的寬度
　double high；}；//左端點的縱坐標
　基于最低水平線，對于不規(guī)則區(qū)域的矩形件排樣，采用掃描的方式找出不規(guī)則區(qū)域中最低且能排入此矩形件的水平線。按照最低水平線得到圖2。
如圖2，可以明顯看出，在①中可以插入后面的更小的矩形件，或者將4或5塞入其中，可以減少總排樣圖的高度。在②中可以將2插入其中，這樣也完全可以增加不規(guī)則區(qū)域的利用，減少總排樣圖的高度。
1.3 本文改進算法
　當每排完一個矩形件，依照上述算法就要更新最低水平線，此時只適合針對矩形板材的排樣，不規(guī)則區(qū)域的排樣會出現(xiàn)上述大規(guī)模的空間浪費。
　本文提出基于最低水平線的改進算法：在更新水平線的同時，需判斷水平線首尾元素的寬度是否為0，如果不為0，則要在首元素添加頭元素：先取得首元素指針head，過點(head->left，head->high)與不規(guī)則區(qū)域相交，取下面的一點pt。新增line對象，line(pt.x，0，pt.y)，將pt添加到首元素。判斷水平線尾元素與判斷首元素類似。
　針對最低水平線搜索算法的改進算法的步驟如下：
　(1)判斷底邊是否水平，若水平且能排入當前的矩形件，則排入零件；否則向上掃描直至找到能排入的水平線段，排入零件。
　(2)當前要排入的零件Pi，當前水平線為Llowest，判斷Llowest->wide與Pi.wide的關系。若Llowest->wide大于或等于Pi.wide，則轉(zhuǎn)入(3)，否則轉(zhuǎn)入(4)。
　(3)判斷排入到該水平線上的零件是否超出不規(guī)則邊界。如果此時的零件沒有超出不規(guī)則區(qū)域，則排入此零件，且更新水平線。否則，此時的零件超出了不規(guī)則區(qū)域，如果超出了右側(cè)邊界，則不能排入此零件，同時向后搜索能夠排入的零件，如果搜索不到則直接更新水平線。如果超出了左邊界，則向右移動此零件直至不超出邊界，移動距離為s，移動之后的零件Pi仍大于Llowest-s，則排入此零件。如果移動之后的零件Pi小于Llowest-s，則需向后搜索能夠排入且不超出邊界的零件，如果搜索不到則直接更新水平線。搜索到了則將該零件排入到當前水平線上，同時更新水平線?；氐?2)。
　(4)判斷此時的Llowest是否是最低水平線段的首元素或尾元素。如果不是，則在序列中從Pi位置開始向后搜索一個可以排放的零件，同時將這個零件插入到Pi之前的位置；如果沒有搜索到，則將Llowest提升至與其相鄰且高度較低的一段平齊，更新水平線。如果是，則轉(zhuǎn)入(5)。
　(5)如果Llowest是最低水平線段的首元素，則獲取此段水平線的下一個元素next，求得點(next->left，next->high)到不規(guī)則區(qū)域左側(cè)邊的距離為d，此時且有零件序列中寬度最小元素Plowest。如果d小于Plowest.wide，則更新next，將Llowest->left賦給next->left，同時next的寬度增加d，同時刪除首元素。如果Pi.wide大于或等于d，則在序列中從Pi位置開始向后搜索一個可以排放的wide最大的零件，同時將此時找到的元素插入到當前Pi的前面；如果沒有搜索到，則同樣更新next，同時刪除首元素。否則Pi.wide小于d，則此時可以將此零件排入首元素，從下往上掃描，直到找到大于或等于Pi.wide的線段為止，之后更新水平線。如果是最低水平線的尾元素，此時與首元素的處理類似。
重復(2)，直至所有零件排放完畢。
　由圖3可以看出，經(jīng)過本文改進算法的排入圖，零件總排樣高度有了明顯降低，整個優(yōu)化排樣過程都緊湊地排放零件，使不規(guī)則區(qū)域的“空洞”區(qū)域得到了有效利用，提高了材料利用率。有效地將最低水平線算法在不規(guī)則區(qū)域排樣領域應用。

2 遺傳算法的過程
2.1 遺傳算子
　(1)交叉算子。將父輩種群中的個體隨機兩兩配對，進行單點交叉操作，產(chǎn)生m個新個體構(gòu)成種群。設隨機選定的2個進行交叉的個體分別為P={p1，p2，…，pn}和Q={q1，q2，…，qn}。單點交叉是在1∪n范圍內(nèi)隨機生成一個交叉位t，從P中將位于t之前的元素拷貝至子代個體I1中作為前面的元素，P中未拷貝元素按Q中出現(xiàn)的先后順序拷貝至I2；同樣的方法可以產(chǎn)生另一新個體I2。
　(2)變異算子。對交叉操作產(chǎn)生的子代個體，利用兩種變異算子進行變異：①旋轉(zhuǎn)變異。在1∪n范圍內(nèi)隨機產(chǎn)生一個旋轉(zhuǎn)位，以概率Pm1對子代個體中位于其后的矩形零件進行旋轉(zhuǎn)；②顛倒變異。在1∪n范圍內(nèi)隨機產(chǎn)生2個變異位，以概率Pm2對子代個體中兩個變異位之間的所有零件顛倒順序。
當零件個數(shù)較少時，顛倒變異可以提高算法的局部搜索能力。而零件個數(shù)較多時，解碼過程中動態(tài)調(diào)整動作相應增多，則在遺傳過程中的順序調(diào)整意義不大。所以解決大規(guī)模矩形件排樣問題時，只考慮旋轉(zhuǎn)變異。
　(3)選擇算子。對變異后的m個子代個體依次求解其適應度，并分別與其父輩個體的適應度進行比較，若大于其父輩個體的適應度值，則接收此子代個體，替換其父輩個體作為下一代的父輩個體；否則，不接收此子代個體，其父輩個體直接進化，作為下一代的父輩個體。
2.2 適應度函數(shù)
　遺傳算法對一個解的好壞用適應度函數(shù)進行評價，適應度越大，解的質(zhì)量越好。本文采用參考文獻[2]中的適應度函數(shù)f(p)=Area/Area0，其中Area是矩形零件的總面積，Area0是排樣圖最大高度以下的面積，適應度值最大為1。
2.3 終止準則
　重復執(zhí)行，直到最好解的適應度達到要求或滿足預定的進化代數(shù)，停止計算，輸出最優(yōu)解。
3 實驗計算
　依據(jù)表1所給數(shù)據(jù)，在改進遺傳算法的基礎上做了一組實驗。

　采用遺傳算法和最低水平線進行計算，設定板材的端點順時針為(300，50)(100，150)(250，350)(500，300)(600，100)，得出如圖4所示的排樣圖。

　此時排樣圖的最高輪廓線為(383.5，80，146)，其中高度為146。上述排樣圖的適應度為0.723。
采用遺傳算法進行計算，設定種群規(guī)模m=20。迭代100次計算20次，取其平均適應度作為評價參數(shù)，得到如圖5所示的排樣圖。

　此時排樣圖的最高輪廓線為(516.25，40，157)，其中高度為157。排樣圖的適應度為：0.784。
經(jīng)過遺傳算法的迭代求解，排樣圖的整體高度已經(jīng)有了很大的改進。
對于求解不規(guī)則區(qū)域的排樣，本文在最低水平線的基礎上提出了改進，并利用遺傳算法，使不規(guī)則區(qū)域的面積利用率更為有效。
　在研究不規(guī)則區(qū)域排樣的問題中，需要考慮的是整體排樣圖的高度。利用所給的布局函數(shù)和目標函數(shù)值，確定整體排樣圖的高度。本文提出的搜索算法中的前后端搜索方式還有待改進。不規(guī)則區(qū)域的布局可以使用本文算法。由于變異算子、交叉算子等數(shù)值對遺傳算法的影響，本文在適應度方面還有待改進，可以提高效率。
參考文獻
[1] 趙新芳，崔耀東，楊瑩，等.矩形件帶排樣的一種遺傳算法[J].計算機輔助設計與圖形學學報，2008(4).
[2] 龔志輝，黃星梅.二維矩形件優(yōu)化排樣算法的改進研究[J].湖南大學學報(自然科學版)，2003，30(3)：47-49.
[3] HOPPER E， Turton B C H. A review of the application of metaheuristic algorithms to 2D strip packing problems [J]. Artificial Intelligence Review， 2001，16(4)： 257-300.
[4] 賈志欣，殷國富，羅陽.二維不規(guī)則零件排放問題的遺傳算法求解[J].計算機輔助設計與圖形學學報，2002，14(5)：467-470.
[5] 龔志輝.基于遺傳算法的矩形件優(yōu)化排樣系統(tǒng)研究 [D].長沙：湖南大學，2003.
[6] 黃紅兵.矩形毛坯優(yōu)化排樣算法的改進[J].機械工程師，2004(11)：12-14.
[7] HOPPER E， Turton B C H. An empirical investigation of metaheuristic and heuristic algorithms for a 2D packing problem[J]. European Journal of Operational Research， 2001， 128(1)：34-57.
[8] Zhang D， Kang Y， Deng A. A new heuristic recursive algorithm for the strip rectangular packing problem[J]. Computers & Operations Research， 2006， 33(8)：2209-2217.
[9] Zhang D， Liu Y， Chen S， et al. A meta-heuristic algorithm for the strip rectangular packing problem [M].Lecture Notes in Computer Science. Heidelberg： Springer， 2005，612： 1235-1241.