Nothing Special   »   [go: up one dir, main page]

skip to main content
10.1145/2463372.2463481acmconferencesArticle/Chapter ViewAbstractPublication PagesgeccoConference Proceedingsconference-collections
research-article

Accelerating convergence in cartesian genetic programming by using a new genetic operator

Published: 06 July 2013 Publication History

Abstract

Genetic programming algorithms seek to find interpretable and good solutions for problems which are difficult to solve analytically. For example, we plan to use this paradigm to develop a car accident severity prediction model for new occupant safety functions. This complex problem will suffer from the major disadvantage of genetic programming, which is its high demand for computational effort to find good solutions. A main reason for this demand is a low rate of convergence. In this paper, we introduce a new genetic operator called forking to accelerate the rate of convergence. Our idea is to interpret individuals dynamically as centers of local Gaussian distributions and allow a sampling process in these distributions when populations get too homogeneous. We demonstrate this operator by extending the Cartesian Genetic Programming algorithm and show that on our examples convergence is accelerated by over 50% on average. We finish this paper with giving hints about parameterization of the forking operator for other problems.

References

[1]
Wolfgang Banzhaf, Frank D Francone, and Peter Nordin. The Effect of Extensive Use of the Mutation Operator on Generalization in Genetic Programming Using Sparse Data Sets. In Proceedings of the 4th International Conference on Parallel Problem Solving from Nature, pages 300--309. Springer-Verlag, 1996.
[2]
Janet Clegg, James Alfred Walker, and Julian Frances Miller. A New Crossover Technique for Cartesian Genetic Programming. In Proceedings of the 9th annual conference on Genetic and evolutionary computation, GECCO '07, pages 1580--1587. ACM, 2007.
[3]
Lawrence Davis et al. Handbook of Genetic Algorithms, volume 115. Van Nostrand Reinhold New York, 1991.
[4]
John H. Holland. Adaptation in Natural and Artificial Systems: An Introductory Analysis with Applications to Biology, Control, and Artificial Intelligence. University of Michigan Press, April 1975.
[5]
Gregory S Hornby. ALPS: The Age-Layered Population Structure for Reducing the Problem of Premature Convergence. In Proceedings of the 8th annual conference on Genetic and evolutionary computation, pages 815--822. ACM, 2006.
[6]
IEEE Task P754. IEEE Standard for Floating-Point Arithmetic. Technical report, Microprocessor Standards Committee of the IEEE Computer Society, August 2008.
[7]
ISO. ISO C Standard 1999. Technical report, ISO, 1999. ISO/IEC 9899:1999 draft.
[8]
John R. Koza. Genetic Programming: A Paradigm for Genetically Breeding Populations of Computer Programs to Solve Problems. Stanford University, Department of Computer Science, 1990.
[9]
W. B. Langdon. A Many Threaded CUDA Interpreter for Genetic Programming. In Proceedings of the 13th European Conference on Genetic Programming, volume 6021 of LNCS, pages 146--158. Springer, 2010.
[10]
Joel Lehman and Kenneth O. Stanley. Efficiently Evolving Programs Through the Search for Novelty. In Proceedings of the 12th annual conference on Genetic and evolutionary computation, GECCO '10, pages 837--844. ACM, 2010.
[11]
Julian F. Miller. An Empirical Study of the Efficiency of Learning Boolean Functions using a Cartesian Genetic Programming Approach. In Proceedings of the Genetic and Evolutionary Computation Conference, volume 2, pages 1135--1142. Morgan Kaufmann, 1999.
[12]
Julian F. Miller, editor. Cartesian Genetic Programming. Springer Berlin Heidelberg, 1st edition. edition, September 2011.
[13]
Julian F. Miller and Stephen L. Smith. Redundancy and Computational Efficiency in Cartesian Genetic Programming. Transactions on Evolutionary Computation, 10(2):167--174, September 2006.
[14]
Julian F. Miller and Peter Thomson. Cartesian Genetic Programming. In Proceedings of the Third European Conference on Genetic Programming, volume 1802, pages 121--132. Springer-Verlag, 2000.
[15]
Ingo Rechenberg. Evolutionsstrategie: Optimierung technischer Systeme nach Prinzipien der biologischen Evolution. Number 15 in Problemata. Frommann-Holzboog, Stuttgart-Bad Cannstatt, 1973.
[16]
Michael Schmidt and Hod Lipson. Distilling Free-Form Natural Laws from Experimental Data. Science, 324 (5923):81--85, 2009.
[17]
Karel Slan'y. Comparison of CGP and Age-Layered CGP Performance in Image Operator Evolution. Genetic Programming, pages 351--361, 2009.
[18]
Zhenguo Tu and Yong Lu. A Robust Stochastic Genetic Algorithm (StGA) for Global Numerical Optimization. Transactions on Evolutionary Computation, 8(5):456--470, October 2004.
[19]
Zhenguo Tu and Yong Lu. Corrections to "A Robust Stochastic Genetic Algorithm (StGA) for Global Numerical Optimization". Transactions on Evolutionary Computation, 12(6):781--781, December 2008.

Cited By

View all
  • (2022)Immune System Programming: A Machine Learning Approach Based on Artificial Immune Systems Enhanced by Local SearchElectronics10.3390/electronics1107098211:7(982)Online publication date: 22-Mar-2022
  • (2022)Comparative Evaluation of Genetic Operators in Cartesian Genetic ProgrammingIntelligent Systems Design and Applications10.1007/978-3-030-96308-8_71(765-774)Online publication date: 27-Mar-2022
  • (2019)Recent Developments in Cartesian Genetic Programming and its VariantsACM Computing Surveys10.1145/327551851:6(1-29)Online publication date: 28-Jan-2019
  • Show More Cited By

Recommendations

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences
GECCO '13: Proceedings of the 15th annual conference on Genetic and evolutionary computation
July 2013
1672 pages
ISBN:9781450319638
DOI:10.1145/2463372
  • Editor:
  • Christian Blum,
  • General Chair:
  • Enrique Alba
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: 06 July 2013

Permissions

Request permissions for this article.

Check for updates

Author Tags

  1. cartesian genetic programming
  2. genetic operator
  3. optimization

Qualifiers

  • Research-article

Conference

GECCO '13
Sponsor:
GECCO '13: Genetic and Evolutionary Computation Conference
July 6 - 10, 2013
Amsterdam, The Netherlands

Acceptance Rates

GECCO '13 Paper Acceptance Rate 204 of 570 submissions, 36%;
Overall Acceptance Rate 1,669 of 4,410 submissions, 38%

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)5
  • Downloads (Last 6 weeks)1
Reflects downloads up to 18 Dec 2024

Other Metrics

Citations

Cited By

View all
  • (2022)Immune System Programming: A Machine Learning Approach Based on Artificial Immune Systems Enhanced by Local SearchElectronics10.3390/electronics1107098211:7(982)Online publication date: 22-Mar-2022
  • (2022)Comparative Evaluation of Genetic Operators in Cartesian Genetic ProgrammingIntelligent Systems Design and Applications10.1007/978-3-030-96308-8_71(765-774)Online publication date: 27-Mar-2022
  • (2019)Recent Developments in Cartesian Genetic Programming and its VariantsACM Computing Surveys10.1145/327551851:6(1-29)Online publication date: 28-Jan-2019
  • (2019)Cartesian genetic programming: its status and futureGenetic Programming and Evolvable Machines10.1007/s10710-019-09360-6Online publication date: 6-Aug-2019
  • (2019)Continuous Cartesian Genetic Programming with Particle Swarm OptimizationIntelligent Systems Design and Applications10.1007/978-3-030-16660-1_96(985-995)Online publication date: 14-Apr-2019
  • (2018)Analysing symbolic regression benchmarks under a meta-learning approachProceedings of the Genetic and Evolutionary Computation Conference Companion10.1145/3205651.3208293(1342-1349)Online publication date: 6-Jul-2018
  • (2016)More efficient evolution of small genetic programs in Cartesian Genetic Programming by using genotypie age2016 IEEE Congress on Evolutionary Computation (CEC)10.1109/CEC.2016.7748330(5052-5059)Online publication date: Jul-2016
  • (2015)Cartesian Genetic ProgrammingProceedings of the Companion Publication of the 2015 Annual Conference on Genetic and Evolutionary Computation10.1145/2739482.2756571(179-198)Online publication date: 11-Jul-2015
  • (2014)Symbolic Regression for Precrash Accident Severity PredictionProceedings of the 9th International Conference on Hybrid Artificial Intelligence Systems - Volume 848010.1007/978-3-319-07617-1_12(133-144)Online publication date: 11-Jun-2014

View Options

Login options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Media

Figures

Other

Tables

Share

Share

Share this Publication link

Share on social media