臺灣博碩士論文加值系統

自然界的演化是多樣與奇妙的。本篇研究著眼在由簡單到複雜與動態環境的兩個重要的演化現象。而遺傳演算法提供了一個簡化的演化平台，很適合應用於這些重要演化現象的模擬與探索。藉由簡單到複雜的過程，自然界的生物演化出了複雜的遺傳機制，例如適合在動態環境下生存的多倍體結構。本篇論文發展了一結構調適的模型，並將傳統的單倍體遺傳演算法延伸為多倍體。結構調適模型主要包含了結構的複雜化，結構的精簡化與結構的自我演化等概念。我們同時發展了結構延展、結構縮減與結構強制同型等遺傳運算來實現以上的概念。再者，我們也發展了兩個控制多倍體表現型的方法，控制基因與顯隱性函數。
本篇論文的目標是希望能夠加強傳統的遺傳演算法於解決具多狀態特性的動態問題上。在一個多狀態問題中，問題的最佳解會隨著問題的狀態而改變。例如投資問題，投資者往往會依據是市場目前的狀態，而使用不同的投資策略。自然界的多倍體提供了生物擁有兩組以上生存策略的能力，很適合應用多狀態問題。狀態與狀態之間的界限，有些是模糊而重疊的，有些則是明確的。針對這兩種類型，我們也發展了不同的機制來分別解決。
我們提供了三組實驗來測試所提出的多倍體與結構調適的模型。三組實驗分別為：多狀態的背包問題、多狀態的函數最佳化問題與模糊控制器的自動學習。實驗結果驗證了所提出的模型不僅可以有效的解決多狀態問題，也可已演化出合適的多倍體結構，兼具效能與效率上的優點。

Natural evolution, which guides organisms'' adaptation to the natural environment, is marvelous and fascinating. This study considers two important properties of natural evolution, a {\it simple-to-complex\/} process and a {\it dynamic environment\/}. Based on simple-to-complex evolution, natural organisms have developed complex chromosomal structures such as polyploids, which help them to survive in a dynamic environment. Genetic algorithms (GAs), which include several simple operators to simulate the process of biological adaptation, are feasible evolutionary platforms to explore these natural properties.
Many real world problems are hard to solve by artificial intelligence systems, because of their dynamic properties. In nature, polyploidy facilitates organisms'' having dynamic survival strategies. This fact motivates the extension of the haploid encoding used by conventional GAs to a complex form, {\it polyploid\/}, to solve dynamic strategy problems. The proposed method is expected to enable GAs to solve a special kind of dynamic strategy problems, {\it multi-state problems\/}, in which different problem solving strategies should be employed in different problem states. The dominance function can be represented in either a fuzzy or a crisp way according to the characteristics of the problem since the boundaries between states may be fuzzy in a multi-state problem. Two dominance mechanisms, including {\it regulator genes\/} and {\it dominance functions\/}, are proposed to control the phenotype of a polyploid.
In practice, genetic algorithms cannot easily obtain optimal solutions when the chromosome structure is too complex, because a complex structure, such as that of polyploid, always involves a large search space. This study proposes a {\it structural adaptation\/} model, which comprises the concepts of structural variation, simple-to-complex evolution, and selection, to overcome the difficulty of a large search space. In the structural adaptation model, a population of individuals with the simplest structure initially, progressively develops new survival strategies by structural variation, and the selection determines the appropriate polyploid structures. This study also presents three basic structural operations, {\it structural expansion, structural deletion\/}, and {\it structural coercion\/} to simulate random structural variation in nature.
A series of experiments, including solving non-stationary knapsack problems, optimizing multi-state Dejong functions, and modeling fuzzy systems, are presented to verify the polyploid and structural adaptation. The experimental results demonstrate that the proposed model can effectively solve multi-state problems, and find both the optimal solution and the optimal polyploid structure.

Abstract (in Chinese) i
Abstract (in English) ii
Contents iv
List of Figures viii
List of Tables xii
1 Introduction 1
1.1 Motivation: Evolution of Complex Structures 1
1.1.1 Simple to Complex Evolution 3
1.1.2 Structural Adaptation 4
1.2 Importance: Dynamic Strategy Applies in the Real World 5
1.3 Goal: Improving GA for Solving Multi-State Problems 6
1.3.1 Types of Multi-State Environments 8
1.4 Experiments 9
1.5 Organization 10
2 Relevant Literature 11
2.1 Fuzzy Modeling and Soft Computing 12
2.2 Integration of Fuzzy and Neural Networks 12
2.3 Integration of Fuzzy and Evolutionary Computation 13
2.4 Issues of Evolutionary Computation 18
2.4.1 Diversity 18
2.4.2 Polyploidy and Dominance 19
2.4.3 Structure Adaptation 21
3 Polyploidy 23
3.1 Regulator Gene 24
3.2 Dominance Function 29
3.2.1 Crisp Dominance 29
3.2.2 Fuzzy Dominance 30
3.3 Polyploidy Evolution Flow 33
3.4 Crossover and Mutation 35
3.5 Issues of Polyploidy Encoding 36
3.6 Property 39
4 Structural Adaptation 40
4.1 Atomic Operations 41
4.2 Crossover between Distinct Structures 45
4.3 Structural Variation 48
5 Experimental Results 54
5.1 Blind Non-stationary Knapsack Problems 55
5.1.1 Two State Environment 56
5.1.2 Two States with More Environmental Changes 67
5.1.3 Three State Environment 74
5.2 Multi-state Function Optimization Problem 80
5.2.1 Pure Polyploidy Model 82
5.2.2 Polyploidy Model with Structure Adaptation 84
5.2.3 Premature Expansion 88
5.2.4 Type 1 Expansion Being Better 90
5.2.5 Structure Successfully Evolving 91
5.3 Fuzzy Modeling 94
5.3.1 Mamdani Fuzzy Models 101
5.3.2 TSK Fuzzy Models (Sugeno fuzzy models) 109
6 Conclusions 113
6.1 Advantages 113
6.2 Limitations 116
6.3 Future Work 117
Bibliography 118

1. T. Back. Evolutionary Algorithms in Theory and Practice. Oxford Univ. Press, 19961.
2. T. Back. On the behavior of evolutionary algorithms in dynamic environments. In The 1998 IEEE International Conference on Evolutionary Computation Proceedings, pages 446--451, 1998.
3. T. Back, U. Hammel, and H. Schwefel. Evolutionary computation: comments on the history and current state. IEEE Transactions on Evolutionary Computation, 1(1):3--17, 1997.
4. T. Back and H. Schwefel. Evolutionary computation: an overview. In Proceedings of IEEE Conference on Evolutionary Computation, pages 20--29, 1996.
5. F. Bolata and A. Nowe. From fuzzy linguistic specifications to fuzzy controllers using evolution strategies. In Proc. 4th Int. Conf. on Fuzzy Systyems, pages 1089--1094, 1995.
6. J. J. Buckley and Y. Hayashi. Fuzzy neural networks: A survey. Fuzzy Sets and Systems, 66:1--13, 1994.
7. R. Calabretta, S. Nolfi, D. Parisi, and R. Galbiati. Diploid robots adapting to fast changing environments. In Proceedings of the 8th International Conference on Artificial Neural Networks, pages 1145--1150, 1998.
8. B. Carse, T. C. Fogarty, and A. Munro. Evolving fuzzy rule base controllers using genetic algorithms. Fuzzy Sets and Systems, 80:273--293, 1996.
9. C. Cercone and G. McCalla. Ten years of computational intelligence. Computational Intelligence, 10(4):i--vi, 1994.
10. U. K. Chakraborty and H. Muhlenbein. Linkage equilibrium and genetic algorithms. In IEEE International Conference on Evolutionary Computation, pages 25--29, 1997.
11. F. Cheong and R. Lai. Constraining the optimization of a fuzzy logic controller,. IEEE Transactions on Systems, Man, and Cybernetics, 30(1):31--46, 2000.
12. H. G. Cobb and J. J. Grefenstette. Genetic algorithms for tracking changing environments. In Proceedings of the Fifth International Conference on Genetic Algorithms, pages 523--530, 1993.
13. E. Collingwood, D. Corne, and P. Ross. Useful diversity via multiploidy. In Proceedings of IEEE International Conference on Evolutionary Computation, pages 810--813, 1996.
14. O. Cordon and F. Herrera. A general study on genetic fuzzy systems. In J. Periaux, G. Winter, Galan M, and P. Cuesta, editors, Genetic Algorithms in Engineering and Computer Science, pages 33--57. Wiley, 1995.
15. O. Cordon and F. Herrera. A two-stage evolutionary process for designing tsk fuzzy rule-based systems. IEEE Transactions on Systems, Man, and Cybernetics - Part B: Cybernetics, 29(6), 1999.
16. O. Cordon, F. Herrera, and M. Lozano. A classified review on the combination fuzzy logic-genetic algorithms bibliography: 1989-1995. In E. Sanchez, T. Shibata, and L. Zadeh, editors, Genetic Algorithms and Fuzzy Logic Systems. Soft Computing Perspectives, pages 209--241. World Scientific, 1997.
17. K. A. DeJong. An Analysis of the Behavior of a Class of Genetic Adaptive Systems. PhD thesis, University of Michigan, Ann Arbor, 1975.
18. I. Dumitrache and C. Buiu. Genetic learning of fuzzy controllers. Mathematics and Computer in Simulation, 49:13--26, 1999.
19. D. B. Fogel. Evolutionary Computation: Toward a New Philosophy of Machine Intelligence. IEEE Press, 1995.
20. D. B. Fogel. Evolutionary Computation: Toward a New Philosophy of Machine Intelligence. IEEE Press, 2000.
21. L. J. Fogel. Toward inductive inference automata. In Proceedings of the International Federation for Information Processing Congress, pages 395--400, 1962.
22. J. A. Freeman. Neural Networks. Addison Wesley, 1991.
23. D. E. Goldberg. Genetic Algorithms in Search, Optimization, and Machine Learning. Addison Wesley, 1989.
24. D. E. Goldberg. Genetic Algorithms in Search, Optimization, and Machine Learning. Addison Wesley, 1989.
25. D. E. Goldberg and R. E. Smith. Nonstationary function optimization using genetic dominance. In In Proceedings of the Second International Conference on Neural Networks, pages 59--68, 1987.
26. A. F. Gomez-Skarmeta and F. Jimenez. Fuzzy modeling with hybrid systems. Fuzzy Sets and Systems, 104:199--208, 1999.
27. A. Gonzalez and R. Perez. Structural learning of fuzzy rules from noised examples. In Proceedings of 1995 IEEE International Conference on Fuzzy Systems, pages 1323--1330, 1995.
28. B. Greene. Crossover and diploid dominance with deceptive fitness. In Proceedings of the 1999 Congress on Evolutionary Computation, pages 1369--1376, 1999.
29. F. Greene. A method for utilizing diploid/dominance in genetic search. In Proceedings of the 1999 Congress on Evolutionary Computation, pages 439--444, 1994.
30. M. M. Gupta and D.H. Rao. On the principles of fuzzy neural net-works. Fuzzy Sets and Systems, 61:1--18, 1994.
31. BS. Hadad and CF. Eick. Supporting polyploidy in genetic algorithms using dominance vectors. In Evolutionary Programming VI. 6th International Conference, pages 223--234, 1997.
32. Y. Hayashi, J. J. Buckley, and E. Czogala. Fuzzy neural network with fuzzy signals and weights. In Proc. Int. Joint Conf. Neural Networks, 1992.
33. F. Herrera, M. Lozano, and J. L. Verdegay. Tuning fuzzy logic controllers by genetic algorithms. International Journal of Approx. Reasoning, 12:299--315, 1995.
34. F. Herrera, M. Lozano, and J. L. Verdegay. A learning process for fuzzy control rules using genetic algorithms. Fuzzy Sets and Systems, 100:143--158, 1998.
35. J. H. Holland. Adaptive plans optimal for payoff-only environments. In Proceedings of the Second Hawaii International Conference on System Sciences, pages 917--920, 1969.
36. J. H. Holland. Adaptation in Natural and Artificial Systems. The University of Michigan Press, 1975.
37. J. H. Holland. Genetic algorithms and classifier systems: foundations and future directions. In Genetic Algorithms and their Applications: Proceedings of the Second International Conference on Genetic Algorithms, pages 82--89, 1987.
38. J. H. Holland and J. S. Reitman. Cognitive systems based on adaptive algorithms,. In Pattern-directed Inference Systems,. Academic Press, 1978.
39. R. B. Hollstien. Artificial Genetic Adaptation in Computer Control Systems. PhD thesis, University of Michigan, 1971.
40. A. Homaifar and E. Maccormick. Simultaneous design of membeship function and rule sets for fuzzy controllers using genetic algorithms. IEEE Transaction on Fuzzy System, 3:129--139, 1995.
41. Y. Ichikawa and Y.Ishii. Retaining diversity of genetic algorithms for multivariable optimization and neural network learning. In In Proceedings of the IEEE International Conference on Neural Networks, pages 1110--1114, 1993.
42. P. Isasi, A. Sanchis, J. Molina, and A. Berlanga. A computational model of evolution: haploidy versus diploidy. Computers and Artificial Intelligence, 18(6):575--94, 1999.
43. J.-S. R. Jang. Anfis: Adaptive network based fuzzy inference systems. IEEE Transactions on Systems, Man, and Cybernetics, 23(3):665--685, 1993.
44. J.-S. R. Jang, C. T. Sun, and E. Mizutani. Neuro-Fuzzy and Soft Computing: A Computational Approach to Learning and Machine Intelligence. Prentice Hall, 1997.
45. Y. H. Joo, H. S. Hwang, K. B. Kim, and K. B. Woo. Fuzzy system modeling by fuzzy partition and ga hybrid scheme. Fuzzy Sets and Systems, 86:279--288, 1997.
46. C. F. Juang, J. Y. Lin, and C. T. Lin. Genetic reinforcement learning through symbiotic evolution for fuzzy controller design. IEEE transactions on Systems, Man, and Cybernetics-Part B: Cybernetics, 30(2):290--302, 2000.
47. C. Karr. Genetic algorithms for fuzzy controllers. AI Expert, 6(2), 1991.
48. C. L. Karr and E. J. Gentry. Fuzzy control of ph using genetic algorithms. IEEE Transaction on Fuzzy Systems, 1:46--53, 1993.
49. K. Kiguchi, K. Watanabe, K. Izumi, and T. Fukuda. Application of multiple fuzzy-neuro force controllers in an unknown environment using genetic algorithms. In Proceedings of the 2000 IEEE International Conference on Robotics and Automation, pages 2106--2111, 2000.
50. B. Kosko. Neural networks and fuzzy systems: a dynamical systems approach. Prentice Hall, 1991.
51. J. R. Koza. Genetically breeding populations of computer programs to solve problems in artificial intelligence. In Proceedings of the 2nd International IEEE Conference on Tools for Artificial Intelligence, pages 6--9, 1990.
52. J. R. Koza. Genetic Programming: On the Programming of Computers by Means of Natural Selection. MIT Press, 1992.
53. J. R. Koza. Genetic Programming: Automatic Discovery of Reusable Programs. MIT Press, 1994.
54. T. Kuo and S.-Y. Hwang. A genetic algorithm with disruptive selection. In Proceedings of the Fifth International Conference onGenetic Algorithms, 1993.
55. J. E. Lansberry and L. Wozniak. Adaptive hydrogenerator governor tuning with a genetic algorithm. IEEE Transactions on Energy Conversion, 9(1):179--185, March 1994.
56. M. Lee and H. Takagi. Integrating design stages of fuzzy systems using genetic algorithms. In Proc. Second IEEE Inter. Conf. on Fuzzy System, pages 612--617, 1993.
57. C. T. Lin and C. P. Jou. Ga-based fuzzy reinforcement learning for control of a magnetic bearing system. IEEE Transactions on Systems, Man, Cybernetics, 30(2):276--289, 2000.
58. J. Liska and S. S. Melsheimer. Complete design of fuzzy logic systems using genetic algorithms. In Proc. Third IEEE International Conference on Fuzzy Systems, pages 1377--1382, 1994.
59. P. J. MacVicar-Whelan. Fuzzy sets for man-machine interactions. International Journal of Man-Machine Studies, 8:687--697, 1976.
60. E. H. Mamdani and S. Assilian. An experiment in linguistic systhesis with a fuzzy logic controller. International Journal of Man-Machine Studies, 7(1):1--13, 1975.
61. S. Massebeuf, C. Fonteix, LN. Kiss, I. Marc, and Pla F. Zaras K. Multicriteria optimization and decision engineering of an extrusion. In Proceedings of the 1999 Congress on Evolutionary Computation-CEC99, pages 14--21, 1999.
62. M. Mitchell. An Introduction to Genetic Algorithms. MIT Press, 1996.
63. S. Mitra and Y. Hayashi. Neuro-fuzzy rule generation: survey in soft computing framework. IEEE Transactions on Neural Networks, 11(3):748--768, 2000.
64. M. Mizumoto. Fuzzy controls under various approximate reasoning methods. In Proceedings 2nd IFSA Congress, pages 143--146, 1987.
65. D. E. Moriarty and R. Mikkilainen. Efficient reinforcement learning through symbiotic evolution. Machine Learning, 22:11--32, 1996.
66. D. Nauck, F. Klawonn, and R. Kruse. Foundations of Neuro-Fuzzy Systems. Wiley, 1997.
67. D. Park, A. Kandel, and G. Langholz. Genetic-based new fuzzy reasoning models with application to fuzzy control. IEEE Transaction on Systems, Man, and Cybernetics, 24:39--47, 1994.
68. A. Parodi and P. Bonelli. A new approach of fuzzy classifier systems. In Proc. Fifth International Conference on Genetic Algorithms, pages 223--230, 1993.
69. W. Pedrycz. Genetic algorithms for learning in fuzzy relational structures. Fuzzy Sets and Systems, 69:37--52, 1995.
70. D. Poole, A. Mackworth, and R. Goebel. Computational Intelligence: A Logical Approach. Oxford University Press, 1998.
71. I. Rechenberg. Evolutionsstrategie: Optimierung technischer System nach Prinzipien der biologischen Evolution. Frommann-Holzboog, 1973.
72. C. Ryan, G. Moghadampour, and P. Tormanen. Diploidy without dominance means of genetic algorithms-case: frequency controller. In Proceedings of the Third Nordic Workshop on Genetic Algorithms and their Applications (3NWGA), pages 63--70, 1997.
73. R. J. Schalkoff. Artificial Neural Networks. McGraw-Hill, 1997.
74. H.-P Schwefel. Evolutionsstrategie und numerische optimierung. PhD thesis, Technische Universit at Berlin, Germany, May 1975.
75. R. E. Smith and D. E. Goldberg. Diploidy and dominance in artificial genetic search. Complex Systems, 6:251--285, 1992.
76. R. E. Smith and D. E. Goldberg. Diploidy and dominance in artificial genetic search. Complex Systems, 6:251--285, 1992.
77. S. F. Smith. A learning system based on genetic adaptive algorithms. PhD thesis, University of Pittsburgh, 1980.
78. R. J. Streifel, R. J. Marks II, R. Reed, J. J. Choi, and M. Healy. Dynamic fuzzy control of genetic algorithm parameter coding. IEEE Transactions on Systems, Man, and Cybernetic-Part B: Cybernetics, 29(3):426--433, 1999.
79. M. Sugeno and G. T. Kang. Structure identification of fuzzy model. Fuzzy Sets and Systems, 28:15--13, 1988.
80. T. Takagi and M. Sugeno. Fuzzy identification of systems and its applications to modeling and control. IEEE Transactions on System, Man and Cybernetics, 15:116--132, 1985.
81. P. Thrift. Fuzzy logic synthesis with genetic algorithms. In Proc. 4th Int. Conf. Genetic Algorithms, pages 509--513, 1991.
82. M. Valenzuela-Rendon. The fuzzy classifier system: a classifier system to continuously varying variable. In Proc. Forth International Conference on Genetic Algorithms, pages 346--353, 1991.
83. R. R. Yager and D. P. Filev. Essentials of Fuzzy Modeling and Control. Wiley, 1994.
84. L. A. Zadeh. Fuzzy sets. Information and Control, 8:338--353, 1965.
85. L. A. Zadeh. Soft computing and fuzzy logic. IEEE Software, 11(6):48--56, 1994.