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

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

2、法可以求得滿足/ 一刀切0 約束的最優(yōu)解.: 遺傳算法; 矩形件排樣; 組合優(yōu)化號: T P301 文獻(xiàn)標(biāo)識碼: 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矩形件排樣是指在給定的矩形板材上, 排了排樣的約束條件, 而且切割時(shí)會(huì)產(chǎn)生一定的切縫寬度. 這些都會(huì)對排樣結(jié)果產(chǎn)生影響. 文中將矩形匹配分割算法的局部搜索和遺傳算法的全局搜索合, 提出了一種滿足/ 一刀切0工藝要求的矩形件排放多規(guī)格多數(shù)量的矩形件時(shí), 如何排放可以使板材的利用率最大. 這是一個(gè)典型

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

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

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

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

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

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

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

13、 / 00表示按原方向排放 / 10表示旋轉(zhuǎn) 90b圖 1 / 一刀切0 示例Fig . 1 Example o f quir e cutting 50 #智 能 系統(tǒng) 學(xué) 報(bào)第 2 卷后排放.上述取 P2 交叉點(diǎn)開始的順序?yàn)?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 塊板材. 對于每個(gè)所表示的排樣方案由矩形匹配分割算法具體確定. 也就是說, 在遺傳算法中通過調(diào)用矩形匹配分割算O1 : ( 1

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

15、, 方向交叉只對第 2 層的字符進(jìn)行操作.材部分的字符全設(shè)為 0, 并將矩形匹配分割算法中的分割方向設(shè)為豎切, 就可以實(shí)現(xiàn)矩形件在卷材上交叉如下:設(shè)父代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 層形式的編碼就可以具,有比較廣泛的適用性, 為算法既可以應(yīng)用于套排, 也可應(yīng)用于單排提供了方便.1. 3. 2 適應(yīng)度函數(shù)已有文獻(xiàn)中用一個(gè)排樣方案的板材利用率即板材上排放的矩形件的面積與板材面積之比的大小衡.交叉后的子代O1 的第 1 層為 P1 的

16、第 1層, 第 2 層為 P 1 的第 1 層字符在 P2 中所對應(yīng)的第量一個(gè)的優(yōu)劣, 余料面積相同而形狀不2 層的 0, 1 值.O2 的第 1 層為 P2 的第 1 層,同, 其可利用性是不同的, 利用率應(yīng)當(dāng)包含余料面積的大小和形狀 2 個(gè)要素. 因此, 在適應(yīng)度函數(shù)中采用第 2 層為 P2 的第1 層字符在 P1 中所對應(yīng)的第2 層的 0, 1 值. 這樣, 得到子1 2 3, 1 3 5 2 4 6 7如下:了一個(gè)余料的長寬比例系數(shù) B( 0<相等時(shí), B最大.1. 3. 3 交 叉B1) , 當(dāng)長和寬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 :.由于矩形件的排放順序和排放方向均產(chǎn)生不同的排樣結(jié)果, 因此, 設(shè)計(jì)了順序交叉和方向交叉1. 3. 4變 異由于板材橫切或豎切的改變都將改變剩余矩形的形狀, 從而使以后的排放方式發(fā)生變化. 因此, 變的交叉算子. 在執(zhí)行每次交叉操作時(shí), 隨機(jī)確定是順序交叉還是方向交叉.1) 順序交叉異操作只對的第 2 層實(shí)施變異操作. 根據(jù)變順序交叉只在的第 1 層進(jìn)行. 在異概率在種群中隨機(jī)選擇出和的長度范圍內(nèi)隨機(jī)產(chǎn)生一個(gè)交叉點(diǎn), 這個(gè)點(diǎn)可能在板材部分也可能在矩形件部分. 如果在板材部分就只對板材順序?qū)嵤┙徊? 而矩形件部分保持不變. 如果在矩形件

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

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

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

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

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

23、90 m m 和10 mm , 空白部分的最大切割矩形 52 #智 能 系統(tǒng) 學(xué) 報(bào)第 2 卷的矩形件, 其數(shù)量及的數(shù)據(jù)如表 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. 運(yùn)行算法得到的排樣結(jié)果如圖 5 所示, 卷材的使用長度為 1 150 m m,

24、 小于文獻(xiàn) 4 的卷材長度 1 245 mm.表 2 矩形件數(shù)據(jù) 2 2 楊 威, 羅 陽,傳算法 J .59 62. 大規(guī)模矩形零件優(yōu)化套排的遺大學(xué)學(xué)報(bào)( 工程科學(xué)版) , 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.編號數(shù)量長/ mm寬/ mm5840784020. 基于改進(jìn)遺傳算法的矩形件優(yōu)化排樣 3, J . 計(jì)算機(jī)工程與應(yīng)用, 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 . 基于遺傳模擬退火算法的矩形,青島科技大學(xué)學(xué)報(bào), 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., 劉 軍, 李 兵, 等. 一個(gè)實(shí)用的矩形件優(yōu)化排樣啟發(fā)式算法 J . 工程圖學(xué)學(xué)報(bào), 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