圖形演化理論中策略參數與基因運算元的設計

本論文設計出一種能與圖形染色體進行交互作用的突變策略參數，在過去僅有演化理論 (Evolutionary Computation) 中的演化策略 (Evolution Strategy) 才有所謂的突變用策略參數，儘管如此，亦僅能用於實數型的染色體。透過策略參數的分析與設計，將可以使得我們更能掌握各類型圖形染色體突變對圖形性質所產生的影響。在本論文中，共分析並設計出六種適用於圖形染色體上的突變策略參數，它們分別為 EdgePrune、EdgeDiff、NodePrune、NodeDiff、GraphPrune與GraphDiff。策略參數是用於讓圖形染色體上之特定節點產生突變的，然而它本身也會發生突變。如此一來，前面所分析的六種突變策略便有機會經由突變，進而轉換成其它種類的突變策略，不再只是一成不變。在本論文中也將該六種圖形染色體的突變策略歸納成三大類，以便於設計策略參數所使用的突變運算元。除了突變，兩個或兩個以上的策略參數的重組運算元亦有存在的需求，這是因為當兩個或兩個以上的圖形染色體再進行重組時，對於各節點的突變策略參數亦會隨之交換與重組。在本論文便加以設計出兩種策略參數交配與重組的方法，即Discrete Recombination Mapping與 Intermediate Recombination Mapping。為了驗證圖形演化理論與其策略參數，本論文並建構出兩個實作系統分別用來解決旅行者花費的問題 (Traveler’s Cost Problem) 與老鼠走迷宮。利用 Traveler’s Cost Problem 進行與基因演算法 (Genetic Algorithm) 的比較，使用老鼠走迷宮進行與 (Genetic Programming) 的比較。

關鍵字

基因程式設計；基因演算法；演化策略；演化理論；圖形演化理論；策略參數

並列摘要

A strategy parameter is designed for mutating the graph chromosome in this paper. In past, only Evolution Strategy, one of the major three classes EAs, has strategy parameter for controlling the real form chromosome. The impact of the mutation operators on the characteristics of graph can be revealed through the analysis of strategy parameter for graph chromosomes. There are six mutation strategies analyzed and designed in this paper, including EdgePrune, EdgeDiff, NodePrune, NodeDiff, GraphPrune, and GraphDiff. Although the strategy parameter is used in mutating graph chromosomes, it will be also transformed to other strategies by mutation. Therefore, those six mutation strategies have chances to transform to others. A strategy will not keep same forever. This paper also induces those mutation strategies into three classes for designing the mutation operators of strategy parameter. Besides mutation operators, recombination operators are also designed for the strategy parameter in this paper. Two recombination mapping are designed: discrete recombination mapping and intermediate recombination mapping。 In order to verify the Graph Evolution theory and its strategy parameter, two experiment systems are constructed to solve Traveler’s Cost Problem and A Mouse in the Maze Problem. The comparisons between Genetic Algorithm and Graph Evolution are made by solving Traveler’s Cost Problem. A piece of program is considered as chromosome and generated by both Genetic Programming and Graph Evolution. After the program code is generated automatically, the fitness of the chromosome depends on how long a mouse will take for escaping the maze.

並列關鍵字

Genetic Algorithm ； Evolutionary Computation ； Strategy Parameter ； Genetic Programming ； Evolution Strategies ； Graph Evolution

參考文獻

[Aze92] R. Azencott, (1992), Simulated Annealing, New York: Wiley, 1992

[BaS93] T. Bäck and H. P. Schwefel, (1993), "An Overview of Evolutionary Algorithms for Parameter Optimization," Evolutionary Computation, Vol. 1, No. 1, MIT Press, 1993, pp.1-23

[BerH99] Michael Berthold and David J. Hand, (1999), Intelligent Data Analysis, Berlin, Heidelberg: Springer-Verlag, 1999

[ChH99] Maiga Chang and Jia-Sheng Heh (1999), "Implements an Evolutionary Self-Organizing Map Based on Graph Evolution," Journal of Chinese Fuzzy Systems Association, Vol. 5, Issue 2, Dec. 1999, pp. 17-24

[DaS87] L. Davis and M. Steenstrup, (1987), "Genetic Algorithms and Simulated Annealing: An Overview," Genetic Algorithms and Simulated Annealing, Edited by L. Davis, Research Notes in Artificial Intelligence, Los Altos, CA: Morgan Kaufmann, 1987, pp.1-11

國際替代計量

圖形演化理論中策略參數與基因運算元的設計

未授權

主題瀏覽