主要研究矩形零件的排樣方法，遺傳算法的用途在此處體現的淋漓盡致
本文算子的選擇是有效的 為進一步驗證算法,對零件數量從16~97的不 同算例進行試驗,每類有3個例子,其最優排放圖 均已知,各個算例的基本試驗數據(零件數量,板材尺 寸)和本文試驗最好結果見表2, 表2算例2的基本試驗數據及本文試驗結果 Tab 2 Dimension of second example and best result given by this paper 問題 零件最優高度原最優板材所得最低高度 ()SA+文算法結果(b)SA+最低水平線算法結果 種類 數量 mm 尺寸/mm mm 20 20×20 20 圖1算例1的排放圖 40×15 Fig 1 Layout of first example 28 60×30 32 表1本文算法與最低水平線算法排樣結果對比 C4 49 60 60×60 64 Tab. 1 Difference between our algorithm and 73 60×90 the lowest outline algorithm 97 120 80×120 129 最小高度最小高度最大高度平均高度運行時間 圖2給出了部分算例的最好排放結果。 Hopper 算法 /mm出現頻次/mm/mm/ms 8. Turton對以上規模不同的矩形件采用BL、BLF SA+最低水平線48 1/50 53.7 16 算法進行排放,允許零件旋轉90°,GA、NE、SA、HC SA+本文方法48 3/50 5 I 48.6 等算法搜索排放順序。文中指出采用BLF排放效果 優于BL算法10%~30%,采用SA+BLF算法所得 4.2算例2 結果最優,見表3。 (a)C11 (b)C41 (c)C61 圖2算例2采用本文算法所得的排放圖 ig 2 Best layout of second example with our algorithm 表3各類別實例的相對距離百分比1 表4各實例運行時間對比表 Tab3 Relative distance of best solution to Tab 4 Average elapsed time for optimum height for six cases % six cases with different algorithm 問題種類 BI BLF SA+BLF本文算法 問題 A+BLF SA+本文算法 17 4 種類 ms 16 2.8 24 12 6.7 C4 18 16 132 120 C6 5 7.5 注:1)表中值表示所得最好結果U與最優值lO)pt差值的白分比 C6 1528 1894 47 (U-Op:)/lOpt。 宇航材料工藝2007年第4期 17 對比表2、表3知,本文算法和文獻[6]中采用 圖3表明:矩形排放耗時10ms,經人機交互調 BLF解碼的綜合算法結果相近,并且在零件數量較整后材料利用率為86.4%,比人工排樣提高約11 少(如n=16)時能獲得最優解,與埋論分析一致;由8%。 表4知,本文算法的運行時間大大少于BLF算法,這5結論 是因為在排放R;時只需搜索當前輪廓線段,比BLF 實際算例表明最低輪廓線搜索算法能有效地進 算法(搜索所有空域區域)搜索空間減少,因此效率明行矩形件排放,與模擬退火算法相結合,能在較短時 顯提高。由于文獻[6的運行環境是:處理器奔騰間內獲得與BLF算法相近的排放結果,并且在零件 200MHκ,RAM65M, Windows nt4.0;而本文運行數量較少時能獲得最優解,是解決大規模矩形件排放 環境為:CPU2.8GHz,RAM512M,其速度大約是問題的有效方法 200MHz處理器的15倍,因此表4所給BLF混合算 參考文獻 法的運行時間做了相應處理?？梢姴捎幂喞阉鞣?1張麗萍,張春麗,蔣壽偉.皮料優化排樣的有效方法 與BLF算法可獲得相近的排放效果,但前者效率明軟件學報,2005;16(2):316~323 顯高于后者。文獻[7采用啟發式遞歸(HR)算法對 2曹炬,周濟,余俊.矩形件排樣優化的背包算法.中國 以上算例進行求解,大大提高了運行效率,但在零件機械工程,1994;5(2):11~12 數量較多時其速度也明顯低于本文算法。因此最低 3曹炬.二維異形切割件優化排樣的擬合算法.中國機 輪廓搜索法可用于求解大規模矩形件的排樣問題。 械工程,2000;11(4):438~441 4.3應用舉例 1 Jakobs S On genetic algorithms for the packing of 針對不規則復合材料鋪層,采用矩形包絡法求出 polygons,Eur. of oper,Res.,1996881):165-181 其包絡矩形,然后采用上述算法進行排放。圖3是飛 5賈志欣.面向發電設備制造的下料優化排樣原理與關 機坐艙罩頂棚的鋪層展開數據采用以上策略獲得的鍵技術,四川大學博士學位論文,2002 排放圖。 6 Hopper E, Turton B C H. An empirical investigation of meta-heuristic and heuristic algorithms for a 2D packing problem. EurJ of Oper Res, 2001; 128(1): 3457 7 Zhang Defu, Kang Yan, Deng Ansheng. A new heuristic recursive algorithm for the strip rectangular packing problem Computers &. Operations Research, 2006; 33(8): 2209-2 217 圖3復合材料鋪層排放實例 (編輯李洪泉) ig. 3 Layout for composites plys 18 宇航材料工藝2007年第4期 矩形件優化排樣的研究 舊 萬數據 WANFANG DATA文獻鏈接 作者: 鄧冬梅,厝米水,安魯陵,王桂賓, Deng Dongmei, Zhou laishui, An Luling, Wang guibin 作者單位: 南京航空航天大學機電學院,南京,210016 刊名 宇航材料工藝sTc|PKU 英文刊名: AEROSPACe mATERIALS technology 年,卷(期): 2007,37(4) 被引用次數 4次 慘考文獻(條) 1.張麗萍.張春麗.蔣壽偉皮料優化排樣的有效方法[期刊論文]軟件學報2005(02) 2.曹炬.周濟.余俊矩形件排樣優化的背包算法[期刊論文]中國機械工程1994(02) 3.曹炬二維異形切割件優化排樣的擬合算法「期刊論文]中國機械工程2000(04 4.Jakobs S On geretic algorithms for the packing of polygons 1996 (0 5.賈志欣面向發電設備制造的下料優化排樣原理與關鍵技術[學位論文]2002 6. Hopper E Turton B C H An empirical investigation of meta-heuristic and heuristic algorithms for a 2D packing problem 2001(01) 7. Zhang Defu. Kang Yan. Deng Ansheng A new heuristic recursive algorithm for the strip rectangular packing problem 2006 (08) 相似文獻(1條) 1.學位論文鄧冬梅復合材料鋪層排樣抆術硏究與開發2007 復合材料因其比強度高、比模量大、材料的剛度和強度可設汁等一系列優點,在航空航天領域得到廣泛應用,但高昂的價咯成了復合材料應用的最大壁 壘。國外的硏究和應用成果表明數字化技術是降低復合材料構件制造成本、提高構件性能的有效途徑。目前國內主要還以手工沒計和手工制造為主、自動化 程度不高,不僅浪費人力、物力,而且產品質量難以保證,因此有必要對復合材料數字化技術進行研究。優化排樣是復合材料構件數字化生產過程中的重要 環節。 本文在研宄各種排樣算法的基礎上,提岀丁新的矩形件排樣算法、優化算法以及不規則樣片的排樣算法,并與復合材料鋪層排樣的特點相結合開發了復 合材料鋪層排樣軟仁。主要研究內容和創新點如下 矩形件排樣不僅適用于矩形樣片的排放,也是不規則樣片排咩的基礎。本文在建立矩形件排樣數學模型的基礎上,介紹了各種常見的定序列矩形件排樣 算法并分析其特點,提出了一種新的啟發式排樣算法——最低輪廓線搜索算法。該算法滿足“最下最左”條件,克服了其他排樣算法對某些排欄圖不能給出 排列的缺點,實驗結果表明該算法排樣效果好于最低水平線算法和最下最左(BL)算法。利用該算法實現了大量不同規格圖紙的集中出圖,省時省力,節約 氏張2050%。 矩形件排樣問題具有圖形運算和組合優化兩方面的特性,單純的排樣算法只能解決圖形運算問題,樣片的排放順序對排樣結果同樣重要。針對較小規模 (一般少于100個圖形)的矩形件排樣問題,本文提岀了模擬退火與最低輪廓線搜索算法相結合的綜合優化算法。對于十多個圖形的排樣,該算法可短時間內求 得最優舾:對于近百個圖形的排樣,在排樣效果相當旳情冮下,該亥算法比其基于模擬退火的綜合優化算法效率提髙百以饣。針對大規模矩形件排樣問題 本文提出了蟻群笪法與最低軫廓線搜索算法相結合旳綜合優化算法,該算法比模擬退火與最低輪廓線算法相結合的綜合優化算法效率提高十倍以上。 不規則圖形排欄是所有排樣研究中的熱點和難點。本文將不規則樣片簡化成多邊形進行排樣,提出了兩種不同的解法方法:一是基于矩形的排樣方法 ,二是直接對多邊形進行排樣。基于矩形求解不規則樣片排樣時,將圖形運算、矩形件排樣算法及交互調整相結合,提出了基于矩形的多邊形綜合排樣算法 。通過各種優化組合策略,對單一樣片和多種樣片進行組合求其最小包絡矩形,從而將不規則形狀樣片排樣轉化為矩形件排樣進行求解。直接冄放多邊形時 ,重點研究兩個多邊形的臨界多邊形(NFP)的求解。首先對基于傾斜圖法的NFP求解法進行了改進和優化,完善了凹、凸兩多邊形NFP的求解,然后提出了適 用于任意兩多邊形N求解的邊界繞行法,該方法比基于傾斜圖的求解方法適用范圍廣,計算簡單、效率高。 根據復合材料構件數宇化生產的主要過程,分析總結了復合材料鋪層排樣的特點,并將伉化排樣算法與復合材料鋪層排樣的特點相結合,設計丌發了復 合材料構件鋪層排欄軟件系統。 引證文獻(3條) 1.盧遠志楊建新.文桂林.周兵.鐘志華基于排樣思想的工程圖坐標尺寸防干涉方法[期刊論文]中南大學學報(自然 科學版)2010(2) 2.張偉.安魯陵.邵撓眀.鄭盈一種矩形件分層排樣算法[期刊論文]宇航材料工藝2010(1) 3.陳婷.許超鈑金零件排樣技術及其發展[期刊論文]鍛壓裝備與制造技術2008(4) 本文鏈接http://d.wanfangdata.comcn/periodicAlyhclgy200704005.aspx 授權使用:廣東工業大學圖書館( gdgydxtsg),授權號:4flc88c5-bfdd-4dec-8ebf-9ec501113fe6 下載時間:2011年4月14日