基因演算法標準作業程序之研究

A Study of Standard Operation Procedure in Genetic Algorithm

林志強(Chih-Chiang Lin)

指導教授 ： 陳同孝

國立臺中科技大學/資訊學群/資訊科技與應用研究所/碩士(2006年)

摘要

以往處?最佳化問題的方式，常用的方法有線性規劃、動態規劃及分支界定等方法。當問題過於複雜時，上述方法會因問題太大導致電腦記憶體的?足而無法實作，或是需要長時間計算而?能有效求解，故希望能用基因演算法求得近似解。使用基因演算法求解時，需要選擇適當的基因運算子以及設定演算法的??。這些環結必須與問題做緊密的結合，才能有效地逼近到最佳解，但是如何決定基因運算子及??的設定方法是非常困難的。
因此本研究提出基因演算法標準作業程序(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.

並列關鍵字

Optimization ； Genetic Algorithm ； Standard Operation Procedure ； Local Search

參考文獻

[1] J. H. Holland, Adaptation in Natural and Artificial Systems, Ann Arbor, MI: The University of Michigan Press, 1975.

[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)

[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.

[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.