Discovering a domain alphabet

ABSTRACT

A key to the success of any genetic programming process is the use of a good alphabet of atomic building blocks from which solutions can be evolved efficiently. An alphabet that is too granular may generate an unnecessarily large search space; an inappropriately coarse grained alphabet may bias or prevent finding optimal solutions. Here we introduce a method that automatically identifies a small alphabet for a problem domain. We process solutions on the complexity-optimality Pareto front of a number of sample systems and identify terms that appear significantly more frequently than merited by their size. These terms are then used as basic building blocks to solve new problems in the same problem domain. We demonstrate this process on symbolic regression for a variety of physics problems. The method discovers key terms relating to concepts such as energy and momentum. A significant performance enhancement is demonstrated when these terms are then used as basic building blocks on new physics problems. We suggest that identifying a problem-specific alphabet is key to scaling evolutionary methods to higher complexity systems.

REFERENCES

• 1: John H. Holland, Building Blocks, Cohort Genetic Algorithms, and Hyperplane-Defined Functions, Evolutionary Computation, v.8 n.4, p.373-391, December 2000 [doi>10.1162/106365600568220]
• 2: M. Kotanchek, G. Smits, and E. Vladislavleva, "Trustable symbolic regression models: using ensembles, interval arithmetic and pareto fronts to develop robust and trust-aware models," in Genetic Programming Theory and Practice V, 2008, pp. 201--220.
• 3: John H. Holland, Adaptation in Natural and Artificial Systems: An Introductory Analysis with Applications to Biology, Control and Artificial Intelligence, 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: U.-M. O'Reilly, "The Trouble Aspects of a Building Block Hypothesis for Genetic Programming," Santa Fe Institute Feb 1994.
• 6: J. P. Rosca, "Towards automatic discovery of building blocks in genetic programming," in Working Notes for the AAAI Symposium on Genetic Programming, E. V. Siegel and J. R. Koza, Eds. MIT, Cambridge, MA, USA: AAAI 445 Burgess Drive, Menlo Park, CA 94025, USA, 1995, pp. 78--85.
• 7: N. McPhee, B. Ohs, and T. Hutchison, "Semantic Building Blocks in Genetic Programming," in Genetic Programming, 2008, pp. 134--145.
• 8: John J. Grefenstette, Credit Assignment in Rule Discovery Systems Based on Genetic Algorithms, Machine Learning, v.3 n.2-3, p.225-245, October 1988 [doi>10.1007/BF00113898]
• 9: Carlos M. Fonseca , Peter J. Fleming, Genetic Algorithms for Multiobjective Optimization: FormulationDiscussion and Generalization, Proceedings of the 5th International Conference on Genetic Algorithms, p.416-423, June 01, 1993
• 10: Carlos M. Fonseca , Peter J. Fleming, An overview of evolutionary algorithms in multiobjective optimization, Evolutionary Computation, v.3 n.1, p.1-16, Spring 1995 [doi>10.1162/evco.1995.3.1.1]
• 11: John R. Koza, Genetic programming: on the programming of computers by means of natural selection, MIT Press, Cambridge, MA, 1992
• 12: M. Ben, J. W. Mark, and W. B. Geoffrey, "Using a Tree Structured Genetic Algorithm to Perform Symbolic Regression," in First International Conference on Genetic Algorithms in Engineering Systems: Innovations and Applications, GALESIA. vol. 414, A. M. S. Zalzala, Ed. Sheffield, UK: IEE London, UK, 1995, pp. 487--492.
• 13: Edwin D. De Jong , Jordan B. Pollack, Multi-Objective Methods for Tree Size Control, Genetic Programming and Evolvable Machines, v.4 n.3, p.211-233, September 2003 [doi>10.1023/A:1025122906870]
• 14: Michael Schmidt , Hod Lipson, Comparison of tree and graph encodings as function of problem complexity, Proceedings of the 9th annual conference on Genetic and evolutionary computation, July 07-11, 2007, London, England [doi>10.1145/1276958.1277288]
• 15: X. H. Nguyen, R. I. McKay, and D. L. Essam, "Solving the Symbolic Regression Problem with Tree-Adjunct Grammar Guided Genetic Programming: The Comparative Results," in The Australian Journal of Intelligent Information Processing Systems. vol. 7, 2001, pp. 114--121.
• 16: M. D. Schmidt and H. Lipson, "Coevolution of Fitness Predictors," IEEE Transactions on Evolutionary Computation, vol. 12, pp. 736--749, Dec 2008.
• 17: M. D. Schmidt and H. Lipson, "Coevolution of Fitness Maximizers and Fitness Predictors" in Proceedings of the Genetic and Evolutionary Computation Conference, Late Breaking Paper, 2005.
• 18: M. D. Schmidt and H. Lipson, "Co-evolving Fitness Predictors for Accelerating and Reducing Evaluations," in Genetic Programming Theory and Practice IV. vol. 5, L. R. Rick, S. Terence, and W. Bill, Eds. Ann Arbor: Springer, 2006, pp. 113--130.
• 19: S. W. Mahfoud, "Niching methods for genetic algorithms," University of Illinois at Urbana-Champaign, 1995.
• 20: F. Francisco, S. Giandomenico, T. Marco, and V. Leonardo, "Parallel Genetic Programming," in Parallel Metaheuristics, A. Enrique, Ed. Hoboken, New Jersey, USA: Wiley-Interscience, 2005, pp. 127---153.
• 21: G. Christian, P. Marc, and D. Marc, "A Robust Master-Slave Distribution Architecture for Evolutionary Computations," in Genetic and Evolutionary Computation Conference Late Breaking Papers, R. Bart, Ed. Chicago, USA, 2003, pp. 80--87.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.6 Learning
          Subjects: Knowledge acquisition

General Terms:
Algorithms

Keywords:
building blocks, domain alphabet, symbolic regression