ABSTRACT
One crucial issue in genetic programming (GP) is how to acquire promising building blocks efficiently. In this paper, we propose a GP method (called GPTM, GP with Tree Mining) which protects the subtrees repeatedly appearing in superior individuals. Currently GPTM utilizes a FREQT-like efficient data mining method to find such subtrees. GPTM is evaluated by three benchmark problems, and the results indicate that GPTM is comparable to or better than POLE, one of the most advanced probabilistic model building GP methods, and finds the optimal individual earlier than the standard GP and POLE.
- P. J. Angeline and J. B. Pollack. The evolutionary induction of subroutines. In Proc. of the 14th Conf. of the Cognitive Science Society, pages 236--241, 1992.Google Scholar
- H. Arimura and T. Uno. A polynomial space and polynomial delay algorithm for enumeration of maximal motifs in a sequence. In Proc. of the 16th Intl. Symp. on Algorithms and Computation (ISAAC-2005), pages 724--737, 2005. Google ScholarDigital Library
- T. Asai, K. Abe, S. Kawasoe, H. Arimura, H. Sakamoto, and S. Arikawa. Efficent substructure discovery from large semi-structured data. In Proc. of the 2nd SIAM Intl. Conf. on Data Mining, 2002. Google ScholarDigital Library
- Y. Chi, Y. Yang, Y. Xia, and R. R. Muntz. CMTree Miner: mining both closed and maximal frequent subtrees. In Proc. of the 8th Pacific-Asia Conf. on Knowledge Discovery and Data Mining (PAKDD-2004), pages 63--73, 2004.Google Scholar
- T. C. Fogarty. Varying the probability of mutation in the genetic algorithm. In Proc. of the 3rd Intl. Conf. on Genetic Algorithms (ICGA-89), pages 104--109, 1989. Google ScholarDigital Library
- Y. Hasegawa and H. Iba. Optimizing programs with estimation of Bayesian network. In Proc. of the 2006 Congress on Evolutionary Computation (CEC-2006), pages 1378--1385, 2006.Google ScholarCross Ref
- Y. Hasegawa and H. Iba. Probabilistic model building genetic programming based on estimation of Bayesian network. Trans. of the Japanese Society for Artificial Intelligence, 22(1):37--47, 2007. In Japanese.Google ScholarCross Ref
- R. D. Howard and J. R. Koza. Evolving modules in genetic programming by subtree encapsulation. In Proc. of the 4th European Conf. on Genetic Programming (EuroGP 2001), pages 160--175, 2001. Google ScholarDigital Library
- T. Ito, H. Iba, and S. Sato. Depth-dependent crossover for genetic programming. In Proc. of the 1998 IEEE Intl. Conf. on Evolutionary Computation (ICEC-98), pages 775--780, 1998.Google ScholarCross Ref
- J. R. Koza. Genetic Programming: On the Programming of Computers by means of Natural Selection. MIT Press, 1992. Google ScholarDigital Library
- J. R. Koza. Genetic Programming II: Automatic Discovery of Reusable Subprograms. MIT Press, 1994. Google ScholarDigital Library
- B. Punch, D. Zongker, and E. Goodman. The royal tree problem -- a benchmark for single and multi-population genetic prgramming. In P. J. Angeline and K. E. Kinnear (Eds), Advances in Genetic Programming II. MIT Press, 1996. Google ScholarDigital Library
- J. P. Rosca and D. H. Ballard. Discovery of subroutines in genetic programming. In P. J. Angeline and K. E. Kinnear (Eds), Advances in Genetic Programming II. MIT Press, 1996. Google ScholarDigital Library
- R. Salustowicz and J. Schmidhuber. Probabilistic incremental program evolution. Evolutionary Computation, 5(2):123--141, 1997. Google ScholarDigital Library
- Y. Shan, R. I. McKay, R. Baxter, H. Abbass, D. Essam, and H. X. Nguyen. Grammar model-based program evolution. In Proc. of the 2004 Congress on Evolutionary Computation (CEC-2004), pages 478--485, 2004.Google ScholarCross Ref
- W. A. Tackett. Mining the genetic program. IEEE Expert, 10(3):28--38, 1995. Google ScholarDigital Library
- K. Yanai and H. Iba. Program evolution by integrating EDP and GP. In Proc. of the Genetic and Evolutionary Computation (GECCO-2004), pages 774--785, 2004.Google ScholarCross Ref
Index Terms
- Accelerating genetic programming by frequent subtree mining
Recommendations
Frequent Subtree Mining - An Overview
Advances in Mining Graphs, Trees and SequencesMining frequent subtrees from databases of labeled trees is a new research field that has many practical applications in areas such as computer networks, Web mining, bioinformatics, XML document mining, etc. These applications share a requirement for ...
Frequent Subtree Mining - An Overview
Advances in Mining Graphs, Trees and SequencesMining frequent subtrees from databases of labeled trees is a new research field that has many practical applications in areas such as computer networks, Web mining, bioinformatics, XML document mining, etc. These applications share a requirement for ...
How online simplification affects building blocks in genetic programming
GECCO '09: Proceedings of the 11th Annual conference on Genetic and evolutionary computationThis paper investigates the effect on building blocks during evolution of two online program simplification methods in genetic programming. The two simplification methods considered are algebraic simplification and numerical simplification. The building ...
Comments