跳到主要內容

臺灣博碩士論文加值系統

(107.21.85.250) 您好!臺灣時間:2022/01/18 09:40
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果 :::

詳目顯示

我願授權國圖
: 
twitterline
研究生:吳明達
研究生(外文):Ming-Da Wu
論文名稱:複雜結構之演化:應用結構調適與多倍體於多狀態問題之研究
論文名稱(外文):Evolution of Complex Structures: Employing Structural Adaptation and Polyploidy in Solving Multi-State Problems
指導教授:孫春在孫春在引用關係
指導教授(外文):Chuen-Tsai Sun
學位類別:博士
校院名稱:國立交通大學
系所名稱:資訊科學系
學門:工程學門
學類:電資工程學類
論文種類:學術論文
論文出版年:2002
畢業學年度:90
語文別:英文
論文頁數:129
中文關鍵詞:演化式計算遺傳演算法多狀態問題動態策略模糊理論多倍體複雜結構
外文關鍵詞:evolutionary computationgenetic algorithmsmulti-state problemdynamic strategyfuzzypoly[loidycomplex structures
相關次數:
  • 被引用被引用:0
  • 點閱點閱:121
  • 評分評分:
  • 下載下載:0
  • 收藏至我的研究室書目清單書目收藏:0
自然界的演化是多樣與奇妙的。本篇研究著眼在由簡單到複雜與動態環境的兩個重要的演化現象。而遺傳演算法提供了一個簡化的演化平台,很適合應用於這些重要演化現象的模擬與探索。藉由簡單到複雜的過程,自然界的生物演化出了複雜的遺傳機制,例如適合在動態環境下生存的多倍體結構。本篇論文發展了一結構調適的模型,並將傳統的單倍體遺傳演算法延伸為多倍體。結構調適模型主要包含了結構的複雜化,結構的精簡化與結構的自我演化等概念。我們同時發展了結構延展、結構縮減與結構強制同型等遺傳運算來實現以上的概念。再者,我們也發展了兩個控制多倍體表現型的方法,控制基因與顯隱性函數。
本篇論文的目標是希望能夠加強傳統的遺傳演算法於解決具多狀態特性的動態問題上。在一個多狀態問題中,問題的最佳解會隨著問題的狀態而改變。例如投資問題,投資者往往會依據是市場目前的狀態,而使用不同的投資策略。自然界的多倍體提供了生物擁有兩組以上生存策略的能力,很適合應用多狀態問題。狀態與狀態之間的界限,有些是模糊而重疊的,有些則是明確的。針對這兩種類型,我們也發展了不同的機制來分別解決。
我們提供了三組實驗來測試所提出的多倍體與結構調適的模型。三組實驗分別為:多狀態的背包問題、多狀態的函數最佳化問題與模糊控制器的自動學習。實驗結果驗證了所提出的模型不僅可以有效的解決多狀態問題,也可已演化出合適的多倍體結構,兼具效能與效率上的優點。
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.
QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top
1. 15. 黃英忠、趙必孝(民83),「參與式領導與研究發展創新影響之研究」,人力資源學報,第21-33頁。
2. 65.鄭月遂,積極推動就業希望工程紓解失業壓力,中國勞工,第1014期,第88-93頁(2001)。
3. 64.鄭玉瑞,從國際性失業問題探討我國因應措施,勞工行政,第95期,第23-29頁(1996)。
4. 2.王麗容,婦女就業的障礙,勞工行政,第112期,第25-27頁(1997)。
5. 32.林文鵬,如何運用中、老人的人力,管理科學論述,第14頁(1989)。
6. 14. 黃同圳(民87),「人力資源管理策略化程度與組織績效關係探討」,輔仁管理評論,第五卷第一期,頁1-18。
7. 31.林祖嘉,台灣地區大專畢業生工資預期與失業期間關係之研究,臺灣銀行季刊,第43卷,第1期,第347-371頁(1992)。
8. 30.林荔華,專上畢業生在職尋職行為之探討,經濟論文叢刊,第16卷,第3期,第415-437頁(1988)。
9. 66.蔡宏明,產業結構變遷下的外勞政策,政策月刊,第52期,第43頁(1999)。
10. 12. 曾紀幸(民87),「產業別與國際化交易網路之關係-在台外商公司之實證研究」,國立屏東商專學報,第六期,頁15-33。
11. 72.藍科正,外勞大量引進有無促進失業,政策月刊,第52期,第25頁(1999)。
12. 63.鄭玉瑞,從外勞重新定義探討外勞問題,中國勞工,第1003期,第10頁(2000)。
13. 60.廖仁傑,台灣地區高齡就業之研究,勞工研究,第137期,第1-44頁(1999)。
14. 56.張晉芬,企業組織中升遷機會的決定及員工的期望:兼論內部勞動市場理論的應用,人文及社會科學集刊,中央研究院中山人文社會科學研究所,第6卷,第1期,第205-230頁(1994)。
15. 54.楊明仁、施春華、顏永杰,外籍勞工之適應困擾與心理健康,社區發展季刊,第75期,第193-202頁(1996)。