基于遺傳算法的二維滑窗排樣算法

1、基于遺傳算法的二維滑窗排樣算法張?jiān)娊?閆佳男 劉明珠 趙子越摘要 ：根據(jù)板材的整體情況，將板材抽象為框架，用點(diǎn)云形式表示，模擬板材之間、板材與邊界的碰撞與約束，以滑窗的形式插入新的板材。并以遺傳算法求解最佳插入方案。關(guān)鍵詞：二維排樣 遺傳算法 滑窗算法概述二維不規(guī)則零件的排樣問題就是將一系列形狀各異的零件排放在給定的板材上，按最優(yōu)方式找出零件的最優(yōu)排布。要求零件排放在板材內(nèi)，各個(gè)零件互不重疊，并滿足一定的工藝要求，使得給定板材的利用率最高，以達(dá)到節(jié)約材料，提高效益的目的。二維排樣技術(shù)廣泛應(yīng)用于鈑金加工、輕工、服裝和印刷業(yè)排版等行業(yè)中。對(duì)于材料利用率的提高可帶來顯著的經(jīng)濟(jì)效益，因此，研究零件在板

2、材上的最優(yōu)布局具有重要的現(xiàn)實(shí)意義。傳統(tǒng)二維排樣算法通過不停排除最小包圍矩形來計(jì)算剩余空間的多少，常要求被分割的原材料為矩形。對(duì)于不規(guī)則形狀的原材料難以下手。本文提出了一種通過點(diǎn)云來模擬空間的排布，來對(duì)不規(guī)則板材下的不同尺寸的矩形毛料進(jìn)行排布，并通過遺傳算法進(jìn)行優(yōu)化的算法，獲得了較好的效果。1. 算法流程遺傳算法的基因定位毛料的型號(hào)與擺放的方向。適應(yīng)度函數(shù)為收益最大。其中，收益的計(jì)算來自于不同尺寸的每塊毛料可以獲得的收益之和。算法思路為：Step 1:隨機(jī)生成初始種群基因。該基因記載了按照順序碼放的毛料型號(hào)及橫放或縱放Step 2：載入墻體圖片，其中黑色（0）代表無法安放毛料的位置，白色（255

3、）代表可以安放毛料的位置。Step 3：遍歷全部基因，按照基因記載的碼放方式依次碼放毛料。碼放時(shí)，以毛料為為模板進(jìn)行匹配（搜索窗），從左至右，從上至下滑動(dòng)窗口，直至搜索窗內(nèi)的像素全部為白色（255），將對(duì)應(yīng)毛料碼放至此（將搜索窗內(nèi)像素填充為黑色）。Step 4：計(jì)算全部基因碼放毛料后，所產(chǎn)生的總利潤(rùn)，作為該基因的適應(yīng)度。若某基因適應(yīng)度為當(dāng)前最優(yōu)，則記錄。Step 5：依據(jù)各基因適應(yīng)度大小占全部基因適應(yīng)度和的比例，計(jì)算對(duì)應(yīng)基因被復(fù)制的概率，并依該概率進(jìn)行復(fù)制。Step 6：根據(jù)交配概率選出交配的基因組，進(jìn)行交配，并依據(jù)突變概率進(jìn)行突變。Step 7：轉(zhuǎn)至Step 3，循環(huán)流程。直至達(dá)到規(guī)定次數(shù)，

4、結(jié)束循環(huán)并輸出當(dāng)前最優(yōu)方案。并且，實(shí)際編程中，由于上述流程計(jì)算量過大，運(yùn)行時(shí)間過長(zhǎng)，因此將原比例按照10毫米=1像素進(jìn)行縮放，并且毛料以僅有外框和少量橫豎軸線的骨架圖代替實(shí)心色塊進(jìn)行匹配。優(yōu)化后，程序的運(yùn)行速度得到了大幅的提高，使得遺傳算法的運(yùn)行時(shí)間達(dá)到許可范圍。編程實(shí)現(xiàn)2. 實(shí)驗(yàn)結(jié)果在core i5 cpu，2.53GHz，內(nèi)存2GB的計(jì)算機(jī)上，程序運(yùn)行時(shí)間約為300秒。驗(yàn)證數(shù)據(jù)使用了太陽(yáng)能小屋設(shè)計(jì)中光伏電池的最優(yōu)鋪設(shè)問題9的數(shù)據(jù)。該問題是一對(duì)墻體的太陽(yáng)能電池板鋪設(shè)問題，其中的墻體多為不規(guī)則圖形，是本算法的一種較好的應(yīng)用場(chǎng)景。毛料的尺寸數(shù)據(jù)：表 1 毛料數(shù)據(jù)表毛料編號(hào)數(shù)據(jù)寬高利潤(rùn)C(jī)21321

5、711265C7615180157C10818355178圖 1 板材1圖 2板材22.1. 驗(yàn)證結(jié)果圖 3板材1拍樣圖 4 板材2拍樣由Error! Reference source not found.、Error! Reference source not found.可見，基于遺傳算法的二維滑窗拍樣對(duì)于特異板材的分割有良好的適應(yīng)性，可以獲得一個(gè)較好的拍樣方案。2.2. 比較為了便于比較，使用了如Error! Reference source not found.所示的板材和毛料。該板材大小為10100×8570 cm2，毛料大小為1482×992 cm2。根據(jù)人工計(jì)

6、算，若橫放可以碼放6×8=48塊，縱放可以碼放10×5=50塊。根據(jù)直觀感受，這一板材難有更佳分割方式。然而本文的利用基于遺傳算法的二維滑窗拍樣卻可以在該板材上碼放51塊毛料。（Error! Reference source not found.所示）。這一結(jié)果充分證明了該拍樣方法是有效的具有實(shí)際意義的拍樣算法。圖 5算法拍樣3. 結(jié)論基于遺傳算法的二維滑窗排樣結(jié)合了傳統(tǒng)矩形優(yōu)化排樣算法和圖像匹配算法的優(yōu)點(diǎn)，可以有效的應(yīng)對(duì)各種不規(guī)則情況下的排樣問題，對(duì)空間利用率較高。且由于遺傳算法的特性，該模型有希望得到全局最優(yōu)解。模型采用了骨架化模板匹配對(duì)算法效率進(jìn)行了優(yōu)化，大幅提升了算

7、法的運(yùn)行效率。對(duì)比人工比較，可以達(dá)到更優(yōu)的結(jié)果。但是，由于滑窗匹配算法時(shí)間復(fù)雜度高的基本特性和遺傳算法大運(yùn)算量的特征，程序運(yùn)行效率依然較低，限制了遺傳算法的迭代次數(shù)和種群容量。且由于點(diǎn)云的性質(zhì)本身，數(shù)據(jù)的精度和運(yùn)算的速度無法同時(shí)保證。這是本算法還待改進(jìn)的地方。參考文獻(xiàn)1.韓喜君, 丁根宏. 矩形件優(yōu)化排樣問題的混合遺傳算法求解J. 計(jì)算機(jī)技術(shù)與發(fā)展, 2006, 16(6): 219-221.2.王曉慶. 基于層排樣方式的矩形毛坯下料算法D. 廣西師范大學(xué), 2011.3.郭俐, 崔耀東. 有約束單一尺寸矩形毛坯最優(yōu)排樣的拼合算法J. 農(nóng)業(yè)機(jī)械學(xué)報(bào), 2007, 38(10): 140-144.4.曹炬, 周濟(jì). 矩形件排樣優(yōu)化的背包算法J. 中國(guó)機(jī)械工程, 1994, 5(2): 11-12.5.黃紅兵, 蔣望東. 二維不規(guī)則零件排樣問題的研究J. 廣西科學(xué)院學(xué)報(bào), 2004, 20(4): 225-227.6.李明, 宋成芳, 周澤魁. 一種二維不規(guī)則零件優(yōu)化排樣算法J. 四川大學(xué)學(xué)報(bào) (工程科學(xué)版), 2005.7.史俊友, 馮美貴. 二維不規(guī)則件優(yōu)化排樣的小生境遺傳算法J. 工程 設(shè)計(jì)學(xué)報(bào), 2007, 14(2).8.張小鋒, 童華, 黃