Incorporating expert knowledge in evolutionary search: a study of seeding methods

ABSTRACT

We investigated several methods for utilizing expert knowledge in evolutionary search, and compared their impact on performance and scalability into increasingly complex problems. We collected data over one thousand randomly generated problems. We then simulated collecting expert knowledge for each problem by optimizing an approximated version of the exact solution. We then compared six different methods of seeding the approximate model in to the genetic program, such as using the entire approximate model at once or breaking it into pieces. Contrary to common intuition, we found that inserting the complete expert solution into the population is not the best way to utilize that information; using parts of that solution is often more effective. Additionally, we found that each method scaled differently based on the complexity and accuracy of the approximate solution. Inserting randomized pieces of the approximate solution into the population scaled the best into high complexity problems and was the most invariant to the accuracy of the approximate solution. Furthermore, this method produced the least bloated solutions of all methods. In general, methods that used randomized parameter coefficients scaled best with the approximate error, and methods that inserted entire approximate solutions scaled worst with the problem complexity.

REFERENCES

• 1: J. Moore and B. White, "Exploiting Expert Knowledge in Genetic Programming for Genome-Wide Genetic Analysis," in Parallel Problem Solving from Nature -- PPSN IX, 2006, pp. 969--977.
• 2: Casey S. Greene , Bill C. White , Jason H. Moore, Using expert knowledge in initialization for genome-wide analysis of epistasis using genetic programming, Proceedings of the 10th annual conference on Genetic and evolutionary computation, July 12-16, 2008, Atlanta, GA, USA [doi>10.1145/1389095.1389158]
• 3: W. Banzhaf and J. Miller, "The Challenge of Complexity," in Frontiers of Evolutionary Computation, 2004, pp. 243--260.
• 4: Mohammad-Reza Akbarzadeh-Totonchi , Mohammad Jamshidi, Incorporating A-Priori Expert Knowledge in Genetic Algorithms, Proceedings of the 1997 IEEE International Symposium on Computational Intelligence in Robotics and Automation, p.300, June 10-11, 1997
• 5: John R. Koza, Genetic programming: on the programming of computers by means of natural selection, MIT Press, Cambridge, MA, 1992
• 6: 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.
• 7: 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]
• 8: 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]
• 9: 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.
• 10: 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.
• 11: 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.
• 12: M. D. Schmidt and H. Lipson, "Coevolution of Fitness Predictors," IEEE Transactions on Evolutionary Computation, vol. 12, pp. 736--749, Dec 2008.
• 13: S. W. Mahfoud, "Niching methods for genetic algorithms," University of Illinois at Urbana--Champaign, 1995.

INDEX TERMS

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

General Terms:
Algorithms

Keywords:
prior knowledge, symbolic regression