research-article

Accelerating genetic programming by frequent subtree mining

Authors:

Yoshitaka Kameya,

Junichi Kumagai,

Yoshiaki KurataAuthors Info & Claims

GECCO '08: Proceedings of the 10th annual conference on Genetic and evolutionary computation

Pages 1203 - 1210

https://doi.org/10.1145/1389095.1389332

Published: 12 July 2008 Publication History

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.

References

[1]

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.

[2]

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.

Digital Library

[3]

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.

Digital Library

[4]

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.

[5]

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.

Digital Library

[6]

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.

[7]

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.

[8]

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.

Digital Library

[9]

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.

[10]

J. R. Koza. Genetic Programming: On the Programming of Computers by means of Natural Selection. MIT Press, 1992.

Digital Library

[11]

J. R. Koza. Genetic Programming II: Automatic Discovery of Reusable Subprograms. MIT Press, 1994.

Digital Library

[12]

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.

Digital Library

[13]

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.

Digital Library

[14]

R. Salustowicz and J. Schmidhuber. Probabilistic incremental program evolution. Evolutionary Computation, 5(2):123--141, 1997.

Digital Library

[15]

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.

[16]

W. A. Tackett. Mining the genetic program. IEEE Expert, 10(3):28--38, 1995.

Digital Library

[17]

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.

Cited By

Burlacu BYang KAffenzeller M(2024)Population diversity and inheritance in genetic programming for symbolic regressionNatural Computing: an international journal10.1007/s11047-022-09934-x23:3(531-566)Online publication date: 1-Sep-2024
https://dl.acm.org/doi/10.1007/s11047-022-09934-x
Feng LHou YZhu ZFeng LHou YZhu Z(2021)PreliminaryOptinformatics in Evolutionary Learning and Optimization10.1007/978-3-030-70920-4_2(7-15)Online publication date: 30-Mar-2021
https://doi.org/10.1007/978-3-030-70920-4_2
Zhong JLi LLiu WFeng LHu X(2019)A Co-evolutionary Cartesian Genetic Programming with Adaptive Knowledge Transfer2019 IEEE Congress on Evolutionary Computation (CEC)10.1109/CEC.2019.8790352(2665-2672)Online publication date: Jun-2019
https://doi.org/10.1109/CEC.2019.8790352
Show More Cited By

Index Terms

Accelerating genetic programming by frequent subtree mining

Recommendations

Frequent Subtree Mining - An Overview
Advances in Mining Graphs, Trees and Sequences

Mining 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 Sequences

Mining 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 computation

This 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

Information & Contributors

Information

Published In

cover image ACM Conferences

GECCO '08: Proceedings of the 10th annual conference on Genetic and evolutionary computation

July 2008

1814 pages

ISBN:9781605581309

DOI:10.1145/1389095

Conference Chair:
Conor Ryan
University of Limerick, Ireland
,
Editor:
Maarten Keijzer
Chordiant Software International B.V., The Netherlands

Copyright © 2008 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 12 July 2008

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

GECCO08

Sponsor:

GECCO08: Genetic and Evolutionary Computation Conference

July 12 - 16, 2008

GA, Atlanta, USA

Acceptance Rates

Overall Acceptance Rate 1,669 of 4,410 submissions, 38%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

12
Total Citations
View Citations
209
Total Downloads

Downloads (Last 12 months)2
Downloads (Last 6 weeks)0

Reflects downloads up to 08 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

Burlacu BYang KAffenzeller M(2024)Population diversity and inheritance in genetic programming for symbolic regressionNatural Computing: an international journal10.1007/s11047-022-09934-x23:3(531-566)Online publication date: 1-Sep-2024
https://dl.acm.org/doi/10.1007/s11047-022-09934-x
Feng LHou YZhu ZFeng LHou YZhu Z(2021)PreliminaryOptinformatics in Evolutionary Learning and Optimization10.1007/978-3-030-70920-4_2(7-15)Online publication date: 30-Mar-2021
https://doi.org/10.1007/978-3-030-70920-4_2
Zhong JLi LLiu WFeng LHu X(2019)A Co-evolutionary Cartesian Genetic Programming with Adaptive Knowledge Transfer2019 IEEE Congress on Evolutionary Computation (CEC)10.1109/CEC.2019.8790352(2665-2672)Online publication date: Jun-2019
https://doi.org/10.1109/CEC.2019.8790352
Zhong JFeng LOng Y(2017)Gene Expression Programming: A Survey [Review Article]IEEE Computational Intelligence Magazine10.1109/MCI.2017.270861812:3(54-72)Online publication date: Aug-2017
https://doi.org/10.1109/MCI.2017.2708618
Zhong JOng YCai W(2016)Self-Learning Gene Expression ProgrammingIEEE Transactions on Evolutionary Computation10.1109/TEVC.2015.242441020:1(65-80)Online publication date: Feb-2016
https://doi.org/10.1109/TEVC.2015.2424410
Araseki H(2012)Effectiveness of scale-free properties in genetic programmingThe 6th International Conference on Soft Computing and Intelligent Systems, and The 13th International Symposium on Advanced Intelligence Systems10.1109/SCIS-ISIS.2012.6505204(285-289)Online publication date: Nov-2012
https://doi.org/10.1109/SCIS-ISIS.2012.6505204
Al-Madi NLudwig S(2012)Adaptive genetic programming applied to classification in data mining2012 Fourth World Congress on Nature and Biologically Inspired Computing (NaBIC)10.1109/NaBIC.2012.6402243(79-85)Online publication date: Nov-2012
https://doi.org/10.1109/NaBIC.2012.6402243
Chen XOng YLim MTan K(2011)A Multi-Facet Survey on Memetic ComputationIEEE Transactions on Evolutionary Computation10.1109/TEVC.2011.213272515:5(591-607)Online publication date: 1-Oct-2011
https://dl.acm.org/doi/10.1109/TEVC.2011.2132725
Kameya YPrayoonsri C(2011)Pattern-based preservation of building blocks in genetic algorithms2011 IEEE Congress of Evolutionary Computation (CEC)10.1109/CEC.2011.5949939(2578-2585)Online publication date: Jun-2011
https://doi.org/10.1109/CEC.2011.5949939
Wolfson KZakov SSipper MZiv-Ukelson M(2011)Have your spaghetti and eat it tooGenetic Programming and Evolvable Machines10.1007/s10710-010-9122-112:2(121-160)Online publication date: 1-Jun-2011
https://dl.acm.org/doi/10.1007/s10710-010-9122-1
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Figures

Tables

Media

View Table of Conten