A New Method for Simplifying Algebraic Expressions in Genetic Programming Called Equivalent Decision Simplification
Naoki Mori*, Bob McKay*2, Nguyen Xuan Hoai*3,
Daryl Essam*4, and Saori Takeuchi*5
*Osaka Prefecture University, Osaka, Japan
*2Seoul National University, Seoul, Korea
*3Seoul National University, Seoul, Korea
*4University of New South Wales ADFA, Canberra, Australia
*5Mitsubishi Electric Corporation, Hyogo, Japan
Symbolic Regression is one of the most important applications of Genetic Programming, but suffers from one of the key issues in Genetic Programming, bloat. For a variety of reasons, reliable techniques to remove bloat are highly desirable. This paper introduces a novel approach of removing bloat, Equivalent Decision Simplification, in which subtrees are evaluated over the set of regression points. The effectiveness of the proposed method is confirmed by computer simulation taking simple Symbolic Regression problems as examples.
-  W. Banzhaf, P. Nordin, R. E. Keller, and F. D. Francone, “Genetic Programming – An Introduction; On the Automatic Evolution of Computer Programs and its Applications,” Morgan Kaufmann, dpunkt.verlag, Jan. 1998.
-  J. R. Koza, “Genetic Programming: On the Programming of Computers by Means of Natural Selection,” MIT Press, Cambridge, MA, USA, 1992.
-  J. R. Koza, M. A. Keane, M. J. Streeter, W. Mydlowec, J. Yu, and G. Lanza, “Genetic Programming IV: Routine Human-Competitive Machine Intelligence,” Kluwer Academic Publishers, 2003.
-  T. Soule, “Code Growth in Genetic Programming,” Ph.D. thesis, University of Idaho, Moscow, Idaho, USA, 15 May 1998.
-  T. Soule and J. A. Foster, “Support for multiple causes of code growth in GP,” Position paper at the Workshop on Evolutionary Computation with Variable Size Representation at ICGA-97, 20 July 1997.
-  M. Zhang, P. Wong, and D. Qian, “Online program simplification in genetic programming,” In T.-D. Wang, X. Li, S.-H. Chen, X. Wang, H. A. Abbass, H. Iba, G. Chen, and X. Yao (Eds.), “Simulated Evolution and Learning,” Proc. 6th Int. Conf., SEAL 2006, Vol.4247, Lecture Notes in Computer Science, pp. 592-600, Hefei, China, Oct. 15-18, 2006.
-  N. Mori and K. Matsumoto, “A novel measure of diversity in genetic programmings by means of subtree entropy,” In Proc. of 32th SICE Symposium on Intelligent Systems, pp. 205-210, 2005 (in Japanese).
-  M. Kang, J. Shin, T. H. Hoang, R. I. B. McKay, D. Essam, N. Mori, and X. H. Nguyen, “Code duplication and developmental evaluation in genetic programming,” In Proc. of the 2006 Asia-Pacific Workshop on Intelligent and Evolutionary Systems, pp. 181-191, Seoul, Korea, Nov. 2006.
-  R. McKay, J. Shin, T. H. Hoang, X. H. Nguyen, and N. Mori, “Using compression to understand the distribution of building blocks in genetic programming populations,” Evolutionary Computation, 2007. CEC 2007. IEEE Congress on, pp. 2501-2508, Sep. 25-28 2007.
-  J. Shin, M. Kang, R. I. B. McKay, X. Nguyen, T. H. Hoang, N. Mori, and D. Essam, “Analysing the regularity of genomes using compression and expression simplification,” In Proc. of the 10th European Conf. on Genetic Programm ing (EuroGP2007, Valencia, Spain), Vol.4445, Springer Lecture Notes in Computer Science, pp. 251-260. Springer-Verlag, Berlin, Germany, April 2007.
-  N. Mori, B. McKay, X. H. Nguyen, and D. Essam, “Equivalent decision simplification: A new method for simplifying algebraic expressions in genetic programming, 2007,” Presented at the 2007 Asia-Pacific Symposium on Intelligent and Evolutionary Systems, unpublished proceedings.
-  R. Solomonoff, “A theory of inductive inference,” Information and Control, 7:1-22, pp. 224-254, 1964.
-  N. X. Hoai, “Solving trignometric identities with tree adjunct grammar guided genetic programming,” In A. Abraham and M. Koppen (Eds.), 2001 Int. Workshop on Hybrid Intelligent Systems, LNCS, pp. 339-352, Adelaide, Springer-Verlag, Australia, 11-12 Dec. 2001.
-  B. Welch, “The significance of the difference between two means when the population variances are unequal,” Biometrika, 29, pp. 350-362, 1938.
-  P. Nordin and W. Banzhaf, “Complexity compression and evolution,” In L. Eshelman (Ed.), Genetic Algorithms, Proc. of the Sixth Int. Conf. (ICGA95), pp. 310-317, Pittsburgh, PA, USA, Morgan Kaufmann, 15-19 July 1995.
-  E. Burke, S. Gustafson, and G. Kendall, “A survey and analysis of diversity measures in genetic programming,” In W. B. Langdon, E. Cantú-Paz, K. Mathias, R. Roy, D. Davis, R. Poli, K. Balakrishnan, V. Honavar, G. Rudolph, J. Wegener, L. Bull, M. A. Potter, A. C. Schultz, J. F. Miller, E. Burke, and N. Jonoska (Eds.), GECCO 2002: Proc. of the Genetic and Evolutionary Computation Conf., pp. 716-723, Morgan Kaufmann Publishers, New York, 9-13 July 2002.
-  S. Gustafson, A. Ekart, E. Burke, and G. Kendall, “Problem difficulty and code growth in genetic programming,” Genetic Programming and Evolvable Machines, 5(3), pp. 271-290, Sept. 2004.