鈑金件剩余矩形排樣遺傳優(yōu)化方法研究＊

孫 波，李粉利，劉 璐，劉 崢

（西安工業(yè)大學 機電工程學院，西安710021）

研究板材的排樣問題，可以有效提高鈑金材料的利用率，從而降低生產(chǎn)成本，對提高企業(yè)的經(jīng)濟效益意義重大．在20世紀30年代，Kantorovich首先提出了排樣問題．隨著研究的不斷深入，國外許多學者對排樣問題進行了研究，同時提出了很多可行的排樣算法．文獻［1］將人的經(jīng)驗和啟發(fā)式思想融合，應用于矩形件的排樣中，根據(jù)矩形件的長和寬判定排樣順序，并依照最左最下原則，優(yōu)先將矩形件排放到板材的左下角．文獻［2］將不規(guī)則件擬合為凸多邊形，再將凸多 邊形組合為正六邊形，然后對不規(guī)則件求解排樣問題．文獻［3］在解決定寬無限長板材的排樣問題中使用了神經(jīng)網(wǎng)絡法、遺傳算法等，并把遺傳算法與模擬退火算法結合，通過對實例進行計算、分析評價，證明了多種算法結合求解排樣問題比單一排樣算法效果更好．國內(nèi)研究起步較晚，從20世紀80年代開始研究排樣問題．文獻［4］將遺傳算法與改進后的下臺階（Bench Lower，BL）算法應用于矩形件排樣問題，取得了較好的排樣效果．文獻［5］將遺傳算法和模擬退火算法結合應用于矩形件排樣，利用遺傳算法的全局尋優(yōu)能力找到排列最緊密的次序，然后結合填充算法填充空余部分．文獻［6］用包絡矩形法求解不規(guī)則件的排樣問題，最后將矩形還原為多邊形，避免了不規(guī)則件直接排樣．文獻［7］用離散網(wǎng)格表示不規(guī)則件，加速了重疊零件的判斷．文獻［8］將遺傳算法應用于解決不規(guī)則件的排樣優(yōu)化問題．

本文旨在對剩余矩形排樣算法進行改進，并結合遺傳算法，提出一個有效的求解矩形排樣優(yōu)化的方法，以期提高鈑金材料的利用率．

1 剩余矩形排樣算法的優(yōu)化

對于鈑金件展開后的排樣問題，目前比較有效的方法是先轉(zhuǎn)化為包絡矩形排樣問題．剩余矩形排樣算法，是目前較為有效的一種算法．該算法需要計算板材上所有未被利用的剩余空間，考慮將待排放的矩形件插入到板材任何可能的空白區(qū)域中，可以有效提高鈑金材料的利用率．將剩余矩形排樣算法與遺傳算法等智能算法聯(lián)合使用，能夠得到更好的排樣效果．

1．1 剩余矩形排樣算法的改進

剩余矩形排樣算法用矩形數(shù)據(jù)集合來表示板材中剩余的未排樣的空白區(qū)域，沒有被利用的區(qū)域都會記錄到剩余矩形集合中．根據(jù)剩余矩形集合中的記錄位置按照優(yōu)先最左最下排樣原則選擇一個位置來插入待排放的矩形件．剩余矩形排樣算法在一定程度上能有效的提高鈑金材料的利用率，但是對于某些排樣序列來說，并未起到有效利用材料的目的，如圖1所示，圖中1，2，3，4為矩形件編號．在圖1（a）中，矩形件4的高度大于板材下方空白矩形區(qū)域的高度，此時它就不能插入到此位置，只能尋找下一個矩形區(qū)域來排放．此時板材下方的區(qū)域閑置，就導致了鈑金材料的浪費．若將矩形件4旋轉(zhuǎn)90°，則正好可以插入到板材的下部區(qū)域，如圖1（b）所示．與圖1（a）相比，圖1（b）有效地提高了板材利用率．可見，將矩形件轉(zhuǎn)動90°后優(yōu)先考慮將其排放到位置最低的剩余矩形中，可以有效降低排樣圖的最大高度．

圖1 剩余矩形排樣算法的改進Fig．1 Improving the surplus rectangle layout algorithm

但在有些條件下，將矩形件轉(zhuǎn)動90°后排樣會增大排樣圖的最大高度，因而不適宜轉(zhuǎn)動后排樣，如圖2所示，圖中1，2為矩形件編號．在圖2（a）中，插入矩形件1后，板材上有兩個剩余矩形，分別是陰影部分和矩形件1上方的部分．矩形件2的寬度大于最低剩余矩形的寬度，因此不能將矩形件2直接插入最低剩余矩形來排樣；若將矩形件2轉(zhuǎn)動90°后插入，雖然可以插入，但是排樣后的已用板材的最大高度較大．而不轉(zhuǎn)動，直接將矩形件2左對齊排放在矩形件1的上方，而此時已用的板材的最大高度較?。?/p>

鑒于以上情況，排樣時不能簡單的以轉(zhuǎn)動或者不轉(zhuǎn)動的方式來排樣，還需考慮已用板材的最大高度．下面以4個矩形件為例，說明改進的剩余矩形排放算法的具體步驟．板材和矩形件的信息見表1，排樣過程如圖3所示，圖中1，2，3，4為矩形件編號．

假定本例中4個矩形件的排樣序列Q＝｛1，2，3，4｝，用改進的剩余矩形排樣算法排樣的步驟為

1）將矩形件1排放到板材的左下角，計算剩余矩形集合，此時形成了兩個剩余矩形區(qū)域，如圖3（a）所示．

2）排放矩形件2，先考慮將矩形件2排放到最低剩余矩形區(qū)域，發(fā)現(xiàn)不能插入，如圖3（b）所示；考慮將矩形件2轉(zhuǎn)動90°后再次插入，此時可以插入，插入后記錄已利用的板材的最大高度，如圖3（c）所示；然后將矩形件2不轉(zhuǎn)動，直接將矩形件2排放到下一個剩余矩形區(qū)域中，也就是排放在矩形件1的左上方，記錄此時已利用板材的最大高度，如圖3（d）所示，比較矩形件2兩次排樣后已利用板材的最大高度，選擇高度較小的一種排樣方案，同時重新計算剩余矩形集合．

表1 矩形件信息Tab．1 Rectangular parts information

圖2 轉(zhuǎn)動90°后使高度增大的情況Fig．2 Increasing height after rotating 90degrees

圖3 改進后剩余矩形排樣算法的排樣過程Fig．3 The layout process by the improved surplus rectangle algorithm

3）排放矩形件3，先考慮將其排放到最低矩形區(qū)域，發(fā)現(xiàn)可以插入排放，如圖3（e）所示，同時重新計算剩余矩形集合．

4）排放矩形件4，先考慮排放到最低剩余矩形區(qū)域，發(fā)現(xiàn)不能插入排放，如圖3（g）所示，將其轉(zhuǎn)動90°后，發(fā)現(xiàn)可以排放到最低剩余矩形區(qū)域，記錄此時已利用板材的最大高度，如圖3（h）所示；將矩形件不旋轉(zhuǎn)，直接排放到下一個可排放的剩余矩形區(qū)域，記錄此時已利用板材的最大高度，如圖3（i）所示；比較矩形件4兩次排樣后已利用板材的最大高度，選擇高度較小的一種排樣方案．此時，也得到了最終的排樣方案圖，如圖3（h）所示．

1．2 改進前后板材利用率對比

以文獻［4］中的25個矩形件數(shù)據(jù)信息為例，在長30mm高度足夠高的板材上排樣，隨機生成100組排樣序列，分別用剩余矩形排樣算法與改進后的剩余矩形排樣算法排樣，這兩種算法排樣的利用率如圖4～5所示．

圖4 剩余矩形排樣算法的利用率Fig．4 Utilization rate before improving

圖5 改進后后的剩余排樣算法的利用率Fig．5 Utilization rate after improving

用剩余矩形排樣算法排樣得到的板材最大利用率是0．909 1，平均利用率是0．832 4；改進后的剩余矩形排樣算法排樣后板材的最大利用率是0．952 4，平均利用率是0．854 1．由此可見，改進后的剩余矩形排樣算法能更有效的利用板材材料．

2 遺傳算法支持的剩余矩形件排樣優(yōu)化

剩余矩形排樣算法具有較強的局部優(yōu)化性能，而遺傳算法具有全局尋優(yōu)搜索的性能，將二者結合使用，能更加有效的解決矩形鈑金件的排樣優(yōu)化問題，以便尋求最優(yōu)的排樣方案．

2．1 編碼和解碼

編碼方式采用十進制順序編碼，將每一個矩形件順序編號，在編號的同時確定正負值，規(guī)定矩形件橫放時編號為正，豎放時編號為負．橫放表示矩形件的長邊與水平軸平行，豎放表示矩形件的短邊與垂直軸平行．對于一個染色體（3，-1，2，-4，5）來說，矩形件排樣順序是3，1，2，4，5，其中3號橫放，1號豎放，2號橫放，4號豎放，5號橫放．

對于矩形件的排樣問題，解碼就是將染色體轉(zhuǎn)化為排樣圖的過程，這里采用優(yōu)化后的剩余矩形排樣算法生成排樣圖．

2．2 選擇算子

在解決矩形件排樣優(yōu)化問題時，選擇算子采用輪盤賭選擇法，具體過程為

1）對種群中每個個體預排樣，求出每個個體的適應度值，再求出所有個體的適應度值總和．

2）求出每個個體的相對適應度（也就是被選中概率）Pi＝Fi／Fsum．其中Pi表示第i個個體被選中概率，F(xiàn)i表示第i個個體的適應度值，F(xiàn)sum表示所有個體的適應度值之和．

3）求出每個個體的的累積選擇概率qi．

4） 產(chǎn) 生 一 個 隨 機 數(shù) rand＝ ［0，1］．若rand＜q1，第一個個體被選中，否則第i個個體被選中，使qi-1＜rand＜qi成立．重復該操作，直到選擇的個體數(shù)等于初始種群的個體總數(shù)．

2．3 交叉算子

設定交叉操作算子的方法如下：在染色體上選擇一個位置作為交叉位置，交叉位置之前的基因片段不交叉，交叉位置之后的片段交叉．比較兩個參與交叉的染色體，將交叉位置之前的相同基因去除，將交叉位置之前的剩余基因順序不變的存入數(shù)組p［］和q［］中．然后對染色體的交叉部分進行交叉，若交叉部分的基因不等于這兩個數(shù)組中基因，則直接交換；若與數(shù)組中的基因相同，則先把相同基因換成數(shù)組p［］或q［］中對應基因之后再交換．

2．4 適應度函數(shù)

對于矩形件的排樣優(yōu)化問題，一般有兩種適應度函數(shù)，一種是用板材實際使用的最大高度的倒數(shù)表示；另一種是使用板材的利用率來確定適應度函數(shù)．對于定寬無限長的板材，本文設定遺傳算法的適應度函數(shù)為

式中：h為排樣圖的最大高度；w為板材的寬度；areal為所有矩形件的總面積．

3 矩形件排樣優(yōu)化實例及分析

為了測試遺傳算法支持的剩余矩形件排樣算法的有效性，對文獻［4］中的算例進行求解，進行實例驗證．在一塊高40mm、長15mm的矩形板材上，排列25塊尺寸已知的矩形件．按照本文提出的矩形件排樣問題的算法方案，設置初始種群為50個，遺傳代數(shù)為100代，優(yōu)化后得到的排樣結果如圖6所示．

圖6 優(yōu)化的排樣結果Fig．6 The optimized result of layout

排樣結果：板材利用率0．975 61，按照本文提出的排樣算法得到的排樣序列為P＝｛14，-6，7，-20，5，-15，10，1，25，24，8，-11，-3，-17，-22，-13，-18，2，21，9，19，4，23，-12，-16｝，而文獻［4］中的最優(yōu)排樣板材利用率為0．937 5．通過與文獻［4］中數(shù)據(jù)的比較，可見本文提出的矩形件排樣算法在提高板材利用率方面有一定的優(yōu)越性．

4 結 論

1）剩余矩形排樣算法在求解排樣問題時具有局部性，其在鈑金件排樣過程中板材利用率未達到全局最優(yōu)．對其進行改進，給出了改進剩余矩形排樣算法，該算法可使板材利用率提高．

2）通過遺傳算法與改進剩余矩形排樣算法相結合，給出了剩余矩形排樣遺傳優(yōu)化算法，獲得了排樣最優(yōu)解．該算法鈑金件排樣的板材利用率優(yōu)于剩余矩形排樣算法，排樣得以優(yōu)化．

［1］ YNAASEE H H，ZNIOBER A S．Two-Dimensional Cutting Stock with Multiple Stock Sizes［J］．Journal of the Operational Research Society，1991，42（8）：673．

［2］ DORI D，BEN B M．Efficient Nesting of Congruent Convex Figures［J］．Communications of the ACM，1984，27（3）：228．

［3］ DAGLI C H，POSHYANONDA P．New Approaches to Nesting Rectangular Patterns［J］．Journal of Intelligent Manufacturing，1997（8）：177．

［4］ 劉德全，滕弘飛．矩形件排樣問題的遺傳算法求解［J］．小型微型計算機系統(tǒng)，1998，19（12）：20．LIU De-quan，TENG Hong-fei．On Genetic Algorithm for the Orthogonal Packing of Rectantangles［J］．Mini-Micro System，1998，19（12）：20．（in Chinese）

［5］ 楊彩，史俊友，顧海明．基于遺傳模擬退火算法的矩形件排樣［J］．青島科技大學學報：自然科學版，2004，25（5）：452．YANG Cai，SHI Jun-you，GU Hai-ming．Packing of Rectangular Using Genetic Simulated Annealing Algorithm［J］．Journal of Qingdao University of Science and Technology：Nature Science Edition，2004，25（5）：452．（in Chinese）

［6］ 黃紅兵，蔣望東．二維不規(guī)則零件排樣問題的研究［J］．廣西科學院學報，2004，20（4）：225．HUANG Hong-bing，JIANG Wang-dong．On the Pattern Techniques of the Two-Dimensional Irregular Parts［J］．Journal of Guangxi Academy of Sciences，2004，20（4）：225．（in Chinese）

［7］ 張玉萍，張春麗，蔣壽偉．皮料優(yōu)化排樣的有效方法［J］．軟件學報，2005，16（2）：316．ZHANG Yu-ping，ZHANG Chun-li，JIANG Shou-wei．An Effective Approach for Leather Nesting［J］．Journal of Software，2005，16（2）：316．（in Chinese）

［8］ 賈志欣，殷國富，羅陽．二維不規(guī)則零件排樣問題的遺傳算法求解［J］．計算機輔助設計與圖形學學報，2002，14（5）：467．JIA Zhi-xin，YIN Guo-fu，LUO Yang．Two-Dimensional Irregular Parts Packing with Genetic Algorithm［J］．Journal of Computer-Aided Design ＆ Computer Graphics，2002，14（5）：467．（in Chinese）