Using differential evolution for symbolic regression and numerical constant creation

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 , Peter C. Nelson, Self-emergence of structures in gene expression programming, University of Illinois at Chicago, Chicago, IL, 2006
• 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, Cambridge, MA, 1992
• 4: David E. Goldberg, Genetic Algorithms in Search, Optimization and Machine Learning, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1989
• 5: Zhuli Xie , Xin Li , Barbara Di Eugenio , Peter C. Nelson , Weimin Xiao , Thomas M. Tirpak, Using gene expression programming to construct sentence ranking functions for text summarization, Proceedings of the 20th international conference on Computational Linguistics, p.1381-es, August 23-27, 2004, Geneva, Switzerland [doi>10.3115/1220355.1220557]
• 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.
• 7: Cândida Ferreira, Gene Expression Programming: Mathematical Modeling by an Artificial Intelligence (Studies in Computational Intelligence), Springer-Verlag New York, Inc., Secaucus, NJ, 2006
• 8: Kenneth Price , Rainer M. Storn , Jouni A. Lampinen, Differential Evolution: A Practical Approach to Global Optimization (Natural Computing Series), Springer-Verlag New York, Inc., Secaucus, NJ, 2005
• 9: Qiongyun Zhang , Chi Zhou , Weimin Xiao , Peter C. Nelson, Improving Gene Expression Programming Performance by Using Differential Evolution, Proceedings of the Sixth International Conference on Machine Learning and Applications, p.31-37, December 13-15, 2007 [doi>10.1109/ICMLA.2007.55]
• 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 , Matthew P. Evett, Numeric Mutation as an Improvement to Symbolic Regression in Genetic Programming, Proceedings of the 7th International Conference on Evolutionary Programming VII, p.251-260, March 25-27, 1998
• 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.
• 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.
• 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.
• 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 New York, Inc., Secaucus, NJ, 2006
• 20: R. Shipman , M. Shackleton , I. Harvey, The Use of Neutral Genotype-Phenotype Mappings for Improved Evolutionary Search, BT Technology Journal, v.18 n.4, p.103-111, October 2000 [doi>10.1023/A:1026714927227]

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.2 Automatic Programming
          Subjects: Program synthesis

General Terms:
Algorithms

Keywords:
combinatorial search, constant creation, differential evolution, gene expression programming, genetic algorithms, genetic programming, neutral mutations, optimization, prefix gene expression programming, redundant representations, symbolic regression