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

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

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

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

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

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

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

　此時(shí)排樣圖的最高輪廓線為(516.25，40，157)，其中高度為157。排樣圖的適應(yīng)度為：0.784。
經(jīng)過(guò)遺傳算法的迭代求解，排樣圖的整體高度已經(jīng)有了很大的改進(jìn)。
對(duì)于求解不規(guī)則區(qū)域的排樣，本文在最低水平線的基礎(chǔ)上提出了改進(jìn)，并利用遺傳算法，使不規(guī)則區(qū)域的面積利用率更為有效。
　在研究不規(guī)則區(qū)域排樣的問(wèn)題中，需要考慮的是整體排樣圖的高度。利用所給的布局函數(shù)和目標(biāo)函數(shù)值，確定整體排樣圖的高度。本文提出的搜索算法中的前后端搜索方式還有待改進(jìn)。不規(guī)則區(qū)域的布局可以使用本文算法。由于變異算子、交叉算子等數(shù)值對(duì)遺傳算法的影響，本文在適應(yīng)度方面還有待改進(jìn)，可以提高效率。
參考文獻(xiàn)
[1] 趙新芳，崔耀東，楊瑩，等.矩形件帶排樣的一種遺傳算法[J].計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào)，2008(4).
[2] 龔志輝，黃星梅.二維矩形件優(yōu)化排樣算法的改進(jìn)研究[J].湖南大學(xué)學(xué)報(bào)(自然科學(xué)版)，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ó)富，羅陽(yáng).二維不規(guī)則零件排放問(wèn)題的遺傳算法求解[J].計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào)，2002，14(5)：467-470.
[5] 龔志輝.基于遺傳算法的矩形件優(yōu)化排樣系統(tǒng)研究 [D].長(zhǎng)沙：湖南大學(xué)，2003.
[6] 黃紅兵.矩形毛坯優(yōu)化排樣算法的改進(jìn)[J].機(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.