臺灣博碩士論文加值系統

遺傳演算法（evolution algorithm）已被廣泛地運用在處理最適化問題（optimization），應用的領域涵蓋：數學、工程、生化(bio-chemistry)、分子模擬(molecular simulation)、…等各式問題。尤其，在處理高維度的全域最適化（global optimization）問題上，遺傳演算法相較於傳統以梯度運算為基礎的數值方法（gradient based），更能避免搜尋過程中，侷限於區域解（local optima）、方程式微分及猜測初始值（initial value）的困擾。多族群（multi-population）遺傳演算法的發展，更進一步地提高了遺傳演算法在搜索解空間的過程中，搜尋到全域最適解（global optima）的機率。然而，無論是傳統的單族群（single population）遺傳演算法或多族群的遺傳演算法，在處理全域最適化問題時，仍然有機會面臨可能的早熟問題（probable premature convergence problem）。

本文的目的在於處理遺傳演算法演算過程中，面臨可能的早熟問題時，經由在演算過程中加入可用於偵測早熟的機制，在發現可能的早熟狀況時，進一步透過訊息理論(information theory)，計算搜尋過程中，已搜尋過的資料點在解空間（solution space）中分布情形，並提供一個引導的機制，以有效地處理遺傳演算法在演算過程中，可能面臨的早熟問題。

文中並嘗試處理幾個經常用於測試演算法效率上，高維度的測試問題，並模擬處理多成份蒸餾塔之成份參數預測、線性系統識別(linear system identification)及代謝網路（metabolic network）之最適化問題，用以討論經由訊息理論導引遺傳演算法引導突變(mutation)操作的可行性。

Evolutionary algorithm (EA) has become popular in global optimization with applications widely used in many industrial areas. However, there exists probable premature convergence problem when rugged contour situation is encountered. As to the original genetic algorithm (GA), no matter single population or multi-population cases, the ways to prevent the problem of probable premature convergence are to implement various selection methods, penalty functions and mutation approaches. This work proposes a novel approach to perform very efficient mutation to prevent from premature convergence by introducing the concept of information theory. Information guided mutation is implemented to several variables, which are selected based on the information entropy derived in this work. The areas of search are also determined on the basis of the information amount obtained from previous searches.

Several benchmark problems are solved to show the superiority of this information guided EA. An industrial scale problem is also presented in this work.

摘要 ii
謝誌 iii
目 錄 iv
圖目錄 vi
表目錄 viii
第一章 簡介 1
1.1 研究目的 1
1.2 遺傳演算法之發展 2
1.3 訊息理論之發展 3
1.3.1 訊息理論結合遺傳演算法在最適化問題上之應用 4
第二章 遺傳演算法 10
2.1 簡介 10
2.1.1 編碼及解碼 10
2.1.2 目標函式與適應值 10
2.1.3 選擇及複製 11
2.1.4 交配 12
2.1.5 突變 13
2.2 多族群之遺傳演算法 15
第三章 訊息理論導引之遺傳演算法 17
3.1 簡介 17
3.2 訊息理論 18
3.3 連續變數之離散化 19
3.4 直交設計 22
3.5 早熟偵測機制 24
3.6 選取待突變之變數 25
3.7 引導變數之突變區域 26
第四章 無限制條件之最適化問題 31
4.1 標竿測試問題 31
4.1.1 Giewank’s function 32
4.1.2 Ackley’s function 35
4.1.3 Generalized Schwefel’s function 37
4.2 參數預測問題 43
4.2.1 多成份蒸餾塔之成份預測 43
4.2.2 線性系統識別 52
第五章 有限制條件之最適化問題 55
5.1 簡介 55
5.2 懲罰函數 56
5.3 混合整數之非線性規劃問題（MIXED INTEGER NONLINEAR PROGRAMMING - MINLP） 57
5.3.1 代謝網路之最適化問題(Metabolic Optimization of Regulatory Network) 57
第六章 聚類分析（Clustering Analysis） 63
6.1 簡介 63
6.2 聚類分析於代謝網路上之應用 65
第七章 結論 72
參考文獻 73

1. Adeli, H. and Cheng, N. T. (1994), Augmented lagrangian genetic algorithm for structural optimization, Journal of Aerospace Engineering, 7, 104-118.
2. Alavi, S. and Thompson, D. L. (2004), A molecular-dynamics study of structural and physical properties of nitromethane nanoparticles, Journal of Chemical Physics, 120, 10231-10239.
3. Baker, J. E. (1985), Adaptive selection methods for genetic algorithms, Proceeding of International Conference on Genetic Algorithms, 1, 101-111.
4. Barbosa, H. J. C., Lemonge A. C. C. (2003), A new adaptive penalty scheme for genetic algorithms , Information Sciences, 136, 215..
5. Battiti, R (1996), Reactive search: toward self-tuning heuristics, In V. J. Rayward-Smith, editor, Modern Heuristic Search Mehods, Jjohn Wiley and Sons .
6. Bursulaya, B. D., Totrov, M., Abagyan, R. and Brooks, C. L. (2003), Comparative study of several algorithms for flexible ligand docking, Journal of Computer-Aided Molecular Design, 17, 755-763.
7. Chen, J. H., Wong, S. H., and Jang, S. S. (1998), Product and process development using artificial neural-network model and information analysis, AIChE Journal, 44, 876-887.
8. Chen, S. L. and Huang, C. (2001), Optimal approximation of linear systems by a differential evolution algorithm, IEEE Trans. Syst., man Cy. A, 21, 698-707.
9. Chipperfield, A. J., Fleming, P. J., Pohlheim H. and Fonseca, C. M. (1994), Genetic Algorithm Toolbox User's Guide, ACSE Research Report No. 512, University of Sheffield, Sheffield, pp. 6-25.
10. Coello, C. A. C. (2000), Use of a self-adaptive penalty approach for engineering optimization problems, Computers in Industry, 41,113-127.
11. Deb, K. (1996), An Efficient constraint handling method for genetic algorithms, Computer Methods in Applied Mechanics and Engineering, 186, 311-338.
12. Deb, K. (2001), Multi-Objective Optimization using Evolutionary Algorithms, Jon Wiley & Sons, Chichester.
13. Floudas, C. A. and Pardalos, P. M. (1990), A collection of test problems for constrained global optimization algorithm, Lecture Note in Computer Science 455, Springer, Berlin, Heidlberg, New York.
14. Floudas, C. A. and Pardalos, P. M. (2000), Optimization in Computational Chemistry and Molecular Biology: Local and Global Approaches, Kluwer Academic Publishers, Boston.
15. Gen, M. and Cheng, R. (1996), A survey of penalty techniques in genetic algorithms, Proceedings of the 1996 International Conference on Evolutionary Computation, IEEE, 804-809.
16. Gen, M. and Cheng, R. (2000), Genetic Algorithms & Engineering Optimization, John Wiley & Sons, New York.
17. Goldberg, D. E. (1989), Genetic algorithms in search optimization, and Machine learning, Addison-Wesley: Reading, M. A.
18. Grossmann I. E., Sargent, W. H. (1979), Optimum design of multipurpose chemical plants, Industrial Engineering Chemistry Process Des. Dev., 18, 343-348.
19. Hatzimanikatis, V, Floudas C. A., Bailey J. E. (1006), Optimization of regulatory architectures in metabolic reaction networks, Biotechnology an Bioengineering, 52, 485-500.
20. Holland J. H. (1975), Adaptation in natural and artificial systems: an introductory analysis with applications to biology, control, and artificial intelligence. Ann Arbor: University of Michigan Press. Viii, 183p.
21. Homaifar, A., Lai, S. H. Y. and Qi, X. (1994), Constrained optimization via genetic algorithms, Simulation, 62, 242-254.
22. Joines, J. and Houck, C. (1994), On the use of non-stationary penalty functions to solve non-linear constrained optimization problems with Gas, Proceedings of the First IEEE International Conference on Evolutionary Computation, IEEE Press, 579-384.
23. Katare, S., Caruthers, J. M., Delgass, W. N. and Venkatasubramanian, V. (2004), An intelligent system for reaction kinetic modeling and catalyst design, Industrial & Engineering Chemistry Research, 43, 3484-3512.
24. Klepeis, J. L. and Floudas,C. A. (2003), Ab initio tertiary structure prediction of proteins, Journal of Global Optimization, 25, 113-114.
25. Koziel, S. and Michalewicz Z. (1999), Evolutionary algorithms, homomorphous mapping and constrained parameter optimization, Evolutionary Computation, 7, 19-44.
26. Leung , Y. W. and Wang,Y. (2001), An orthogonal genetic algorithm with quantization for global numerical optimization, IEEE Transactions on Evolutionary Computation, 5, 41-53.
27. Luyben, W. L. (1990), Process Modeling, Simulation and Control for Chemical Engineers, McGraw –Hill, New York.
28. Maria, G. (2004), A review of algorithms an trends in kinetic model identification for chemical and biochemical systems, Chem. Biochem. Eng. Q., 18, 195-222.
29. Metropolis, N., Rosenbluth, A., Rosenbluth, M., Teller, A.and Teller, E. (1953), Equation of state calculations by fast computing machines, Journal of Chemical Physics, 21, 1087-1092.
30. Michalewicz, Z. and Attia, N. (1994), Evolutionary optimization of constrained problems, Procedings of the Third Annual Conference on Evolutionary Programming, World Sientific, 98-108.
31. Michalewicz, Z. and Janikow, C. Z. (1993), Handling constraints in genetic algorithms, Proceedings of the Fourth International Conference on Genetic Algorithms, Morgan Kaufmann, 151-157.
32. Michalewicz, Z. and Nazhiyath, G. (1995), GENOCOP III: A co-evolutionary algorithm for numerical optimization problems with nonlinear constraints, Proceedings of the Second IEEE International Conference on Evolutionary Computation, IEEE Press, 647-651.
33. Mockus, J. (1994), Application of Bayesian approach to numerical methods of global and stochastic optimization, Journal of Global Optimization, 4, 347-356.
34. Morris, G. M., Goodsell, D. S., Halliday, R. S., Huey, R., Hart, W. E., Belew, R. K. and Olson, A. J. (1998), Automated Docking Using a Lamarckian Genetic Algorithm and and Empirical Binding Free Energy Function, Journal Computational Chemistry, 19, 1639-1662.
35. Mühlenbein, H., Schomisch, M. and Born, J. (1991), The parallel genetic algorithm as a function optimizer, Parallel Computing, 17, 619-632.
36. Ong ,Y. S. and Keane, A. J. (2004), Meta-Lamarckian learning in memetic algorithms, IEEE Transactions on Evolutionary Computation, 8, 99-110.
37. Savageau M. A. (1969), Biochemical systems analysis.1. Some mathematical properties of rate law for component enzymatic reactions, Journal of Theoretical Biology, 25, 365-369.
38. Schoenauer, M. and Michalewicz, Z. (1996), Evolutionary computation at the edge of feasiblility, Proceedings of the Fourth International Conference on Parallel Problem Solving from Nature, Springer Verlag, 22-27.
39. Schouenauer, M. and Xanthakis, S. (1993), Constrained GA optimization, Proceedings of the Fifth International Conference on Genetic Algorithms, Morgan Kaufmann, 473-580.
40. Shannon, C. E., A Mathematical Theory of Communication (1948), Bell Syst. Tech. Journal, 27, 379-423, 623-657.
41. Siarry, P., Berthiau, G., Durbin, F. and Haussy, J. (1997), Enhanced simulated annealing for globally minimizing functions of many-continuous variables, ACM Transactions on Mathematical Software, 23, 209-228.
42. Tomassini, M., Vanneschi, L., Fernandez, F. and Galeano G. (2003), Diversity in multipopulation genetic programming, In: Genetic And Evolutionary Computation - GECCO 2003, PT II, Proceedings Lecture Notes In Computer Science 2724, pp. 1812-1813.
43. Tomassini, M., Vanneschi, L., Fernandez, F. and Galeano, G. (2004), A study of diversity in multipopulation genetic programming, Artificial Evolution Lecture Notes In Computer Science, 2936, 243-255.
44. Tsujimura, Y., and Gen, M. (1998), Entropy-based genetic algorithm for solving TSP, In: Second international Conference on Knowledge-Based Intelligent Electronic Systems, pp. 21-23.
45. Voit E. O. (1992), Optimization in Integrated Biochemical Systems, Biotechnology and Bioengineering, 40, 572-582.
46. Wang, K. F., Qian, Y., Yuan, Y. and Yao, P. J. (1998), Synthesis and optimization of heat integrated distillation systems using an improved genetic algorithm, Computers & Chemical Engineering, 23, 125-136.
47. Wright, A. H. (1991), Genetic algorithms for real parameter optimization. In: G. J. E. Rawlins (eds.), Foundations of Genetic Algorithms, p.p. 205—218.
48. Yen, J., Liao, J. C., Lee, B. J. and Randolph, D. (1998), A hybrid approach to modeling metabolic systems using a genetic algorithm and simplex method, IEEE Transactions on Systems Man and Cybernetics Part B-Cybernetics, 28, 173-191.
49. Zhong, W. C., Liu, J., Xue, M. and Jiao, L. C. (2004), A multiagent genetic algorithm for global numerical optimization, IEEE Transactions on Systems, Man and Cybernetics-Part B, 34, 1128-1141.
50. Yeniay, O. and Beytepe, A. (2005), Penalty function methods for constrained optimization with genetic algorithms, Mathematical and Computational Applications, 10, 45-56.