請用此 Handle URI 來引用此文件：
http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/42801完整後設資料紀錄
| DC 欄位 | 值 | 語言 |
|---|---|---|
| dc.contributor.advisor | 于天立(Tian-Li Yu) | |
| dc.contributor.author | Wei-Kai Lin | en |
| dc.contributor.author | 林偉楷 | zh_TW |
| dc.date.accessioned | 2021-06-15T01:23:59Z | - |
| dc.date.available | 2009-07-29 | |
| dc.date.copyright | 2009-07-29 | |
| dc.date.issued | 2009 | |
| dc.date.submitted | 2009-07-23 | |
| dc.identifier.citation | [1] P. J. Angeline and J. B. Pollack. Competitive environments evolve better solutions
for complex tasks. In Proceedings of the 5th International Conference on Genetic Algorithms, pages 264–270, San Francisco, CA, USA, 1993. Morgan Kaufmann Publishers Inc. [2] P. J. Angeline and J. B. Pollack. Coevolving high-level representations. In C. Langton, editor, Artificial Life III, pages 55–71, Reading MA, 1994. Addison- Wesley. [3] R. Axelrod. The evolution of strategies in the iterated prisoner’s dilemma. In Genetic algorithms and simulated annealing. L. Davis editor, Morgan Kaufman, 1987. [4] R. Axelrod and W. D. Hamilton. The evolution of cooperation. Science, 211(4489):1390–1396, 1981. [5] Y. Azaria and M. Sipper. Gp-gammon: Genetically programming backgammon players. Genetic Programming and Evolvable Machines, 6(3):283–300, September 2005. [6] Y. Azaria and M. Sipper. Gp-gammon: Using genetic programming to evolve backgammon players. In M. Keijzer, A. Tettamanzi, P. Collet, J. I. van Hemert, and M. Tomassini, editors, Proceedings of the 8th European Conference on Genetic Programming, volume 3447 of Lecture Notes in Computer Science, pages 132–142, Lausanne, Switzerland, 30 Mar. - 1 Apr. 2005. Springer. [7] H.-G. Beyer and H.-P. Schwefel. Evolution strategies –a comprehensive introduction. Natural Computing: an international journal, 1(1):3–52, 2002. [8] A. Bhatt, P. Varshney, and K. Deb. In search of no-loss strategies for the game of tic-tac-toe using a customized genetic algorithm. In GECCO ’08: Proceedings of the 10th annual conference on Genetic and evolutionary computation, pages 889–896, New York, NY, USA, 2008. ACM. [9] A. Bucci and J. B. Pollack. Order-theoretic analysis of coevolution problems: Coevolutionary statics. In Proceedings of the GECCO-2002 Workshop on Coevolution: Understanding Coevolution, pages 229–235, 2002. [10] K. Chellapilla and D. Fogel. Evolving neural networks to play checkers without relying on expert knowledge. Neural Networks, IEEE Transactions on, 10(6):1382–1391, Nov 1999. [11] K. Chellapilla and D. B. Fogel. Review of efforts to evolve strategies to play checkers as well as human experts. In B. Bosacchi, D. B. Fogel, and J. C. Bezdek, editors, Society of Photo-Optical Instrumentation Engineers (SPIE) Conference Series, volume 4120 of Presented at the Society of Photo-Optical Instrumentation Engineers (SPIE) Conference, pages 43–51, Oct. 2000. [12] J. P. Cohoon, S. U. Hegde, W. N. Martin, and D. Richards. Punctuated equilibria: a parallel genetic algorithm. In Proceedings of the Second International Conference on Genetic Algorithms on Genetic algorithms and their application, pages 148–154, Hillsdale, NJ, USA, 1987. L. Erlbaum Associates Inc. [13] Y. Davidor. A naturally occurring niche and species phenomenon: The model and first results. In ICGA, pages 257–263, 1991. [14] E. D. de Jong and J. B. Pollack. Ideal evaluation from coevolution. Evolutionary Computation, 12(2):159–192, June 2004. [15] E. D. de Jong, K. O. Stanley, and R. P. Wiegand. Introductory tutorial on coevolution. In GECCO ’07: Proceedings of the 2007 GECCO conference companion on Genetic and evolutionary computation, pages 3133–3157, New York, NY, USA, 2007. ACM. [16] K. A. De Jong. An analysis of the behavior of a class of genetic adaptive systems. PhD thesis, University of Michigan, Ann Arbor, MI, USA, 1975. [17] K. A. De Jong. Evolutionary computation: a unified approach. MIT Press, 2006. [18] K. Deb and D. E. Goldberg. Analyzing deception in trap functions, illigal report no. 91009. Technical report, University of Illinois at Urbana-Chmapaign, Illinois Genetic Algorithms Laboratory, Urbana, IL, 1991. [19] D. Dumitrescu, B. Lazzerini, L. C. Jain, and A. Dumitrescu. Evolutionary computation. CRC Press, Inc., Boca Raton, FL, USA, 2000. [20] P. K. Dutta. Strategies and games: theory and practice. MIT Press, 1999. [21] N. Eldredge and S. J. Gould. Models in Paleobiology: Punctuated Equilibria: An Alternative to Phyletic Gradualism, chapter 5, pages 82–115. Freeman, Cooper and Co, 1972. [22] V. Feldman. Evolvability from learning algorithms. In STOC ’08: Proceedings of the 40th annual ACM symposium on Theory of computing, pages 619–628, New York, NY, USA, 2008. ACM. [23] S. Ficici, O. Melnik, and J. Pollack. A game-theoretic and dynamical-systems analysis of selection methods in coevolution. Evolutionary Computation, IEEE Transactions on, 9(6):580–602, December 2005. [24] S. G. Ficici and J. B. Pollack. Game theory and the simple coevolutionary algorithm: Some preliminary results on fitness sharing. In R. K. Belew and H. Juill`e, editors, GECCO 2001 Workshop on Coevolution: Turning Adaptive Algorithms upon Themselves, pages 2–7, San Francisco, California, USA, 7 2001. [25] D. E. Goldberg. Genetic Algorithms in Search, Optimization and Machine Learning. Addison-Wesley Longman Publishing Co., Inc., Boston, MA, USA, 1989. [26] D. E. Goldberg and J. Richardson. Genetic algorithms with sharing for multimodal function optimization. In Proceedings of the Second International Conference on Genetic Algorithms on Genetic algorithms and their application, pages 41–49, Hillsdale, NJ, USA, 1987. L. Erlbaum Associates Inc. [27] P. B. Grosso. Computer simulations of genetic adaptation: parallel subcomponent interaction in a multilocus model. PhD thesis, University of Michigan, Ann Arbor, MI, USA, 1985. [28] O. Hammami, K. Kuroda, Q. Zhao, and K. Saito. Coevolvable hardware platform for automatic hardware design of neural networks. Industrial Technology 2000. Proceedings of IEEE International Conference on, 1:509–514 vol.2, Jan. 2000. [29] G. R. Harik. Finding multimodal solutions using restricted tournament selection. In Proceedings of the 6th International Conference on Genetic Algorithms, pages 24–31, San Francisco, CA, USA, 1995. Morgan Kaufmann Publishers Inc. [30] J. H. Holland. Adaptation in natural and artificial systems. MIT Press, Cambridge, MA, USA, 1992. [31] E. Kita, T. Tamaki, and H. Tanie. Structural design using genetic algorithm. In IUTAM Symposium on Evolutionary Methods in Mechanics, pages 163–172, 2004. [32] J. R. Koza. Genetic Programming: On the Programming of Computers by Means of Natural Selection. MIT Press, 1992. [33] S. W. Mahfoud. Niching methods for genetic algorithms. PhD thesis, University of Illinois at Urbana-Champaign, Champaign, IL, USA, 1995. [34] B. L. Miller, , and D. E. Goldberg. Genetic algorithms, tournament selection, and the effects of noise. Complex Systems, 9:193–212, 1995. [35] J. Nash. Non-cooperative games. The Annals of Mathematics, 54(2):286–295, September 1951. [36] C. K. Oei, D. E. Goldberg, and S. Chang. Tournament selection, niching, and the preservation of diversity. Technical report, Univ. of Illinois, Urbana, Illinois Genetic Algorithms Laboratory, Tech. rep. 91011, 1991. Cite by Sareni 1998. [37] C. Ong, H. Quek, K. Tan, and A. Tay. Discovering chinese chess strategies through coevolutionary approaches. Computational Intelligence and Games, 2007. CIG 2007. IEEE Symposium on, pages 360–367, April 2007. [38] M. Pelikan and D. E. Goldberg. Escaping hierarchical traps with competent genetic algorithms. In Proceedings of the Genetic and Evolutionary Computation Conference (GECCO2001), pages 511–518. Morgan Kaufmann, 2001. [39] J. B. Pollack and A. D. Blair. Co-evolution in the successful learning of backgammon strategy. Machine Learning, 32(3):225–240, September 1998. [40] J. B. Pollack, A. D. Blair, and M. Land. Coevolution of a backgammon player. In Proceedings Artificial Life V, pages 92–98. MIT Press, 1996. [41] M. A. Potter and K. A. De Jong. A cooperative coevolutionary approach to function optimization. In PPSN III: Proceedings of the International Conference on Evolutionary Computation. The Third Conference on Parallel Problem Solving from Nature, pages 249–257, London, UK, 1994. Springer-Verlag. [42] M. A. Potter and K. A. De Jong. Cooperative coevolution: An architecture for evolving coadapted subcomponents. Evol. Comput., 8(1):1–29, 2000. [43] I. Rechenberg. Case studies in evolutionary experimentation and computation. Computer Methods in Applied Mechanics and Engineering, 186(2-4):125 – 140, 2000. [44] C. W. Reynolds. Competition, coevolution and the game of tag. In R. A. Brooks and P. Maes, editors, Proceedings of the Fourth International Workshop on the Synthesis and Simulation of Living Systems, pages 59–69, MIT, Cambridge, MA, USA, 6-8 July 1994. MIT Press. [45] C. D. Rosin and R. K. Belew. New methods for competitive coevolution. Evol. Comput., 5(1):1–29, 1997. [46] S. Russell and P. Norvig. Artificial Intelligence: A Modern Approach. Prentice Hall, 2 edition, 2003. [47] A. L. Samuel. Some studies in machine learning using the game of checkers. IBM Journal, 3:211–229, 1959. [48] A. L. Samuel. Some studies in machine learning using the game of checkers. ii—recent progress. IBM Journal of Research and Development, 11:601–617, 1967. [49] C. Savage. A survey of combinatorial gray codes. SIAM Rev., 39(4):605–629, 1997. [50] C. E. Shannon. Programming a computer for playing chess. Philosophical Magazine, 41:256–275, 1950. [51] G. Sywerda. Uniform crossover in genetic algorithms. In Proceedings of the third international conference on Genetic algorithms, pages 2–9, San Francisco, CA, USA, 1989. Morgan Kaufmann Publishers Inc. [52] G. Tesauro. Practical issues in temporal difference learning. Mach. Learn., 8(3-4):257–277, 1992. [53] G. Tesauro. Temporal difference learning and td-gammon. Commun. ACM, 38(3):58–68, 1995. [54] L. G. Valiant. Evolvability. Electronic Colloquium on Computational Complexity (ECCC), 6(120), 2006. [55] L. G. Valiant. Evolvability. In Proceedings of 32nd International Symposium on Mathematical Foundations of Computer Science, pages 22–43, 2007. [56] J. von Neumann and O. Morgenstern. Theory of Games and Economic Behavior. Princeton University Press, 1944. [57] R. A. Watson and J. B. Pollack. Coevolutionary dynamics in a minimal substrate. In Proceedings of the Genetic and Evolutionary Computation Conference, GECCO-2001, pages 702–709. Morgan Kaufmann, 2001. [58] S. Wright. Evolution and the Genetics of Populations: A Treatise. University of Chicago Press, 1968. [59] A. Yang, Y. Shan, and L. T. Bui. Success in Evolutionary Computation. Springer Berlin / Heidelberg, 2008. [60] K. Y. Yip, P. Patel, P. M. Kim, D. M. Engelman, D. McDermott, and M. Gerstein. An integrated system for studying residue coevolution in proteins. Bioinformatics, 24(2):290–292, 2008. [61] T. Yu, L. Davis, C. Baydar, and R. Roy. Evolutionary Computation in Practice. Springer Berlin / Heidelberg, 2008. [62] T.-L. Yu and W.-K. Lin. Optimal sampling of genetic algorithms on polynomial regression. In GECCO ’08: Proceedings of the 10th annual conference on Genetic and evolutionary computation, pages 1089–1096, New York, NY, USA, 2008. ACM. | |
| dc.identifier.uri | http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/42801 | - |
| dc.description.abstract | 這篇論文探討共同演化的基因演算法用於演化賽局策略的能力。更確切的說，這篇論文的討論限定在雙人、零和且對稱的賽局。在這樣的前提下，單純策略和混合策略被分開討論。要共同演化出一個混合策略的納許均衡是具有挑戰性的，因為均衡的策略不能獲得比其他策略更高的得益期望值。這個論點在剪刀、石頭、布的實驗中被驗證，因為所有的混合策略產生的得益期望值一樣，使得共同演化無法收斂到納許均衡。另一方面，在一些賽局中，單純策略是較容易共同演化的，尤其是族群之多樣性被特別保持的時候。實驗上，使用維持生態位的技巧，例如限制競爭式選擇法、確定性擁擠法，對於共同演化都有明顯的助益。更進一步，內文也展示了在共同演化中，族群大小和評估個體時最佳的對手數量之間，權衡折中的關係。在論文的最後，實驗上示範了一個賽局遊戲，相對於棋盤需要指數大小的族群才能演化，也就是仍存在對共同演化來說較困難的賽局。在這樣的賽局中，需要在族群中維持指數的對手來演化出最佳的策略。 | zh_TW |
| dc.description.abstract | This thesis investigates the ability of coevolutionary genetic algorithms to evolve game-playing strategies. Specifically, it focuses on two-player, zero-sum and symmetric games with both pure and mixed strategies. Pure and mixed strategies are discussed separately. Co-evolving the mixed strategy Nash equilibrium is challenging since the Nash strategy does not yield a higher payoff than other strategies. This argument is verified on the game of rock-paper-scissor, where all mixed strategies yield the same expected payoff and fail to converge to the Nash quilibrium. On the other hand, pure strategies are more co-evolvable with some games especially when the diversity is maintained in the population. Empirically, adopting niching
techniques such as restricted tournament selection and deterministic crowding helps coevolution. Furthermore, this work empirically shows the trade-off between the population size and the optimal number of opponents used to evaluate an individual. Finally, this thesis demonstrates the existence of game strategies that require an exponentially large population with respect to the size of the game. In such games, exponentially many opponents need to be maintained to evolve an optimal strategy. | en |
| dc.description.provenance | Made available in DSpace on 2021-06-15T01:23:59Z (GMT). No. of bitstreams: 1 ntu-98-R96921073-1.pdf: 997921 bytes, checksum: 65b4d843af50e6c2a0968cfab5b0df64 (MD5) Previous issue date: 2009 | en |
| dc.description.tableofcontents | Acknowledgments i
中文摘要ii Abstract iii Contents iv List of Figures vi List of Algorithms viii 1 Introduction 1 2 Background of Game Theory 3 2.1 The Normal-Form Game . . . . . . . . . . . . . . . . . . . . . . . . . 3 2.2 Pure Strategies and Mixed Strategies . . . . . . . . . . . . . . . . . . 4 2.3 Nash Equilibrium . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 2.4 Two-Player, Symmetric, Zero-Sum and Turn-Based Games . . . . . . 5 3 Background of Genetic Algorithms and Coevolutionary Algorithms 7 3.1 Simple Genetic Algorithms . . . . . . . . . . . . . . . . . . . . . . . . 7 3.2 Niching Techniques . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 3.3 Coevolutionary Algorithms . . . . . . . . . . . . . . . . . . . . . . . . 16 4 Mixed Strategy Games, Less Co-Evolvable 19 4.1 Theoretical Approach . . . . . . . . . . . . . . . . . . . . . . . . . . . 19 4.2 Empirical Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21 5 Pure Strategy Games, More Co-Evolvable 23 5.1 Testing Games . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24 5.2 Coevolutionary Genetic Algorithm with Niching . . . . . . . . . . . . 26 5.3 Enhancing Efficiency via Sampling . . . . . . . . . . . . . . . . . . . 40 6 A Less Co-Evolvable Pure Strategy Game 43 6.1 Bit-Flipping Game . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44 7 Conclusions 47 Bibliography 49 | |
| dc.language.iso | en | |
| dc.subject | 最佳取樣 | zh_TW |
| dc.subject | 基因演算法 | zh_TW |
| dc.subject | 共同演化 | zh_TW |
| dc.subject | 賽局理論 | zh_TW |
| dc.subject | 生態位技巧 | zh_TW |
| dc.subject | game theory | en |
| dc.subject | optimal sampling | en |
| dc.subject | niching techniques | en |
| dc.subject | genetic algorithm | en |
| dc.subject | coevolution | en |
| dc.title | 共同演化的基因演算法應用於賽局的共同演化能力 | zh_TW |
| dc.title | Co-Evolvability of Games in Coevolutionary Genetic Algorithms | en |
| dc.type | Thesis | |
| dc.date.schoolyear | 97-2 | |
| dc.description.degree | 碩士 | |
| dc.contributor.oralexamcommittee | 張時中(Shi-Chung Chang),陳穎平(Ying-Ping Chen) | |
| dc.subject.keyword | 基因演算法,共同演化,賽局理論,生態位技巧,最佳取樣, | zh_TW |
| dc.subject.keyword | genetic algorithm,coevolution,game theory,niching techniques,optimal sampling, | en |
| dc.relation.page | 55 | |
| dc.rights.note | 有償授權 | |
| dc.date.accepted | 2009-07-24 | |
| dc.contributor.author-college | 電機資訊學院 | zh_TW |
| dc.contributor.author-dept | 電機工程學研究所 | zh_TW |
| 顯示於系所單位： | 電機工程學系 | |
文件中的檔案：
| 檔案 | 大小 | 格式 | |
|---|---|---|---|
| ntu-98-1.pdf 未授權公開取用 | 974.53 kB | Adobe PDF |
系統中的文件，除了特別指名其著作權條款之外，均受到著作權保護，並且保留所有的權利。