基于遺傳算法的大規(guī)模矩形件優(yōu)化排樣

1、V ol. 2 l . 5 Oct. 2007第 2 卷第 5 期2007 年 10 月智 能 系 統(tǒng) 學 報CAAI T ransactions on Intelligent Systems基于遺傳算法的大規(guī)模矩形件優(yōu)化排樣馬炫, 張亞龍( 西安理工大學 自動化與信息, 陜西 西安 710048)摘 要: 大規(guī)模矩形件優(yōu)化排樣是一個典型的組合優(yōu)化, 屬于 NP hard. 實際工對一個排樣方案一般有滿足/ 一刀切0 的工藝要求,/ 一刀切0要求增加了對排樣的約束. 提出的優(yōu)化算法, 將矩形匹配分割算法作為遺傳算法的器實現一個排樣方案, 用遺傳算法進行排樣方案的全局搜索. 算例比較表明, 該算

2、法可以求得滿足/ 一刀切0 約束的最優(yōu)解.: 遺傳算法; 矩形件排樣; 組合優(yōu)化號: T P301 文獻標識碼: A文章編號: 1673 4785( 2007) 05 0048 05A genetic algorithm for the layout of large scale rectangular partsM A Xuan, ZHANG Ya long( Schoo l o f Automat ion and Information Engineering , X ci an U niversity o f T echnolog y, Xci an 710048,Abstract: T

3、 he o ptimal layout of larg e scale rectang ular parts is a com binato rial o ptimization problem, a typ-ical N P- hard one. In practical engineering, quire cutting is often requested, w hich increases the constraints in the determination of a layout. To satisfy quire cutting requir em ents, in this

4、 paper, an optim ization algo- r ithm is proposed w herein a rectangular matching and seg mentation algo rithm is em plo yed as a decoder of chrom oso mes in a genetic algorithm to determ ine placem ent. A global optim al solutio n for placem ent can be achieved w ith this genetic algor ithm. Simula

5、tion r esults confirmed the validity o f the proposed algo-r ithm.Keywords: g enetic algo rithm; rectangular parts lay out;co mbinatorial optimizatio n矩形件排樣是指在給定的矩形板材上, 排了排樣的約束條件, 而且切割時會產生一定的切縫寬度. 這些都會對排樣結果產生影響. 文中將矩形匹配分割算法的局部搜索和遺傳算法的全局搜索合, 提出了一種滿足/ 一刀切0工藝要求的矩形件排放多規(guī)格多數量的矩形件時, 如何排放可以使板材的利用率最大. 這是一個典型

6、的組合優(yōu)化, 在工業(yè)領域如沖裁件排樣、造船、車輛、家具生產切割等行業(yè)都大量的排樣. 求解最優(yōu)排樣方樣優(yōu)化算法. 設計的編碼和具有方向交叉的交案是一個N P- hard, 至今尚未找到多項式時間叉算子了遺傳算法的搜索性能. 通過算例比較,算法. 因此, 對于大規(guī)模排樣, 在可接受的時間表明了算法的有效性.1矩形件排樣優(yōu)化算法1. 1排樣優(yōu)化矩形件在矩形板材上的排樣內快速找到次優(yōu)解的算法引起了人們的關注. 很多學者在這方面做了卓有成效的研究工作. 文獻 1-3 分別提出了排樣的遺傳算法; 文獻 4 提出了將遺傳算法和模擬退火算法結合的遺傳模擬退火算法; 文獻 5 提出了啟發(fā)式排樣算法等等. 在實際

7、工, 對一個排樣方案中的矩形件進行切割時, 經常, 可以分為 2類: 一類是在單一板材上排樣, 稱為單排, 其中卷材, 卷材可以看成在寬度方向有約束而在長度方向沒有約束的矩形板材; 還有一類是在多塊矩形板材上的排樣, 稱為套排. 顯然, 套排比單排更加復雜.會提出滿足/ 一刀切0的下料工藝要求, 如切割、厚型金屬板材切割等. / 一刀切0的要求實際上增加這里主要研究套排, 排樣優(yōu)化可以描述成收稿日期 20068 49 #第 5 期馬 炫, 等: 基于遺傳算法的大規(guī)模矩形件優(yōu)化排樣切0要求.綜上所述, 按準/ 一刀切0的要求排樣, 可以最大限度地提高板材的利用率. 因此, 算法設計主要考慮在給定

8、多塊矩形板材上如何排放多個矩形件, 即把每個矩形件排放在哪塊板材上, 排在板材的什么位置, 是橫排還是豎排等, 確定一個可以使板材的利用率達到最大的排樣方案. 其數學表示如下:設有一個矩形件集合 Bi , i = 1, 2, , n, 其面積集合為 bi ; 一個板材集合 A j , j = 1, 2, , m, 其滿足準/ 一刀切0的排樣優(yōu)化1. 3遺傳算法遺傳算法作為一種全局數值優(yōu)化., 被廣泛應用于組合優(yōu)化, 對大規(guī)模矩形件排樣優(yōu)化問面積集合為 aj ; 排料優(yōu)化就是尋找一個板材題也顯示出了明顯的優(yōu)勢 1- 3 .矩形件在板材左下角的排法及板材的切法可以有 4 種, 如圖 2 所示. 圖

9、中的虛線表示切割方向, 圖2( a) 為橫排豎切, 圖 2( b) 為橫排橫切, 圖 2( c) 為豎排豎切, 圖 2( d) 為豎排橫切. 顯然, 在解決優(yōu)化排樣中, 矩形件的排法和板材的切法直接影響到優(yōu)化結果. 因此, 把板材和矩形件的編號序列和方向作集合 Ac , j =1, 2, , k, k m, 其面積集合為 ac ,fj及其上的矩形件的放置布局, 使以下目標函數達到最大值:nkE bi / E acjF = max,( 1)i 1j 1knE biE acj .( 2)i 1在布局中要求:j 1為中的信息, 用矩形匹配分割算法實現一個所表示的排樣方案, 進行局部搜索; 再用遺傳,

10、 n, i X j ;1) Bi 、Bj 互不重疊, i , j = 1, 2,2) Bi 必須位于板材內i = 1, 2, , n;3) 滿足一定的工藝要求.1. 2 / 一刀切0約束/ 一刀切0是指在切割一個排樣方案中的矩形件時, 沿矩形件邊的切割線可以將板材分割成 2 部分, 稱切割線是貫通的. 排樣方案中的/ 一刀切0 約束有以下 2 種情況:1) 完全/ 一刀切0. 在排樣方案中, 沿任一矩形件邊的切割線都是貫通的, 這種情況如圖 1( a) 所示. 將矩形件在板材上連續(xù)橫排或連續(xù)縱排 6 , 容易實現/ 一刀切0且切割效率最高, 但排樣結果不一定是最優(yōu)的, 特別是在多規(guī)格且同一種規(guī)

11、格的矩形件數量比較少的情況下, 完全/ 一刀切0使板材的利用率不夠高.2) 準/ 一刀切0. 在排樣方案中至少有一條切割線是貫通的, 切割后形成的 2 塊板材也分別至少有算子實現全局搜索, 是算法設計的主要思想.圖 2 矩形件排放與切法F ig . 2 Placement and cutting o f a par t1. 3. 1編 碼編碼就是用字符串形式表示空間的一個可一條切割線是貫通的, 以以將板材上的全部行解, 稱之為. 一個應該表示出空矩形件以貫通方式切割, 如圖 1( b) 、( c) 所示. 圖 1 ( c) 中, 先沿 a 線切割后, 再沿 b 線即可/ 一刀切0, 然后再分別

12、沿 c 線和 d 線切割. 這樣就可以切割出所有矩形件. 因此, 認為這樣的排樣方案也滿足/ 一刀間的有關信息. 文獻 2 的編碼沒有反映出矩形件排放的方向信息, 僅由矩形匹配算法確定方向, 影響了遺傳算法的全局搜索性能. 對于排樣, 一個表示的一個排放方案, 既要表明哪個矩形件排入哪塊板材, 又要表明矩形件是橫排還是豎排. 為此, 設計一個具有 2 層形式的編碼:13 621 3,01 0,5 240 1100 0第 1 層的字符代表順序, / , 0之前的字符表示板材順序( 例中表示有 3 塊板材) , / , 0之后的字符表示矩形件的排放順序. 第 2 層的字符表示板材和矩形件的放置方向

13、 / 00表示按原方向排放 / 10表示旋轉 90b圖 1 / 一刀切0 示例Fig . 1 Example o f quir e cutting 50 #智 能 系統(tǒng) 學 報第 2 卷后排放.上述取 P2 交叉點開始的順序為 1、6、7、5、2、3、的排樣方案可能是第 5、2、4 號矩形4, 消除中已有的 1、3、5, 得到 6、7、2、4, 按此順序決定 x , O1 變?yōu)榧湃氲?2 塊板材, 第 1、3 號矩形件排入第 1 塊板材, 第 6 號矩形件排入第 3 塊板材. 對于每個所表示的排樣方案由矩形匹配分割算法具體確定. 也就是說, 在遺傳算法中通過調用矩形匹配分割算O1 : ( 1

14、 2 3, 1 3 5同理可得:O2 : ( 1 3 2, 2 3 42) 方向交叉6 7 2 4) .6 7 1 5) .法實現每個所表示的排樣方案. 比如, 對于上如果板材先旋轉 90b, 根據矩形匹配分割算法中始終采用沿矩形件的豎邊切割的規(guī)定, 實際上是對板材實現了沿矩形件的橫向切割. 同樣, 矩形件放入板材時旋轉 90b可以調整矩形件的橫排和豎排.述, 先選 2 號板材將矩形件排樣, 2 號板材排滿后再將剩余的矩形件在 1 號板材上排樣, 1 號板材排滿后再選 3 號板材對其余的矩形件排樣.如果只在一塊板材上排樣, 可將板材部分的字符全部設置為 0. 對于卷材, 可將中第 2 層板因此

15、, 方向交叉只對第 2 層的字符進行操作.材部分的字符全設為 0, 并將矩形匹配分割算法中的分割方向設為豎切, 就可以實現矩形件在卷材上交叉如下:設父代1 2 3,P1 :0 1 0,1 3 2,P2 :1 1 0,為1 3 5 2 4 6 70 1 1 0 1 0 02 3 4 1 6 7 51 0 0 1 0 0 1的排樣. 這樣, 上述 2 層形式的編碼就可以具,有比較廣泛的適用性, 為算法既可以應用于套排, 也可應用于單排提供了方便.1. 3. 2 適應度函數已有文獻中用一個排樣方案的板材利用率即板材上排放的矩形件的面積與板材面積之比的大小衡.交叉后的子代O1 的第 1 層為 P1 的

16、第 1層, 第 2 層為 P 1 的第 1 層字符在 P2 中所對應的第量一個的優(yōu)劣, 余料面積相同而形狀不2 層的 0, 1 值.O2 的第 1 層為 P2 的第 1 層,同, 其可利用性是不同的, 利用率應當包含余料面積的大小和形狀 2 個要素. 因此, 在適應度函數中采用第 2 層為 P2 的第1 層字符在 P1 中所對應的第2 層的 0, 1 值. 這樣, 得到子1 2 3, 1 3 5 2 4 6 7如下:了一個余料的長寬比例系數 B( 0<相等時, B最大.1. 3. 3 交 叉B1) , 當長和寬O1 :,1 0 1, 1 0 1 1 0 0 01 3 2, 2 3 4 1

17、 6 7 50 0 1, 0 1 1 0 0 0 1O2 :.由于矩形件的排放順序和排放方向均產生不同的排樣結果, 因此, 設計了順序交叉和方向交叉1. 3. 4變 異由于板材橫切或豎切的改變都將改變剩余矩形的形狀, 從而使以后的排放方式發(fā)生變化. 因此, 變的交叉算子. 在執(zhí)行每次交叉操作時, 隨機確定是順序交叉還是方向交叉.1) 順序交叉異操作只對的第 2 層實施變異操作. 根據變順序交叉只在的第 1 層進行. 在異概率在種群中隨機選擇出和的長度范圍內隨機產生一個交叉點, 這個點可能在板材部分也可能在矩形件部分. 如果在板材部分就只對板材順序實施交叉, 而矩形件部分保持不變. 如果在矩形件

18、部分就只對矩形件部分實施交叉, 而板材部分保持不變. 進行交叉操作時是保留交叉點前部位, 對該位的值反轉變異, 即若為 0, 則變?yōu)?1,若為 1, 則變?yōu)?0. 由于變異操作, 板材或矩形件的方向發(fā)生了變化, 這樣就需要對于變異點以后的剩余矩形和矩形件重新調用矩形匹配分割算法.1. 4矩形匹配分割算法為了實現/ 一刀切0, 在剩余矩形匹配算法 7 的基礎上提出了矩形匹配分割算法, 按照先進行矩形匹配后進行板材分割的原則進行. 即首先在矩形件中搜索與板材的一個邊匹配程度最近的一個矩形件放入板材的左下角, 然后再把板材分成 2 部分. 由于板材和矩形件都可旋轉, 因此, 這里規(guī)定板材的切割方向為

19、豎切. 算法主要步驟如下:1) 讀入板材的長 L 和寬 W , 所有矩形件的長 l還是后部, 每次也隨機確定. 交叉如下: 設 2 個父代的第 1 層為P1 : ( 1 2 3, 1 3 52 4 6 7) ,P2 : ( 1 3 2, 2 3 41 6 7 5) ./ 0為交叉位置, 即對矩形件部分進行交叉. 若保留交叉點前部分, 得到: ) , ) .O1 : ( 1 2 3, 1 3 5O2 : ( 1 3 2, 2 3 4 51 #第 5 期馬 炫, 等: 基于遺傳算法的大規(guī)模矩形件優(yōu)化排樣和寬w , 切縫寬度 d, 并將所有板材和矩形件的長和寬分別增加一個切縫寬度 d;2)矩形件是否

20、已排完, 若是, 結束返回;的為 300 mm 和 130 m m. 從圖中可以看出, 排樣方案滿足/ 一刀切0要求, 如圖 4( a) 所示, 先沿 a 切割, 再分別沿 b、c、d 切割. 與圖 3 比較, 由于圖 4 所示排樣方案中, 余料( 空白部分) 的可再利用性比較好, 可以說優(yōu)于文獻 6 的排樣方案.3) 在一個排樣順序(的字符順序) 中按順序尋找與板材的邊長最匹配的矩形排入板材的左下角, 修改 L 或 W ;4) 沿排入矩形件的豎邊把板材分為 2 個子矩形;5) 讀入第 1 個子矩形的長和寬, 將第 2 個子矩形入棧保存, 修改矩形參數 L 和 W , 返回 2) .6) 第

21、2 個子矩形出棧, 讀入參數 L 和 W, 返回2).算法中規(guī)定的板材分割和對算法的調用證了一個排樣方案能夠實現/ 一刀切0.如果只將矩形件的邊外延半個切縫寬度來滿足切縫寬度要求, 將會使矩形件的各邊在下料時都需要切割. 在上述算法的 1) 中將板材的長和寬也分別擴大一個切縫寬度, 排樣結果中與板材同邊的矩形件的可以不需要切割. 這樣處理, 不但可以減少切割次數, 而且還可以提高板材的利用率.2計算實例遺傳算法的參數中, 取種群規(guī)模 100, 交叉率0. 8, 變異率 0. 06. 以進化代數作為終止條件, 取為300.2. 1算例 1采用文獻 6 算例 2 中的數據, 即板材長為600 mm

22、, 寬為 400 mm, 規(guī)格相同, 矩形件共有10 種規(guī)格, 其數量和 見表 1 所示.表 1 矩形件數據 1Table 1Data 1 of the rectangular objects編號數量長/ mm寬/ mm131307067892331300120350310708090130 103130110運行算法得到的排樣結果如圖 4 所示. 排樣方案共使用了 2 塊板材, 第 1 塊中的陰影部分和第 2塊中的陰影部分及右上角的空白部分為余料. 陰影2. 2算例 2采用文獻 4 算例中的數據, 即共有 10 種規(guī)格部分的分別為 80 mm 和 10 m m 、90 m m 和10 mm、

23、90 m m 和10 mm , 空白部分的最大切割矩形 52 #智 能 系統(tǒng) 學 報第 2 卷的矩形件, 其數量及的數據如表 2 所示. 在卷材CA O Ju, F EN G Song . T he applicatio n of g enet ic a lg or ithm in rectangula r object optimal layo ut J . Co mputer Eng ineer ing and Application, 1999, 5( 2) : 5 7.上排樣, 卷材寬度為 600 m m. 運行算法得到的排樣結果如圖 5 所示, 卷材的使用長度為 1 150 m m,

24、 小于文獻 4 的卷材長度 1 245 mm.表 2 矩形件數據 2 2 楊 威, 羅 陽,傳算法 J .59 62. 大規(guī)模矩形零件優(yōu)化套排的遺大學學報( 工程科學版) , 2001, 33( 5) :Table 2Data 2 of the rectangular objectsY A N G W ei, L U O Yang , L IU Sheng qing . G enetic a lg o r ithm for lar ge sca le rectangular object optimal embed placement J . Jour nal o f Sichuan U ni

25、ver sity ( Eng ineering science edition) , 2001, 33( 5) : 59 62.編號數量長/ mm寬/ mm5840784020. 基于改進遺傳算法的矩形件優(yōu)化排樣 3, J . 計算機工程與應用, 2006, 42( 25) : 63 65.H A N Xijun, D ING Genho ng . T he o pt imum packing of r ectang les based o n impr ov ed g enetic algo rithm J . Com puter Eng ineer ing and A pplicatio

26、n, 2006, 42 ( 25) :63 65.16959643550502540234496680356080154040 4 楊 彩,件排樣 J . 基于遺傳模擬退火算法的矩形,青島科技大學學報, 2004, 25( 5) : 452 456.Y A N G Cai, SH I Juny ou, G U H aiming. P acking of rec tangular using g enetic simulated annea ling alg or ithm J . Jour nal of Q ingdao U niver sity o f Science and T echnolo g y, 2004, 25( 5) : 452 456., 劉 軍, 李 兵, 等. 一個實用的矩形件優(yōu)化排樣啟發(fā)式算法 J . 工程圖學學報, 2003, 24( 4) : 50 58. 5L U O Yiping , L IU Jun, LI Bing ,. A pr actica l heu圖 5卷材上的排樣方案r istic algo rithm for r ect ang le par ts packing pr oblem J .Jour