research-article

Using differential evolution for symbolic regression and numerical constant creation

Authors:

Brian M. Cerny,

Peter C. Nelson,

Chi ZhouAuthors Info & Claims

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

Pages 1195 - 1202

https://doi.org/10.1145/1389095.1389331

Published: 12 July 2008 Publication History

Abstract

One problem that has plagued Genetic Programming (GP) and its derivatives is numerical constant creation. Given a mathematical formula expressed as a tree structure, the leaf nodes are either variables or constants. Such constants are usually unknown in Symbolic Regression (SR) problems, and GP, as well as many of its derivatives, lack the ability to precisely approximate these values. This is due to the inherently discrete encoding of GP-like methods which are more suited to combinatorial searches than real-valued optimization tasks. Previously, several attempts have been made to resolve this issue, and the dominant solutions have been to either embed a real-valued local optimizer or to develop additional numerically oriented operators. In this paper, an entirely new approach is proposed for constant creation. Through the adoption of a robust, real-valued optimization algorithm known as Differential Evolution (DE), constants and GP-like programs will be simultaneously evolved in such a way that the values of the leaf nodes will be approximated as the tree structure is itself changing. Experimental results from several SR benchmarks are presented and analyzed. The results demonstrate the feasibility of the proposed algorithm and suggest that exotic or computationally expensive methods are not necessary for successful constant creation.

References

[1]

Xin Li. Self-Emergence of Structures in Gene Expression Programming. PhD thesis, University of Illinois at Chicago, 2006.

Digital Library

[2]

Cândida Ferreira. Gene expression programming: A new adaptive algorithm for solving problems. Complex Systems, 13(2):87--129, 2001.

[3]

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

Digital Library

[4]

David E. Goldberg. Genetic Algorithms in Search, Optimization, and Machine Learning. Addison-Wesley Professional, 1989.

Digital Library

[5]

Zhuli Xie, Xin Li, Barbara Di Eugenio, Weimin Xiao, Thomas M. Tirpak, and Peter C. Nelson. Using Gene Expression Programming to Construct Sentence Ranking Functions for Text Summarization. In Proceedings of the 20th International Conference on Computational Linguistics, (COLING 2004), pages 1381--1384, Geneva, Switzerland, August 2004.

Digital Library

[6]

Chi Zhou, Weimin Xiao, Thomas M. Tirpak, and Peter C. Nelson. Evolving Accurate and Compact Classification Rules with Gene Expression Programming. IEEE Transactions on Evolutionary Computation, 7(6):519--531, December 2003.

Digital Library

[7]

Cândida Ferreira. Gene Expression Programming: Mathematical Modeling by an Artificial Intelligence. Springer-Verlag, second edition, 2006.

Digital Library

[8]

Kenneth V. Price, Rainer M. Storn, and Jouni A. Lampinen. Differential Evolution: A Pratical Approach to Global Optimization. Springer-Verlag, 2005.

Digital Library

[9]

Qiongyun Zhang, Chi Zhou, Weimin Xiao, and Peter C. Nelson. Improving Gene Expression Programming Performance by Using Differential Evolution. In Proceedings of the 6th International Conference on Machine Learning and Applications (ICMLA'07), pages 31--37, Cincinnati, OH, USA, 2007. IEEE Computer Society.

Digital Library

[10]

Stefano Cagnoni, Daniel Rivero, and Leonardo Vanneschi. A purely evolutionary memetic algorithm as a first step towards symbiotic coevolution. In Proceedings of the IEEE Congress on Evolutionary Computation, (CEC 2005), pages 1156--1163, Edinburgh, UK, September 2005. IEEE.

[11]

Alexander Topchy and William Punch. Faster Genetic Programming based on Local Gradient Search of Numeric Leaf Values. In Proceedings of the Genetic and Evolutionary Computation Conference (GECCO 2001), pages 155--162, San Francisco, CA, USA, July 2001. Morgan Kaufmann.

[12]

Gunther R. Raidl. A Hybrid GP Approach for Numerically Robust Symbolic Regression. In Genetic Programming 1998: Proceedings of the Third Annual Conference, pages 323--328, Madison, WI, USA, July 1998. Morgan Kaufmann.

[13]

Thomas Fernandez and Matthew P. Evett. Numeric Mutation as an Improvement to Symbolic Regression in Genetic Programming. In Evolutionary Programming VII, 7th International Conference, (EP98), pages 251--260. Springer, 1998.

Digital Library

[14]

Conor Ryan and Maarten Keijzer. An Analysis of Diversity of Constants of Genetic Programming. In Genetic Programming, 6th European Conference, EuroGP 2003, pages 404--413. Springer, 2003.

Digital Library

[15]

Xin Li, Chi Zhou, Peter C. Nelson, and Thomas M. Tirpak. Investigation of Constant Creation Techniques in the Context of Gene Expression Programming. In Maarten Keijzer, editor, Late Breaking Papers at the 2004 Genetic and Evolutionary Computation Conference, Seattle, WA, USA, July 2004.

[16]

Michael O'Neill, Ian Dempsey, Anthony Brabazon, and Conor Ryan. Analysis of a Digit Concatenation Approach to Constant Creation. In Genetic Programming, 6th European Conference, EuroGP 2003, pages 173--182. Springer, 2003.

Digital Library

[17]

Maarten Keijzer. Improving Symbolic Regression with Interval Arithmetic and Linear Scaling. In Genetic Programming, 6th European Conference, EuroGP 2003, pages 70--82. Springer, 2003.

Digital Library

[18]

Michael O'Neill and Anthony Brabazon. Grammatical Differential Evolution. In Proceedings of the 2006 International Conference on Artificial Intelligence (ICAI 2006), pages 231--236. CSREA Press, 2006.

[19]

Franz Rothlauf. Representations for Genetic and Evolutionary Algorithms. Springer-Verlag Berlin Heidelberg, second edition, 2006.

Digital Library

[20]

Rob Shipman, Mark Shackleton, and Inman Harvey. The use of neutral genotype-phenotype mappings for improved evolutionary search. BT Technology Journal, 18(4):103--111, 2000.

Digital Library

Cited By

Koch JAlderliesten TBosman P(2024)Simultaneous Model-Based Evolution of Constants and Expression Structure in GP-GOMEA for Symbolic RegressionParallel Problem Solving from Nature – PPSN XVIII10.1007/978-3-031-70055-2_15(238-255)Online publication date: 14-Sep-2024
https://dl.acm.org/doi/10.1007/978-3-031-70055-2_15
Ari DAlagoz B(2023)A differential evolutionary chromosomal gene expression programming technique for electronic nose applicationsApplied Soft Computing10.1016/j.asoc.2023.110093136:COnline publication date: 1-Mar-2023
https://dl.acm.org/doi/10.1016/j.asoc.2023.110093
Xu KSrivastava AGutfreund DSosa FUllman TTenenbaum JSutton CRanzato MBeygelzimer ADauphin YLiang PVaughan J(2021)A Bayesian-symbolic approach to reasoning and learning in intuitive physicsProceedings of the 35th International Conference on Neural Information Processing Systems10.5555/3540261.3540451(2478-2490)Online publication date: 6-Dec-2021
https://dl.acm.org/doi/10.5555/3540261.3540451
Show More Cited By

Recommendations

An improved class of real-coded Genetic Algorithms for numerical optimization

Over the last few decades, many improved Evolutionary Algorithms (EAs) have been proposed to tackle different types of optimization problems. Genetic Algorithm (GA) among other canonical algorithms have not shown consistent performance over a range of ...
Self-adaptive randomized and rank-based differential evolution for multimodal problems

Differential Evolution (DE) is a widely used successful evolutionary algorithm (EA) based on a population of individuals, which is especially well suited to solve problems that have non-linear, multimodal cost functions. However, for a given population, ...
Constrained differential evolution using generalized opposition-based learning

Differential evolution (DE) is a well-known optimization approach to deal with nonlinear and complex optimization problems. However, many real-world optimization problems are constrained problems that involve equality and inequality constraints. DE with ...

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

11
Total Citations
View Citations
296
Total Downloads

Downloads (Last 12 months)26
Downloads (Last 6 weeks)1

Reflects downloads up to 08 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

Koch JAlderliesten TBosman P(2024)Simultaneous Model-Based Evolution of Constants and Expression Structure in GP-GOMEA for Symbolic RegressionParallel Problem Solving from Nature – PPSN XVIII10.1007/978-3-031-70055-2_15(238-255)Online publication date: 14-Sep-2024
https://dl.acm.org/doi/10.1007/978-3-031-70055-2_15
Ari DAlagoz B(2023)A differential evolutionary chromosomal gene expression programming technique for electronic nose applicationsApplied Soft Computing10.1016/j.asoc.2023.110093136:COnline publication date: 1-Mar-2023
https://dl.acm.org/doi/10.1016/j.asoc.2023.110093
Xu KSrivastava AGutfreund DSosa FUllman TTenenbaum JSutton CRanzato MBeygelzimer ADauphin YLiang PVaughan J(2021)A Bayesian-symbolic approach to reasoning and learning in intuitive physicsProceedings of the 35th International Conference on Neural Information Processing Systems10.5555/3540261.3540451(2478-2490)Online publication date: 6-Dec-2021
https://dl.acm.org/doi/10.5555/3540261.3540451
Fajfar ITuma T(2018)Creation of Numerical Constants in Robust Gene Expression ProgrammingEntropy10.3390/e2010075620:10(756)Online publication date: 1-Oct-2018
https://doi.org/10.3390/e20100756
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: 1-Aug-2017
https://dl.acm.org/doi/10.1109/MCI.2017.2708618
Izzo DBiscani FMereta A(2017)Differentiable Genetic ProgrammingGenetic Programming10.1007/978-3-319-55696-3_3(35-51)Online publication date: 15-Mar-2017
https://doi.org/10.1007/978-3-319-55696-3_3
Batista RSegredo ESegura CLeón CRodríguez C(2013)Solving the unknown complexity formula problem with genetic programmingProceedings of the 12th international conference on Artificial Neural Networks: advances in computational intelligence - Volume Part I10.1007/978-3-642-38679-4_22(232-240)Online publication date: 12-Jun-2013
https://dl.acm.org/doi/10.1007/978-3-642-38679-4_22
Mukherjee SEppstein MMoore J(2012)Differential evolution of constants in genetic programming improves efficacy and bloatProceedings of the 14th annual conference companion on Genetic and evolutionary computation10.1145/2330784.2330891(625-626)Online publication date: 7-Jul-2012
https://dl.acm.org/doi/10.1145/2330784.2330891
Karaboga DOzturk CKaraboga NGorkemli B(2012)Artificial bee colony programming for symbolic regressionInformation Sciences: an International Journal10.1016/j.ins.2012.05.002209(1-15)Online publication date: 1-Nov-2012
https://dl.acm.org/doi/10.1016/j.ins.2012.05.002
Lu QWang B(2011)Feature fitness evaluation for symbolic regression via genetic programming2011 Seventh International Conference on Natural Computation10.1109/ICNC.2011.6022150(1087-1091)Online publication date: Jul-2011
https://doi.org/10.1109/ICNC.2011.6022150
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