臺灣博碩士論文加值系統

以往處理最佳化問題的方式，常用的方法有線性規劃、動態規劃及分支界定等方法。當問題過於複雜時，上述方法會因問題太大導致電腦記憶體的不足而無法實作，或是需要長時間計算而不能有效求解，故希望能用基因演算法求得近似解。使用基因演算法求解時，需要選擇適當的基因運算子以及設定演算法的參數。這些環結必須與問題做緊密的結合，才能有效地逼近到最佳解，但是如何決定基因運算子及參數的設定方法是非常困難的。
因此本研究提出基因演算法標準作業程序(SOPGA)來求解最佳化問題。本研究將各種最佳化問題分為三類，並定義出相對應的編碼型態與其適用的基因運算子。為了改進基因演算法的搜尋能力，SOPGA採用三種不同的區域搜尋法來分別處理上述三類問題。對於簡化最佳化參數設定的問題，本研究使用自適應調整法在演化的過程中決定適當的參數值。在實驗部份以方程式求極值問題、旅行銷售員問題及背包問題當成實驗對象。實驗結果顯示，SOPGA能簡化基因演算法的參數設定可以有效地求解最佳化問題。

Linear Programming, Dynamic Programming, and Branch-and-Bound Algorithm are among the popular methods in solving optimization problems. While the problems are complicated, these methods are time and memory consuming, and thus they are inefficient in finding solutions. In this thesis, we focus on the improvement of Genetic Algorithm. In order to employ Genetic Algorithm more efficiently, we should know how to select operators and parameters of Genetic Algorithm. For approaching the optimal solution, the selections must be suitable and they are dependent on the real problem. However, it is difficult to determine operators and parameters in Genetic Algorithm. Hence, this study aims to present the Standard Operation Procedure in Genetic Algorithm (SOPGA) to solve the optimization problem. We briefly divide the problem into three categories. For each category, we present its corresponding encoding scheme and relevant genetic operators. In order to improve the search capability of Genetic Algorithm, SOPGA uses three local search methods to deal with the problems in each of the three categories. To facilitate the setting of the genetic parameters, we use self-adaptive control to determine relevant parameters. We use three popular templates i.e., the unconstrained optimization problem, the traveling salesman problem, and the knapsack problem to test our method. The experimental results show that SOPGA is useful to find approximately the optimal solution.

中文摘要
英文摘要
目錄
表目錄
圖目錄
第一章 緒論
1-1 研究動機
1-2 研究目的
1-3 研究範例
1-4 研究流程
1-5 論文架構
第二章 文獻探討
2-1 基因演算法的架構
2-2 基因演算法的流程
2-3 基因演算法的特點
2-4 適應函數
2-5 染色體的編碼
2-6 基因演算法的參數
2-7 基因運算子
2-8 基因演法算的搜尋特性
2-9 區域搜尋法
2-10 基因演算法的失敗原因及不適用範圍
2-11 基因演算法的應用
第三章 研究方法
3-1 目標函數及染色體設計方法
3-2 基因運算子設計方法
3-2-1 選擇運算子的設計方法
3-2-2 遺傳運算子的設計方法
3-2-3 遺傳運算子配對方法
3-3 自適應參數設計方法
3-4 增加基因演算法的搜尋能力
3-5 基因演算法標準作業程序SOPGA
第四章 實驗結果及分析
4-1 實驗設計
4-2 基本特性實驗及分析
4-2-1 交配運算子測試
4-2-2 突變運算子測試
4-2-3 適應值調整測試
4-2-4 進化策略測試
4-2-5 區域搜尋測試
4-2-6 群族大小測試
4-2-7 固定參數與自適應參數測試
4-2-8 初始值測試
4-3 方程式極值實驗及分析
4-4 旅行銷售員實驗及分析
4-5 背包問題實驗及分析
第五章 結論與未來研究方向
5-1 結論
5-2 研究成果與貢獻
5-3 未來研究方向
參考文獻

[1] J. H. Holland, Adaptation in Natural and Artificial Systems, Ann Arbor, MI: The University of Michigan Press, 1975.
[2] R.C. Chen, T.S. Chen, C.C. Feng, C.C. Lin, and K.C. Lin, “Application of Genetic Algorithm on Production Scheduling of Elastic Knitted Fabrics,” Engineering and Applied Sciences, vol. 1, no. 2, pp. 149-153, 2006.
[3] K.C. Lin, T.S. Chen, R.C. Chen, and C.C. Lin, “A Production Scheduling System Based on Self-adaptive Genetic Algorithm for Manufacturing Elastic Knitted Fabrics,” in Proceedings of International Conference on Intelligent Systems and Knowledge engineering, Shanghai, China, 2006.(CD-ROM)
[4] R.C. Chen, S.S. Li, C.C. Lin, and T.S. Chen, “Application of Self-Adaptive Genetic Algorithm on Allocating International Demand to Global Production Facilities,” in Proceedings of Sixth World Congress on Intelligent Control and Automation, Dalian, China, 2006. (CD-ROM)
[5] S.S. Li, R.C. Chen, and C.C. Lin, “A Genetic Algorithm-Based Decision Support System for Allocating International Apparel Demand,” WSEAS Transactions on Information Science and Applications, vol. 3, no. 7, pp. 1294-1299, 2006.
[6] R.C. Chen, C.C. Lin, and S.S. Li, “An Automatic Decision Support System Based on Genetic Algorithm for Global Apparel Manufacturing,” Soft Computing, vol. 1, no. 1, pp. 17-21, 2006.
[7] R.C. Chen, S.S. Li, C.C. Feng, and C.C. Lin, “A GA-Based Global Decision Support System for Garment Production,” in Proceedings of the IEEE International Conference on Neural Networks and Brain, Beijing, China, 2005, pp. 805-809.
[8] R.C. Chen, T.S. Chen, and C.C. Lin, “A New Binary Support Vector System for Increasing Detection Rate of Credit Card Fraud,” Pattern Recognition and Artificial Intelligence, vol. 20, no. 2, pp. 227-239, 2006.
[9] T.S. Chen, R.C. Chen, C.C. Lin, T.H. Tsai, S.Y. Li, and X. Liang, “Classification of Microarray Gene Expression Using a Novel Binary Support Vector System,” in Proceedings of the IEEE International Conference on Neural Networks and Brain, Beijing, China, 2005, pp. 485-489.
[10] A.E. Carter and C.T. Ragsdale, “A new approach to solving the multiple travelingsalesperson problem using genetic algorithms,” European Journal of Operational Research, In Press, Corrected Proof, 2005.
[11] Z. Michalewicz, Genetic Algorithm+Data Structure=Evolution Programs, 2nd ed. New York: Springer-Verlag, 1992.
[12] M. Gen and R. Cheng, Genetic Algorithms and Engineering Design, New York: Wiley, 1997.
[13] M. Gen and R. Cheng, Genetic Algorithms and Engineering Optimization, New York: Wiley, 1999.
[14] M. Sakawa, and K. Kato, “Genetic algorithms with double strings for 0–1 programming problems,” European Journal of Operational Research, vol.144, pp. 581–597, 2003.
[15] D. E. Goldberg, Genetic Algorithms in Search, Optimization Machine Learning Reading, MA: Addison-Wesley, 1989.
[16] M. Gen, and B. Liu, “Evolution program for production plan problem,” Engineering Design and Automation, vol. 1, no. 3, pp. 199-204, 1995.
[17] R.S. Adve, T.K. Sarkar, S.M. Rao, E.K. Miller, and D.R. Pflug, “Application of the Cauchy method for extrapolating/interpolating narrowband system responses,” IEEE Transactions on Microwave Theory and Techniques, vol. 45, no. 5, pp. 837-845, 1997.
[18] J. Renegar, “A polynomial-time algorithm, based on Newton's method for linear programming,” Mathematical Programming, vol. 40, pp. 59-93, 1998.
[19] M. J. D. Powell, “Restart procedures for the conjugate gradient method,” Mathematical Programming, vol. 12, pp. 241-254, 1977.
[20] R. Setiono, and L.C.K. Hui, “Use of a quasi-Newton method in a feedforward neural networkconstruction algorithm,” IEEE Transactions on Neural Networks,vol. 6, no. 1, pp. 273-277, 1995.
[21] R. Hooke, and T. A. Jeeves, “Direct Search Solution of Numerical and Statistical Problems,” Journal of the ACM, vol. 8, no.2, pp. 212-229, 1961.
[22] D.R. Sule, Industrial scheduling, Boston: PWS, 1996.
[23] G.E. Liepins, M.R. Hillard, T. Richardson, and M. Palmer, “Genetic Algorithm Application to Set Covering and Traveling Salesman Problems,” Operations research and artificial intelligence: the Integration of Problem Solving Strategies, Boston: Kluwer Academic, 1990.
[24] G.E. Liepins, and M.R. Hillard, “Genetic Algorithms: Foundations and Applications,” Annals of Operations Research, vol. 21, pp. 31-58, 1989.
[25] G. REINELT, “TSPLIB–A traveling salesman problem library,” ORSA J. Comput. vol. 3, pp. 376-384, 1991.
[26] D. H. Ackley, A connectionist machine for genetic hillclimbing, Boston: Kluwer Academic, 1987.
[27] J.A. Vasconcelos, J.A. Ramirez, R.H.C. Takahashi, and R.R. Saldanha, “Improvements in Genetic Algorithm,” IEEE Transactions on Magnetics, vol. 37, pp. 3414-3417, 2001.
[28] H. Mühlenbein, D. Schomisch, and J. Born, "The Parallel Genetic Algorithm as Function Optimizer," Parallel Computing, vol. 17, pp. 619-632, 1991.
[29] J.S. Jang, C.T. Sun and E. Mizutani, Neuro-Fuzzy and Soft Computing, Prentice Hall 1997.
[30] H. Rosenbrock. “An Automatic Method For Finding the Greatest or Least Value of a Function,” The Computer Journal, vol. 3, pp. 175-184, 1960.