臺灣博碩士論文加值系統

基因程式設計(Genetic Programming)簡稱GP，是由電腦模擬進化機制及過程，將程式自行演化以達成特定目的。在本研究中嘗試利用基因程式設計以共同演化方式，演化出紅綠燈遊戲中鬼和遊戲者雙方的攻防策略，希望鬼能找到有效的獵捕策略而遊戲者能善用防衛與合作的策略，並能達到類似兒童在紅綠燈遊戲中的攻防策略。本研究利用「簡易單純的函數與終端點運算」，期望以基因程式技術分別演化出具有高彈性的策略，使鬼能夠繞過複雜障礙物來獵捕遊戲者，遊戲者能善用防衛與合作的策略並加以組合來加強整體的生存力和抵禦鬼的獵捕。
由系統模擬結果顯示，利用「簡易單純的函數與終端點運算」，本研究能夠成功地演化出雙方效率不錯的攻防策略，此結果除了可以做為其他相似研究的參考外，也可以做為演化更複雜的合作模式和策略組合：如機器人的合作模式、線上虛擬人物的自我學習或人類學習模式的基礎。

The genetic programming(GP) can evolve programs automatically by simulating the evolutionary mechanism on computers. In this research, we use the GP technique and the coevolution mechanism to evolve the cooperative model for the Traffic Light Game. We hope these evolution strategies can derive the similar behaviors of the players in the real children’s Traffic Light Game. Simple functions and terminals are used to coevolve the high elastic strategies for the ghost and the players .Then the ghost can efficiently detour round these obstacles and capture players in the simulated environment. Then, the players evolve the more efficiently cooperative models to protect against the ghost .
From the simulation results, the efficient strategies of a ghost and players can be coevolved with simple functions and terminals . This research can not only be used to related researches, but also can be applied to develop more complex cooperative models and strategic combination (eg. the cooperative models for robots、self-learning of virtual agent on line or human learning model).

目錄
第一章 緒論 ………………………………………………1
第一節 研究動機 ………………………………………………………1
第二節 研究目的 ………………………………………………………4
第三節 研究假設 ………………………………………………………5
第四節 研究限制 ………………………………………………………6
第五節 研究流程 ………………………………………………………7
第二章 文獻探討 …………………………………………8
第一節 兒童活動---紅綠燈遊戲………………………………………8
第二節 基因演算法……………………………………………………10
第三節 基因程式設計…………………………………………………16
第四節 共同演化………………………………………………………21
第三章 攻防策略的基因程式設計………………………23
第一節 紅綠燈遊戲的攻防策略………………………………………23
第二節 函數集合與終端點集合………………………………………26
第三節 鬼獵捕策略之演化……………………………………………30
第四節 遊戲者防衛與合作策略之演化………………………………31
第五節 鬼和遊戲者攻防策略之共同演化……………………………32
第六節 系統架構………………………………………………………33
第四章 實驗結果與分析…………………………………40
第一節 鬼的獵捕策略演化……………………………………………40
第二節 遊戲者的防衛與合作策略演化………………………………43
第三節 共同演化的參數設定…………………………………………49
第四節 鬼和遊戲者攻防策略的共同演化……………………………52
第五章 結論與建議………………………………………58
第一節 結論……………………………………………………………58
第二節 建議……………………………………………………………62
參考文獻
表 次
表3-1 鬼演化過程的參數設定……………………………………………30
表3-2 遊戲者演化過程的參數設定………………………………………31
表3-3 鬼和遊戲者共同演化過程的參數設定……………………………32
表4-1 四種鬼的初始策略…………………………………………………52

中文部分
林政行（民73）。1984。植物與昆蟲的共同演化。台灣省立博物館。
孫光天、陳岳宏﹙民89﹚。基因程式技術於螞蟻族群合作模式之研究。第五屆人工智慧研討會，國立台灣科技大學，570-577。
孫光天、蔡博成、賴彥睿﹙民90﹚。基因程式技術於螞蟻族群式三度空間搜尋之研究。第六屆人工智慧研討會，國立中山大學，175-180。
張翠娥、吳文鶯﹙民86﹚。嬰幼兒遊戲與教具。台北市：心理出版社。
蔡博成﹙民91﹚。基因程式技術於黑猩猩獵捕赤疣猴合作模式之研究。國立台南師範學院碩士論文，未出版，台南市。
戴伯昌﹙民89﹚。國民小學自然科網路學習環境─利用基因演算法模擬生物進化之研究。國立台南師範學院碩士論文，未出版，台南市。
Charles Darwin (1998). 物種起源(葉篤莊等人譯)。台北市：臺灣商務印書館。(原出版於西元1859年)
Fergus P. Hughes (2000). 兒童遊戲：兒童發展關的詮釋(郭靜晃譯)。台北市: 洪葉文化出版，。 (原出版於西元1995年)
Richard Dawkins (2002). 盲眼鐘錶匠: 解讀生命史的奧祕(王道還譯)。台北市: 天下文化出版，。 (原出版於西元1996年)
Ridley M.(2000).紅色皇后：性與人性的演化（范昱峰譯）。台北市: 時報出版。
英文部分
Andre, D., Bennett Ⅲ , F. H, & Koza, J. R. (1996). Discovery by Genetic Programming of a Cellular Automata Rule that is Better than any Known Rule for the Majority Classification Problem. Proceedings of the First Annual Conference, 1, 1-11.
Burke, D. S., Grefenstette, J. J., De Jong, K. A., Wu, A. S., & Ramsey, C. L.( 1998). Putting more genetics into genetic algorithms. Evolutionary Computation, 6(4), 387-410.
Clark, D. P., & Russell, L. D. (1997). Molecular Biology- Made simple and fun. Cache River Press,153-173.
Davis, L. (1991). Handbook of Genetic Algorithm. Van Nostrand Reinhold.
Friedrich Froebel (1887). The Education of Man，NY：Appltton.
Gen, M., & Cheng, R. (1997). Genetic Algorithms & Engineering Design. New York: John Wiley & Sons.. inc.
Goldberg D. E.(1989). Genetic Algorithms in search, Optimization and Machine Learning. Addison Wesley, MAssachusetts.
Harvey, I. (1992). The SAGA cross: The mechanics of crossover for variable-length genetic algorithms. Parallel problem solving from nature, 2, 269-278. Amsterdam, NL: Elsevier.
Holland, J. H. (1975). Adaptation in natural and artificial systems, University of Michigan Press, Ann Arbor, Michigan. (Second edition: MIT Press, Cambridge, Massachusetts, 1992).
Koza, J. R. (1992). Genetic Programming: On the Programming of Computers by Means of Natural Selection. Cambridge, MA: MIT Press.
Koza, J. R. (1994). Genetic Programming Ⅱ: Automatic Discovery of Reusable Programs. Cambridge, MA: MIT Press.
Kubota, N., Fukuda, T., Arakawa, T., Shimojima, K. (1997). Evolutionary Transition on Virus Evolutionary Genetic Algorithm. Proceedings of International Conference on Evolutionary Computation, 291-296.
Ladd, S. R. (1996). Genetic algorithms in C++, M&T Books, New York.
Marco, D., Maniezzo, V., & Colorni, A. (1996). The Ant System: Optimization by a Colony of Cooperating Agents. IEEE Transactions on Systems, Man, and Cybernetics-Part B, 26(1), 29-41.
Markus, B., & Wolfgang, B.(2001). A Comparison of Linear Genetic Programming and Neural Networks in Medical Data Mining. IEEE Transactions on Evolutionary Computation, 5(1), 17-26.
Mitchell, M. (1996). An introduction to genetic algorithms, MIT Press, Cambridge, Massachusetts.
Ribeiro Filho, J. L., & Treleaven, C. (1994). Genetic algorithm programming environment. IEEE Computer, 27(6), 28-43.
Sette, S.& Boullart, L. (2001). Genetic Programming: Principles and Applications, Engineering Applications of Artificial Intelligence, 727-736.
Singleton A. (1994). Genetic programming with C++, Byte, 171-176, (Feb).
Srinivas, M. and L. M. Pantnaik (1994), Genetic Algorithm: A Survey, IEEE Computer, June, 17-26.