菁英微調突變式基因演算法於多極值函數之最佳化｜國立臺灣科技大學博碩士論文系統

簡易檢索 / 詳目顯示

回結果列表

研究生：	盧書豪 Shu-hao Lu
論文名稱：	菁英微調突變式基因演算法於多極值函數之最佳化 Genetic Algorithms with Fine-Tuning Mutation on Elite for Multi-Modal Function Optimization
指導教授：	呂森林 none 黃聰耀 none
口試委員:	王英才 none
學位類別：	碩士 Master
系所名稱：	工程學院 - 機械工程系 Department of Mechanical Engineering
論文出版年：	2005
畢業學年度：	93
語文別：	英文
論文頁數：	107
中文關鍵詞：	保留菁英政策、微調突變運算子、基因演算法、最佳化、多極值函數
外文關鍵詞：	Elitist strategy, Genetic algorithms, Optimization, Fine-tuning mutation, Multi-modal functions
相關次數：	點閱：374 下載：3
分享至:	分享至facebook 分享至twitter

查詢本校圖書館目錄查詢臺灣博碩士論文知識加值系統勘誤回報

本研究旨在提出一個有效的方法來改良基因演算法：菁英微調突變式基因演算法，以期精確地搜尋多極值函數的全域最佳解。應用此方法可以同時實現下列兩個目標：使得已經獲得的解答可以更準確，並且維持原有的全域搜尋能力。換言之，要在提升準確度的同時，仍保留族群的雜異程度。在本研究中，提出一種新式的基因運算子：微調突變運算子。有關於微調突變運算子的設計方法，以及微調突變與保留菁英政策的結合方式，將在本文中有詳細的詮釋。
本研究使用五個不同複雜度的多極值函數來模擬，並且比較菁英微調突變式基因演算法與傳統的基因演算法，搜尋效能的表現結果。在大多數的情況下，菁英微調突變式基因演算法，可以在花費較少的迭代數目時，即準確地收斂到全域最佳解。同時，菁英微調突變式基因演算法也有較高的機率可以達到收斂。收斂機率之平均改善率為24.43 (%)，迭代次數之平均改善率為14.50(%)，計算時間之平均改善率為12.81(%)。模擬的結果也顯示，本研究提出的方法可以應用在大多數的基因演算法之參數設定上，諸如：不同的族群數、或者不同的最大迭代次數，我們也相信此方法對於大多數的基因演算法有很高的適用性。

This thesis proposes an efficient approach for multimodal function optimization using Genetic Algorithms (GAs). We recommend the use of Fine-Tuning Mutation with Elitist Strategy (FTME) to realize the twin goals of perfecting the existing solution (exploitation) and maintaining the searching capability to the whole solution space (exploration). To be specific, the accuracy is enhanced without losing the genetic diversity of population. In the GA using FTME (GA-FTME), a novel genetic operator called fine-tuning mutation is proposed. The device of fine-tuning mutation and the combination mechanism of FTME are interpreted.
The performances of the GA-FTME and the Standard GA (SGA) with elitist strategy are compared in optimizing several massively multimodal functions with varying complexities. For most functions, the GA-FTME converges to the global optimum precisely in fewer generations than the SGA, and it achieves a higher convergent probability. The average rate of improvement on convergent probability is 24.43(%). The average rate of improvement on the average critical generations is 14.50(%). The average rate of improvement on the average computation time is 12.81(%). The simulations also demonstrate that the FTME can be applied to most settings of parameters in GAs, such as using different population size and different maximum generation number. We believe that the FTME has a high applicability to most of GAs.

Abstract in Chinese . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . I
Abstract in English . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . II
Acknowledgements . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . III
Contents . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . IV
Nomenclature . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . VI
List of Figures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . IX
List of Tables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . XII
Chapter 1. Introduction and Literatures Review . . . . . . . . . . . . . . . . . . . . . 1
1.1 Background . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.2 Literature Review . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.3 Research Motivation and Goal . . . . . . . . . . . . . . . . . . . . . 15
1.4 Thesis Structure . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
Chapter 2. Genetic Algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
2.1 The Fundamentals of Genetic Algorithms . . . . . . . . . . . . 17
2.2 The Procedures of Genetic Algorithms . . . . . . . . . . . . . . . 18
2.2.1 Initialization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
2.2.2 Decoding . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
2.2.3 Evaluating Fitness . . . . . . . . . . . . . . . . . . . . . . . . . . 21
2.2.4 Selection Operator . . . . . . . . . . . . . . . . . . . . . . . . . . 22
2.2.5 Crossover Operator . . . . . . . . . . . . . . . . . . . . . . . . . 22
2.2.6 Mutation Operator . . . . . . . . . . . . . . . . . . . . . . . . . . 23
2.2.7 Termination Criteria . . . . . . . . . . . . . . . . . . . . . . . . 24
Chapter 3. Applying Fine-Tuning Mutation with Elitist Strategy . . . . . 25
3.1 Design of Fine-Tuning Mutation . . . . . . . . . . . . . . . . . . . 25
3.1.1 What Fine-Tuning Mutation is . . . . . . . . . . . . . . . . 26
3.1.2 How Fine-Tuning Mutation is Designed . . . . . . . . . 28
3.2 Conventional Elitist Strategy . . . . . . . . . . . . . . . . . . . . . . 36
3.3 Combining Fine-Tuning Mutation with Elitist Strategy . . 38
Chapter 4. Simulations and Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42
4.1 Parameters Settings . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42
4.2 Performance Measures . . . . . . . . . . . . . . . . . . . . . . . . . . . 46
4.3 Benchmark Functions for Optimization . . . . . . . . . . . . . . 50
4.3.1 Numerical Example 1 . . . . . . . . . . . . . . . . . . . . . . . 51
4.3.2 Numerical Example 2 . . . . . . . . . . . . . . . . . . . . . . . 60
4.3.3 Numerical Example 3 . . . . . . . . . . . . . . . . . . . . . . . 68
4.3.4 Numerical Example 4 . . . . . . . . . . . . . . . . . . . . . . . 79
4.3.5 Numerical Example 5 . . . . . . . . . . . . . . . . . . . . . . . 90
Chapter 5. Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 98
References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 100
Author . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 107

                                

[1] Holland, J.H., “Adaptation in natural and artificial systems”, Ann Arbor, MI: The University of Michigan Press, 1975.
[2] De Jong, K.A., “An analysis of the behavior of a class of genetic adaptive systems”, Ph. D. Dissertation, The University of Michigan, Ann Arbor, 1975.
[3] Goldberg, D.E., “Genetic algorithms in search, optimization and machine learning”, Reading, MA: Addison-Wesley, 1989.
[4] Davis, Lawrence, “Handbook of genetic algorithms”, International Thomson Computer Press; Reissue edition, 1996.
[5] Greenwell, R.N., Angus, J.E., Finck, M., “Optimal mutation probability for genetic algorithms”, Mathematical and Computer Modelling (Oxford), Vol. 21, No. 8, pp. 1-11, 1995.
[6] Lis, Joanna, “Genetic algorithm with the dynamic probability of mutation in the classification problem”, Pattern Recognition Letters, Vol. 16, No. 12, pp. 1311-1320, Dec. 1995.
[7] Lis, Joanna, “Parallel genetic algorithm with the dynamic control parameter”, Proceedings of the IEEE Conference on Evolutionary Computation, ICEC, pp. 324-329, May. 1996.
[8] Srinivas, M., Patnaik, L.M., “Adaptive probabilities of crossover and mutation in genetic algorithms”, IEEE Transactions on Systems, Man and Cybernetics, Vol. 24, No. 4, pp. 656-667, Apr. 1994.
[9] Shimodaira, H., “A new genetic algorithm using large mutation rates and population-elitist selection (GALME)”, Proceedings of the International Conference on Tools with Artificial Intelligence, pp. 25-32, Nov. 1996.
[10] Tinos, R., De Carvalho, A.C.P.L.F., “A genetic algorithm with gene dependent mutation probability for non-stationary optimization problems”, Proceedings of the 2004 Congress on Evolutionary Computation, CEC2004, Vol. 2, pp. 1278-1285, Jun. 2004.
[11] Ohkura, K., Ueda, K., “A genetic algorithm with neutral mutations for solving nonstationary function optimization problems”, Proceedings of the Australian and New Zealand Conference on Intelligent Information Systems, pp. 248-252, Nov. 1994.
[12] Ohkura, K., Ueda, K., “A genetic algorithm with neutral mutations for massively multimodal function optimization”, Proceedings of the IEEE Conference on Evolutionary Computation, ICEC, Vol. 1, pp. 361-366, Nov. 1995.
[13] Hinterding, Robert, “Gaussian mutation and self-adaption for numeric genetic algorithms”, Proceedings of the IEEE Conference on Evolutionary Computation, ICEC, Vol. 1, pp. 384-388, Nov. 1995.
[14] Fukumi, M., Akamatsu, N., “A genetic algorithm with deterministic mutation based on neural network learning”, Systems and Computers in Japan, Vol. 29, No. 3, pp. 10-17, Mar. 1998.
[15] Fukumi, M., Akamatsu, N., “Method to design a neural pattern recognition system by using a genetic algorithm with partial fitness and a deterministic mutation”, Proceedings of the IEEE International Conference on Systems, Man and Cybernetics, Vol. 3, pp. 1989-1993, Oct. 1996.
[16] Fukumi, M., Akamatsu, N., “Rule extraction from neural networks trained using evolutionary algorithms with deterministic mutation”, IEEE International Conference on Neural Networks - Conference Proceedings, Vol. 1, pp. 686-689, May. 1998.
[17] Ohki, M., Moriyama, T., Ohkita, M., “Optimization of fuzzy reasoning by genetic algorithm using variable bit-selection probability”, Systems and Computers in Japan, Vol. 30, No. 6, pp. 54-63, Jun. 1999.
[18] Fogel, D.B., Anderson, R.W., “Revisiting Bremermann's genetic algorithm: I. Simultaneous mutation of all parameters”, Proceedings of the IEEE Conference on Evolutionary Computation, ICEC, Vol. 2, pp. 1204-1209, Jul. 2000.
[19] Lim, M.H., Yuan, Y., Omatu, S., “Efficient genetic algorithms using simple genes exchange local search policy for the quadratic assignment problem”, Computational Optimization and Applications, Vol. 15, No. 3, pp. 249-268, 2000.
[20] Folino, G., Pizzuti, C., Spezzano, G., “Parallel hybrid method for SAT that couples genetic algorithms and local search”, IEEE Transactions on Evolutionary Computation, Vol. 5, No. 4, pp. 323-334, Aug. 2001.
[21] Koper, E.M., Wood, W.D., Schneider, S.W., Baldwin, R.O., Hill, R.R., “A genetic algorithm and local search technique for minimization of monopole coupling on aircraft by physical antenna placement”, IEEE Antennas and Propagation Society, AP-S International Symposium (Digest), Vol. 2, pp. 358-361, 2002.
[22] Koper, E.M., Wood, W.D., Schneider, S.W., “Aircraft antenna coupling minimization using genetic algorithms and approximations”, IEEE Transactions on Aerospace and Electronic Systems, Vol. 40, No. 2, pp. 742-751, Apr. 2004.
[23] Jaszkiewicz, Andrzej, “Genetic local search for multi-objective combinatorial optimization”, European Journal of Operational Research, Vol. 137, No. 1, pp. 50-71, Feb. 2002.
[24] Jaszkiewicz, Andrzej, “On the performance of multiple-objective genetic local search on the 0/1 knapsack problem-A comparative experiment”, IEEE Transactions on Evolutionary Computation, Vol. 6, No. 4, pp. 402-412, Aug. 2002.
[25] Jaszkiewicz, A., Kominek, P., “Genetic local search with distance preserving recombination operator for a vehicle routing problem”, European Journal of Operational Research, Vol. 151, No. 2, pp. 352-364, Dec. 2003.
[26] Ishibuchi, H., Yoshida, T., Murata, T., “Balance between genetic search and local search in memetic algorithms for multiobjective permutation flowshop scheduling”, IEEE Transactions on Evolutionary Computation, Vol. 7, No. 2, pp. 204-223, Apr. 2003.
[27] Ombuki, B.M., Ventresca, M., “Local search genetic algorithms for the job shop scheduling problem”, Applied Intelligence, Vol. 21, No. 1, pp. 99-109, Jul./Aug. 2004.
[28] Mahinthakumar, G., Sayeed, M., “Hybrid genetic algorithm - Local search methods for solving groundwater source identification inverse problems”, Journal of Water Resources Planning and Management, Vol. 131, No. 1, pp. 45-57, Jan./Feb. 2005.
[29] Rajendran, I., Vijayarangan, S., “Optimal design of a composite leaf spring using genetic algorithms”, Computers and Structures, Vol. 79, No. 11, pp. 1121-1129, Apr. 2001.
[30] Venkataraman, P., “Applied optimization with MATLAB Programming / P. Venkataraman”, John Wiley & Sons, New York, 2002.
[31] Zitzler, E., Deb, K., Thiele, L., “Comparison of multiobjective evolutionary algorithms: empirical results”, Evolutionary Computation, Vol. 8, No. 2, pp. 173-195, June. 2000.
[32] Chen, X.P., Jiang, M., Xu, B., Cao, J., “The application of elitist preserved genetic algorithms on fuzzy controller”, Proceedings of the 3rd World Congress on Intelligent Control and Automation, Vol. 1, pp. 590-592, 2000.
[33] Eberhart, R.C., Shi, Y., “Comparing inertia weights and constriction factors in particle swarm optimization”, Proceedings of the IEEE Conference on Evolutionary Computation, ICEC, Vol. 1, pp. 84-88, Jul. 2000.

簡易檢索 / 詳目顯示

相關論文