于天立Yu, Tian-Li臺灣大學:電機工程學研究所林偉楷Lin, Wei-KaiWei-KaiLin2010-07-012018-07-062010-07-012018-07-062009U0001-2307200920543300http://ntur.lib.ntu.edu.tw//handle/246246/188155這篇論文探討共同演化的基因演算法用於演化賽局策略的能力。更確切的說，這篇論文的討論限定在雙人、零和且對稱的賽局。在這樣的前提下，單純策略和混合策略被分開討論。要共同演化出一個混合策略的納許均衡是具有挑戰性的，因為均衡的策略不能獲得比其他策略更高的得益期望值。這個論點在剪刀、石頭、布的實驗中被驗證，因為所有的混合策略產生的得益期望值一樣，使得共同演化無法收斂到納許均衡。另一方面，在一些賽局中，單純策略是較容易共同演化的，尤其是族群之多樣性被特別保持的時候。實驗上，使用維持生態位的技巧，例如限制競爭式選擇法、確定性擁擠法，對於共同演化都有明顯的助益。更進一步，內文也展示了在共同演化中，族群大小和評估個體時最佳的對手數量之間，權衡折中的關係。在論文的最後，實驗上示範了一個賽局遊戲，相對於棋盤需要指數大小的族群才能演化，也就是仍存在對共同演化來說較困難的賽局。在這樣的賽局中，需要在族群中維持指數的對手來演化出最佳的策略。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 nichingechniques 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.Acknowledgments i文摘要iibstract iiiontents ivist of Figures viist of Algorithms viii Introduction 1 Background of Game Theory 3.1 The Normal-Form Game . . . . . . . . . . . . . . . . . . . . . . . . . 3.2 Pure Strategies and Mixed Strategies . . . . . . . . . . . . . . . . . . 4.3 Nash Equilibrium . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.4 Two-Player, Symmetric, Zero-Sum and Turn-Based Games . . . . . . 5 Background of Genetic Algorithms and Coevolutionary Algorithms 7.1 Simple Genetic Algorithms . . . . . . . . . . . . . . . . . . . . . . . . 7.2 Niching Techniques . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11.3 Coevolutionary Algorithms . . . . . . . . . . . . . . . . . . . . . . . . 16 Mixed Strategy Games, Less Co-Evolvable 19.1 Theoretical Approach . . . . . . . . . . . . . . . . . . . . . . . . . . . 19.2 Empirical Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21 Pure Strategy Games, More Co-Evolvable 23.1 Testing Games . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24.2 Coevolutionary Genetic Algorithm with Niching . . . . . . . . . . . . 26.3 Enhancing Efficiency via Sampling . . . . . . . . . . . . . . . . . . . 40 A Less Co-Evolvable Pure Strategy Game 43.1 Bit-Flipping Game . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44 Conclusions 47ibliography 49997921 bytesapplication/pdfen-US基因演算法共同演化賽局理論生態位技巧最佳取樣genetic algorithmcoevolutiongame theoryniching techniquesoptimal samplingthesishttp://ntur.lib.ntu.edu.tw/bitstream/246246/188155/1/ntu-98-R96921073-1.pdf