研究生: |
王俊堯 Chun-Yao Wang |
---|---|
論文名稱: |
應用自動調適生物共生演算法於二維鋼板切割最佳化之研究 Auto-tuning SOS Solving Two-dimensional steel Plate cutting Problems |
指導教授: |
鄭明淵
Min-Yuan Cheng |
口試委員: |
郭斯傑
Sy-Jye Guo 吳育偉 Yu-Wei Wu |
學位類別: |
碩士 Master |
系所名稱: |
工程學院 - 營建工程系 Department of Civil and Construction Engineering |
論文出版年: | 2018 |
畢業學年度: | 106 |
語文別: | 中文 |
論文頁數: | 88 |
中文關鍵詞: | 啟發式演算法 、二維平面切割 、自動調適生物共演算法 、最佳化系統 |
外文關鍵詞: | Heuristic Algorithm, 2D plane cutting, Auto-tuning SOS, Optimization system |
相關次數: | 點閱:209 下載:0 |
分享至: |
查詢本校圖書館目錄 查詢臺灣博碩士論文知識加值系統 勘誤回報 |
近年來隨著原物料取得越來越困難以及原物料價格的上漲,如何有效地將原物料的使用價值發揮到最大,是相關產業所要面對的重要問題。探討加工生產業以及營建產業中,原物料經常遇到裁切之問題包含鋼板切割、壓克力板、玻璃裁切、木板…等,這些都是屬於二維平面切割的問題,如何使用將原物料的使用率發揮到最大、將切割後剩餘的材料降至最少是一個值得關注的課題。
近年來啟發式演算法的應用逐漸成熟,目前工程上許多複雜問題都可以藉由啟發式演算法進行求解。本研究所應用之自動調適生物共生演算法(Auto-tuning SOS)為一創新最佳化演算法[2],Auto-tuning SOS是以生物共生演算法(SOS)為基礎,結合田口實驗方法及窗口移動搜尋兩種方法搜尋全域最佳解,經測試後發現此方法,具有提升搜尋效率,並且減少消耗時間以及資源的優勢。
本研究以解決二維平面切割的問題,並針對鋼板切割問題進行探討,以找出餘料最小之目標函數直。然後再與基因演算法(Genetic Algorithm, GA)、粒子群演算法(Particle Swarm Optimization, PSO)、生物共生演算法(Symbiotic Organisms Search, SOS)等演算法進行求解比較,找出適用於鋼板切割問題的最優良演算法。
經運算測試後得証,使用自動調適生物共生演算法在二維平面切割的問題時,可得出最佳之結果。
In recent years, it has become increasingly difficult to obtain raw materials and the price of raw materials has risen. How to effectively maximize the use value of raw materials is an important issue for related industries. In the processing industry and the construction industry, the original material often encounters cutting problems including steel plate, acrylic plates, glass, wooden plates, etc. These are all problems with 2D plane cutting.
The application of heuristic algorithms has gradually matured in recent years. Many current engineering problems can be solved by heuristic algorithms. Auto-tuning SOS is a new optimization algorithm based on the SOS and Self-tuning SOS, plus the Taguchi Methods and Sliding Window. After testing, Auto-tuning SOS was found to improve search efficiency and reduce the time spent and the advantages of resources.
This study solves the problem of 2D plane cutting combined with Auto-tuning SOS. Organism code consists of three parts, Box Packing Sequence, Vector of Box Orientations and Vector of Placement Heuristics. Compared with other algorithms such as Genetic Algorithm (GA), Particle Swarm Optimization (PSO), and Symbiotic Organisms Search (SOS)
[1]Min-Yuan Cheng and Doddy Prayogo,”Symbiotic Organisms Search: A new metaheuristic optimization algorithm” ,Computers and Structures 139 pp.98–112 ,2014
[2]邱雅萍,”自動調適生物共生演算法在工程上之應用—以鋼筋裁切為例,”台灣科技大學營建系碩士學位論文,2017
[3]K. Tang et al, "Benchmark functions for the CEC 2008 special session and competition on large scale global optimization," Nature Inspired Computation and Applications Laboratory, USTC, China, vol. 24, 2007.
[4]J.E. Beasley, "A population heuristic for constrained two-dimensional non-guillotine cutting," European Journal of Operational Research 156 ,pp.601–627,2004
[5]邢文訓,謝金星”現代優化計算方法”,1999
[6]J. Holland, "Adaption in natural and artificial systems," Ann Arbor MI: The University of Michigan Press, 1975.
[7]J. Kennedy and R. C. Eberhart, “Particle swarm optimization,” in: Proc. IEEE Int. Conf. on Neural Networks, Perth, Australia, vol. 4, pp. 1942-1948, 1995.
[8]R. Storn and K. Price, "Differential evolution–a simple and efficient heuristic for global optimization over continuous spaces," Journal of global optimization, vol. 11, no. 4, pp. 341-359, 1997.
[9]Karaboga, D, "An idea based on honey bee swarm for numerical optimization, "Technical Report-TR06, Erciyes Univ. Press, Erciyes. ,2005
[10]D. Pham, A. Ghanbarzadeh, E. Koc, S. Otri, S. Rahim, and M. Zaidi,"The bees algorithm-A novel tool for complex optimisation," in Intelligent Production 76 Machines and Systems-2nd I* PROMS Virtual International Conference, 2011:
[11]M.Dorigo, M.Birattari, and T.Stutzle, "Ant colony optimization," IEEE computational intelligence magazine, vol. 1, no. 4, pp. 28-39, 2006.
[12]張均豪,”應用改良式基因演算法於鋼桁架橋梁桿件最佳化設計,”台灣科技大學營建系碩士學位論文,2015
[13]連立川,” 粒子蜂群演算法於營建場址配置最佳化之研究,”台灣科技大學營建系碩士學位論文,2010
[14]銀徽,”以超啟發式演算法進行鋼筋混凝土結構最佳化設計,”營建管理季刊,2009
[15]I.T. Yang and Y.H. Hsieh, "Reliability-based design optimization with discrete design variables and non-smooth performance functions: AB-PSO algorithm," Automation in construction, vol. 20, no. 5, pp. 610-619, 2011
[16]G. Taguchi ,"Introduction to quality engineering: designing quality into products and processes," 1986.
[17]李輝煌, 田口方法-品質設計的原理與實務. 高立圖書有限公司, 2004.
[18]DYCKHOFF,”A typology of cutting and packing problems,” European Journal of Operational Research 44,pp145-159,1990
[19]Gerhard Wascher , Heike Hausner and Holger Schumann, ”An improved typology of cutting and packing problems, ” European Journal of Operational Research 183 pp.1109–1130,2007
[20]Janne Karelahti, ”Solving the cutting stock problem in the steel industry ” Department of Engineering Physics and Mathematics,2002
[21]Jakobs S ,”On genetic algorithms for the packing of polygons. ” Eur J Oper Res 88:pp165–18, 1996
[22]A. Ramesh Babu and N. Ramesh Babu,”Effective nesting of rectangular parts in multiple rectangular sheets using genetic and heuristic algorithms,” International Journal of Production Research,Vol 37,PP.1625-1643,1999
[23]葉進儀,吳泰熙,張維昌,”結合平行基因演算法與排列啟發式方法解二維長方形排列問題,” 品質學報 Vol. 13, No. 1 ,2006
[24]Wu, T.H., Chen, J.F., Low, C.Y., and Tang, P.T.” Nesting of two-dimensional parts in multiple plates using hybrid algorithm, ” International Journal of Production Research, 41 (16), 3883-3900,2003,
[25]T.W.Leung , C.H.Yung and Marvin D.Troutt,” Applications of genetic search and simulated annealing to the two-dimensional non-guillotine cutting stock problem,”Computers and Industrial Engineering Volume 40 Issue 3, Pages 201 - 214 ,2001
[26]K. K. LAI and JIMMY W. M. CHAN ,”DEVELOPING A SIMULATED ANNEALING ALGORITHM FOR THE CUTTING STOCK PROBLEM ,” Computers ind. Engng Vol. 32, No. 1, pp. 115-127, 1997
[27José Fernando Gonçalves and Mauricio G. C. Resende,” A parallel multi-population genetic algorithm for a constrained two-dimensional orthogonal packing problem,” Journal of Combinatorial Optimization, Volume 22, Issue 2, pp 180–201 ,2011
[28]José FernandoGonçalves ,”A hybrid genetic algorithm for the two-dimensional knapsack problem. ,” Eur J Oper Res 183,pp1150–1166, 2007
[29]R Alvarez-Valdes, FParren and JM Tamarit,”A GRASP algorithm for constrained two-dimensional non-guillotine cutting problems,” Journal of the Operational Research Society 56, pp414–425, 2005
[30]Alvarez-Valdes R, Parreño F, Tamarit J,” A tabu search algorithm for a two-dimensional nonguillotine cutting problem. ,” Eur J Oper Res 183:pp1167–1182, 2007
[31]Beasley JE ,”An exact two-dimensional non-guillotine cutting tree search procedure. ,” Oper Res 33:49–64, 1985
[32]Hadjiconstantinou E, Christofides N , ”An exact algorithm for general, orthogonal, two dimensional knapsack problems. ” Eur J Oper Res 83:39–56, 1995
[33]Wang PY ,” Two algorithms for constrained two-dimensional cutting stock problems. ”Oper Res31,pp573–586, 1983
[34]Christofides N, Whitlock C ,” An algorithm for two dimensional cutting problems. ” Oper Res 25,pp31–44, 1977
[35]Fekete SP, Schepers J ”A combinatorial characterization of higher-dimensional orthogonal packing. ” Math Oper Res 29,pp353–368, 2004
[36]Lai KK, Chan JWM ”Developing a simulated annealing algorithm for the cutting stock problem. ”Comput Ind Eng 32, pp115–127, 1997
[37]Leung TW, Chan CK, Troutt MD,”Application of a mixed simulated annealing-genetic algorithm heuristic for the two-dimensional orthogonal packing problem. ” Eur J Oper Res 141:pp241–252, 2003
[38]Hopper E, Turton BCH, ”An empirical investigation of meta-heuristic and heuristic algorithms for a 2D packing problem. ” Eur J Oper Res 128:pp34–57, 2001
[39]José Fernando Gonçalves and Mauricio G.C. Resende ,”A biased random key genetic algorithm for 2D and 3D bin packing problems,” International Journal of Production Economics, vol. 145, issue 2, 500-510, 2013
[40]黃詩琪,”開發BIM程式產出建築鋼筋數量估算報表之研究,”台灣科技大學營建系碩士學位論文,2016
[41]盧立昕, "BH 型鋼裁切問題之啟發式解法," 成功大學土木工程學系學位論文, 2010
[42]陳正誠,”鋼結構設計手冊(極限設計法)” 2012