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

　矩形件帶排樣問題(RSPP)是在不規(guī)則板材上布置多個(gè)大小不同的矩形零件,，并滿足以下約束條件：(1)零件排放在板材內(nèi)部,；(2)各零件之間互不重疊；(3)滿足一定的工藝要求,。其優(yōu)化目標(biāo)是尋求一個(gè)零件布局方案,，使得浪費(fèi)的板材面積最小，亦材料的利用率最大,。排樣問題對造船,、服裝、模具等材料加工行業(yè)有重要意義,，材料利用率的提高可直接降低材料浪費(fèi),，提高經(jīng)濟(jì)效益，也符合當(dāng)今創(chuàng)建節(jié)約型社會(huì)的需求,。
與參考文獻(xiàn)[1]中的矩形件帶排樣相比,，不規(guī)則區(qū)域的排樣增加了對板材兩端空洞的利用，實(shí)際上增加了兩端空洞排樣時(shí)的搜索,，所以不規(guī)則區(qū)域的排樣問題在幾何計(jì)算方面的復(fù)雜度較高,。在滿足約束條件的情況下，矩形排樣的最低最左原則或最低水平線原則在不規(guī)則區(qū)域排樣的情況下已不能滿足需要,，最低最左等傳統(tǒng)放置方法將導(dǎo)致較大的空白區(qū)域無法利用。
　最大限度地節(jié)約材料,、提高材料利用率是生產(chǎn)中提高效益的一個(gè)重要手段,。由于排樣問題的廣泛存在，如板金下料,、報(bào)刊排版,、服裝裁剪等，都需要在可接受的時(shí)間里得到最優(yōu)或近似解,。
參考文獻(xiàn)[1-3]中提到的利用遺傳算法求解的矩形件排樣問題,，均采用遺傳算法和改進(jìn)的最低水平算法進(jìn)行計(jì)算，利用此方式對不規(guī)則區(qū)域排樣,，得到的排樣圖出現(xiàn)明顯的空洞,。本文提出一種新方法,，通過對板材兩端空洞的利用，提高板材的利用率,。
1 算法描述
1.1 本文改進(jìn)遺傳算法流程圖
　本文采用十進(jìn)制的編碼方式對每一個(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è)體),。
初始種群的好壞對遺傳算法的收斂速度和求解質(zhì)量有較大的影響,。本文在初始種群時(shí)，分析了矩形零件的數(shù)據(jù)特點(diǎn),，采用經(jīng)驗(yàn)選擇與隨機(jī)生成相結(jié)合的初始方法,，大矩形件排放完后再排小矩形，材料利用率不會(huì)太低,。
　算法開始,，首先將零件根據(jù)面積降序排列，面積相等時(shí)根據(jù)長度降序排列,，產(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è)體對應(yīng)的零件固定序列快速地求出其對應(yīng)的排樣圖，得到所需要占據(jù)的板材高度,，才能計(jì)算其適應(yīng)度值,，從而對該個(gè)體進(jìn)行評價(jià),。本文在文獻(xiàn)[1]方法的基礎(chǔ)上提出一種基于最低水平線的擇優(yōu)插入算法，對給定的零件固定序列進(jìn)行優(yōu)化排樣,，降低排樣高度,，使零件排放緊湊，提高材料利用率,。
　針對不規(guī)則區(qū)域的排樣時(shí),，利用此算法的搜索策略有兩種方案：一種是向后搜索到一個(gè)可以放下的零件時(shí)馬上停止搜索；另一種是向后搜索所有可以放下的零件,，再從中選擇一個(gè)寬度最大的,，使空間得到較為有效的利用。本文采用第二種方案,。
　當(dāng)搜索到最優(yōu)零件后,，參考文獻(xiàn)[2]中采用的是“互換”兩個(gè)零件位置的方式。如果最優(yōu)零件位置比較靠后,，且最優(yōu)零件小于當(dāng)前排放零件面積,，則當(dāng)前面積較大的零件就會(huì)調(diào)整到后面的位置。如此多次搜索,、互換零件位置可能造成在排樣的前期將較小尺寸的零件全部利用掉,，后期剩下的都是大尺寸零件；而較大尺寸的零件對排樣高度的影響較大,，這樣可能會(huì)出現(xiàn)即使前期得到的排樣圖零件緊湊,、空洞較小，但后期總體排樣高度驟增的情況,，導(dǎo)致得不到高質(zhì)量的排樣圖,。
　此時(shí)采用文中的插入策略，將此時(shí)搜索到的最優(yōu)零件直接插入到當(dāng)前的零件之前,。
在零件排放過程中會(huì)出現(xiàn)多段最高輪廓線,，如圖2所示，最低水平線為當(dāng)前所有輪廓線中最低的一段,。如有數(shù)段,，選擇最左的一段，其位置和長度在整個(gè)排樣的過程中不斷變化,，如圖2所示。本文提出了一種基于最低水平線搜索算法,，步驟如下：

　(1)設(shè)置初始最高輪廓線為板材的最下面的邊(板材在豎直方向無限高),。
　(2)當(dāng)前要排入的零件為Pi，當(dāng)前最低水平線為Llowest,，比較是否大于或等于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)
　基于最低水平線,，對于不規(guī)則區(qū)域的矩形件排樣，采用掃描的方式找出不規(guī)則區(qū)域中最低且能排入此矩形件的水平線,。按照最低水平線得到圖2,。
如圖2，可以明顯看出,，在①中可以插入后面的更小的矩形件,，或者將4或5塞入其中，可以減少總排樣圖的高度,。在②中可以將2插入其中,，這樣也完全可以增加不規(guī)則區(qū)域的利用，減少總排樣圖的高度,。
1.3 本文改進(jìn)算法
　當(dāng)每排完一個(gè)矩形件,，依照上述算法就要更新最低水平線，此時(shí)只適合針對矩形板材的排樣,，不規(guī)則區(qū)域的排樣會(huì)出現(xiàn)上述大規(guī)模的空間浪費(fèi),。
　本文提出基于最低水平線的改進(jìn)算法：在更新水平線的同時(shí)，需判斷水平線首尾元素的寬度是否為0,，如果不為0,，則要在首元素添加頭元素：先取得首元素指針head，過點(diǎn)(head->left,，head->high)與不規(guī)則區(qū)域相交,，取下面的一點(diǎn)pt。新增line對象,，line(pt.x,，0,，pt.y)，將pt添加到首元素,。判斷水平線尾元素與判斷首元素類似,。
　針對最低水平線搜索算法的改進(jìn)算法的步驟如下：
　(1)判斷底邊是否水平，若水平且能排入當(dāng)前的矩形件,，則排入零件,；否則向上掃描直至找到能排入的水平線段，排入零件,。
　(2)當(dāng)前要排入的零件Pi,，當(dāng)前水平線為Llowest，判斷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)過本文改進(jìn)算法的排入圖,，零件總排樣高度有了明顯降低，整個(gè)優(yōu)化排樣過程都緊湊地排放零件,，使不規(guī)則區(qū)域的“空洞”區(qū)域得到了有效利用,，提高了材料利用率。有效地將最低水平線算法在不規(guī)則區(qū)域排樣領(lǐng)域應(yīng)用。

2 遺傳算法的過程
2.1 遺傳算子
　(1)交叉算子,。將父輩種群中的個(gè)體隨機(jī)兩兩配對,，進(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)變異算子,。對交叉操作產(chǎn)生的子代個(gè)體,，利用兩種變異算子進(jìn)行變異：①旋轉(zhuǎn)變異。在1∪n范圍內(nèi)隨機(jī)產(chǎn)生一個(gè)旋轉(zhuǎn)位,，以概率Pm1對子代個(gè)體中位于其后的矩形零件進(jìn)行旋轉(zhuǎn),；②顛倒變異。在1∪n范圍內(nèi)隨機(jī)產(chǎn)生2個(gè)變異位,，以概率Pm2對子代個(gè)體中兩個(gè)變異位之間的所有零件顛倒順序,。
當(dāng)零件個(gè)數(shù)較少時(shí)，顛倒變異可以提高算法的局部搜索能力,。而零件個(gè)數(shù)較多時(shí),，解碼過程中動(dòng)態(tài)調(diào)整動(dòng)作相應(yīng)增多，則在遺傳過程中的順序調(diào)整意義不大,。所以解決大規(guī)模矩形件排樣問題時(shí),，只考慮旋轉(zhuǎn)變異。
　(3)選擇算子,。對變異后的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ù)
　遺傳算法對一個(gè)解的好壞用適應(yīng)度函數(shù)進(jìn)行評價(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)度作為評價(jià)參數(shù),，得到如圖5所示的排樣圖,。

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