臺灣博碩士論文加值系統

現近年來，資訊技術迅速發展並被廣泛地應用於各個領域中。許多複雜的工程問題可藉由啟發式演算法解決。以鋼筋裁切為例，如何在已知數量及長度之原料鋼筋中，裁出所需鋼筋使得餘料最少或成本最低，便可利用啟發式演算法進行分析。
生物共生演算法(Symbiotic Organisms Search)為學者鄭明淵等人所發展的一種新式最佳化演算法。為提升SOS的性能，學者鄭明淵等人研究發展出自我調適生物共生演算法(Self-tuning SOS)，使用自身演算法調整SOS三個階段的權重參數。但由於其嵌套結構複雜龐大，使得演算法收斂速度極慢，耗時極長，效率性能有待提升。本研究在生物共生演算法的基礎上，針對三個階段的權重進行探討，提出自動調適生物共生演算法(Auto-tuning SOS)。在搜尋最佳解的過程中，使用視窗移動選擇階段權重，同時使用田口方法進行篩選，保留表現較好的參數組合。本研究引入50個標竿函數進行模式驗證，對比結果顯示自動調適生物共生演算法表現優異，並且在搜尋前期顯示了快速收斂的特質，可以通過減少外部循環次數來減少大量的運算時間。
本研究選用鋼筋裁切為案例，生物種群的編碼設計，採用兩倍於需求鋼筋數量維度之向量產生順序和組別，以「下次適應裝箱法」進行裝箱作業，計算目標函數值。研究結果顯示，本研究所建立之演算法模式，與GA、PSO、DE、ABC、SOS等演算法相比較，可獲得更佳最適解；與Self-tuning SOS相比有收斂較快的優勢。

In recent decades, information technology was wisely applied in various areas. Many complex engineering problems can be easily solved by metaheuristic algorithm. For example, the problem of steel bars cutting, which is aim to reduce the oddments or the cost under known material steel bars, can be analyzed by algorithm.
Symbiotic Organisms Search is a new algorithm that developed by Min-Yuan Cheng, etc. from CIC lab. To improve this algorithm, Cheng optimize the weights of three phases using SOS itself, which is named Self-tuning SOS. However, due to complicated nested double-structure, the algorithm converges very slowly and takes a long time. Based on SOS, this study brings out Auto-tuning SOS ,focusing on weights of three phases. It applies Sliding-Window and Taguchi Method during the search to reserve the better weights group. 50 benchmark functions are introduced into this new model, the results shows the Auto-tuning SOS performances well and converge in the early phase. Therefore, function evaluation can be reduced to save computing time.
This study takes steel bars cutting problem as case. Organism code consists of two parts, sequence and group. Next Fit rule is used to calculate the cost of cutting plan. Result shows that this model finds better optimum comparing with GA, PSO, DE, ABC, SOS. It also converges fast than Self-tuning SOS.

摘要
Abstract
目錄
表目錄
圖目錄
第1章 緒論
1.1 研究動機
1.2 研究目的
1.3 研究範圍與限制
1.4 研究方法與流程
1.5 論文架構
第2章 文獻回顧
2.1 啟發式演算法(Metaheuristic Algorithm)
2.1.1 啟發式演算法定義
2.1.2 啟發式演算法的特徵
2.2 標竿函數(Benchmark Function)
2.2.1 標竿函數的用途
2.2.2 標竿函數的分類
2.2.3 標竿函數的各式形狀
2.3 生物共生演算法(Symbiotic Organisms Search, SOS)
2.3.1 生物共生演算法概念
2.3.2 生物共生演算法流程圖
2.4 自我調適生物共生演算法(Self-tuning SOS)
2.4.1 算法簡介
2.4.2 Self-tuning SOS的優勢與缺陷
2.5 窗口移動搜尋(Sliding Window)
2.6 田口實驗方法(Taguchi Method)
2.6.1 田口方法簡介
2.6.2 田口方法的實施步驟
2.6.3 田口直交表
2.7 鋼筋裁切問題
第3章 Auto-tuning SOS模式建立
3.1 移動窗口設定
3.2 田口直交表
3.3 Auto-tuning SOS模式流程圖
3.4 方法測試與分析
3.4.1 標竿函數測試
3.4.2 比較分析
3.4.3 收斂圖分析
3.4.4 討論與應用
3.5 測試結果應用
第4章 案例測試與分析
4.1 鋼筋裁切問題
4.1.1 問題定義
4.1.2 編碼方式
4.1.3 下次適應裝箱法
4.2 推論模式應用流程
4.3 案例一資料與測試結果
4.3.1 案例一資料
4.3.2 案例一測試結果
4.4 案例二資料與測試結果
4.4.1 案例二資料
4.4.2 案例二測試結果
第5章 結論與建議
5.1 結論
5.2 建議
參考文獻
附錄A
A-1 標竿函數程式

[1] Y. LeCun, L. Bottou, Y. Bengio, and P. Haffner, "Gradient-based learning applied to document recognition," Proceedings of the IEEE, vol. 86, no. 11, pp. 2278-2324, 1998.
[2] J. Nielsen, "Heuristic evaluation," Usability inspection methods, vol. 17, no. 1, pp. 25-62, 1994.
[3] A. Kaveh and S. Talatahari, "A novel heuristic optimization method: charged system search," Acta Mechanica, vol. 213, no. 3, pp. 267-289, 2010.
[4] M.-Y. Cheng and D. Prayogo, "Symbiotic organisms search: a new metaheuristic optimization algorithm," Computers & Structures, vol. 139, pp. 98-112, 2014.
[5] 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.
[6] G. Taguchi, Introduction to quality engineering: designing quality into products and processes. 1986.
[7] I. H. Osman and G. Laporte, "Metaheuristics: A bibliography," ed: Springer, 1996.
[8] J. Holland, "Adaption in natural and artificial systems," Ann Arbor MI: The University of Michigan Press, 1975.
[9] J. Kennedy, "Particle swarm optimization," in Encyclopedia of machine learning: Springer, 2011, pp. 760-766.
[10] 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.
[11] M. Dorigo, M. Birattari, and T. Stutzle, "Ant colony optimization," IEEE computational intelligence magazine, vol. 1, no. 4, pp. 28-39, 2006.
[12] Z. W. Geem, J. H. Kim, and G. Loganathan, "A new heuristic optimization algorithm: harmony search," simulation, vol. 76, no. 2, pp. 60-68, 2001.
[13] D. Karaboga and B. Basturk, "A powerful and efficient algorithm for numerical function optimization: artificial bee colony (ABC) algorithm," Journal of global optimization, vol. 39, no. 3, pp. 459-471, 2007.
[14] 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 Machines and Systems-2nd I* PROMS Virtual International Conference (3-14 July 2006), 2011: sn.
[15] X.-S. Yang, "Firefly algorithms for multimodal optimization," in International symposium on stochastic algorithms, 2009, pp. 169-178: Springer.
[16] C. Blum and A. Roli, "Metaheuristics in combinatorial optimization: Overview and conceptual comparison," ACM Computing Surveys (CSUR), vol. 35, no. 3, pp. 268-308, 2003.
[17] 杜玲玲, "混合超启发式法求解大规模 VRP 的优化研究," 华东交通大学学报, vol. 28, no. 1, pp. 62-67, 2011.
[18] 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.
[19] T. Back, Evolutionary algorithms in theory and practice: evolution strategies, evolutionary programming, genetic algorithms. Oxford university press, 1996.
[20] R. L. Haupt and S. E. Haupt, Practical genetic algorithms. John Wiley & Sons, 2004.
[21] R. Oldenhuis, "Test functions for global optimization algorithms," 2014.
[22] G. A. Ortiz, "Evolution Strategies (ES)," Mathworks: Natick, MA, USA, 2012.
[23] D. Karaboga and B. Akay, "A comparative study of artificial bee colony algorithm," Applied mathematics and computation, vol. 214, no. 1, pp. 108-132, 2009.
[24] 楊秉蒼, 陳志賢, and 單明陽, "營建鋼筋裁切規劃系統實作以 EXCEL 規劃求解 1," 2002.
[25] P. C. Gilmore and R. E. Gomory, "A linear programming approach to the cutting-stock problem," Operations research, vol. 9, no. 6, pp. 849-859, 1961.
[26] 楊秉蒼, 呂淑鈴, and 葉怡成, "以線性規劃作建築工程鋼筋裁切最適化之研究," 第十六屆全國技術及職業教育研討會, 工業類, 土木建築, 第 81 頁~ 第 90 頁, 2001.
[27] 李冠廷, "質群演算法應用於鋼筋裁切最佳化問題之研究," 淡江大學土木工程學系碩士班學位論文, pp. 1-86, 2007.
[28] 盧立昕, "BH 型鋼裁切問題之啟發式解法," 成功大學土木工程學系學位論文, pp. 1-79, 2010.
[29] R. R. Prabodanie, J. F. Raffensperger, and M. W. Milke, "A pollution offset system for trading non-point source water pollution permits," Environmental and Resource Economics, vol. 45, no. 4, pp. 499-515, 2010.
[30] 李輝煌, 田口方法-品質設計的原理與實務. 高立圖書有限公司, 2004.
[31] M.-Y. Cheng and L.-C. Lien, "Hybrid Artificial Intelligence–Based PBA for Benchmark Functions and Facility Layout Design Optimization," Journal of Computing in Civil Engineering, vol. 26, no. 5, pp. 612-624, 2012.
[32] 歐淑民, "以改良粒子群演算法求解鋼筋裁切最佳化問題," 朝陽科技大學營建工程系碩士班學位論文, vol. 1-56, 2011.