Multi-task code reuse in genetic programming

ABSTRACT

We propose a method of knowledge reuse between evolutionary processes that solve different optimization tasks. We define the method in the framework of tree-based genetic programming (GP) and implement it as code reuse between GP trees that evolve in parallel in separate populations delegated to particular tasks. The technical means of code reuse is a crossbreeding operator which works very similar to standard tree-swapping crossover. We consider two variants of this operator, which differ in the way they handle the incompatibility of terminals between the considered problems. In the experimental part we demonstrate that such code reuse is usually beneficial and leads to success rate improvements when solving the common boolean benchmarks.

REFERENCES

• 1: A. Bajurnow and V. Ciesielski. Layered learning for evolving goal scoring behavior in soccer players. In Proceedings of the 2004 IEEE Congress on Evolutionary Computation, pages 1828--1835, Portland, Oregon, 20--23 June 2004. IEEE Press.
• 2: Rich Caruana, Multitask Learning, Machine Learning, v.28 n.1, p.41-75, July 1997 [doi>10.1023/A:1007379606734]
• 3: E. Galvan Lopez, R. Poli, and C. A. Coello Coello. Reusing code in genetic programming. In M. Keijzer, U.-M. O'Reilly, S. M. Lucas, E. Costa, and T. Soule, editors, Genetic Programming 7th European Conference, EuroGP 2004, Proceedings, volume 3003 of LNCS, pages 359--368, Coimbra, Portugal, 5--7 Apr. 2004. Springer-Verlag.
• 4: J. Ghosn and Y. Bengio. Bias learning, knowledge sharing. ijcnn, 01:1009, 2000.
• 5: T. Haynes. On-line adaptation of search via knowledge reuse. In J. R. Koza, K. Deb, M. Dorigo, D. B. Fogel, M. Garzon, H. Iba, and R. L. Riolo, editors, Genetic Programming 1997: Proceedings of the Second Annual Conference, pages 156--161, Stanford University, CA, USA, 13--16 July 1997. Morgan Kaufmann.
• 6: Gregory S. Hornby , Jordan B. Pollack, Creating high-level components with a generative representation for body-brain evolution, Artificial Life, v.8 n.3, p.223-246, 2002 [doi>10.1162/106454602320991837]
• 7: D. Howard. Modularization by multi-run frequency driven subtree encapsulation. In R. L. Riolo and B. Worzel, editors, Genetic Programming Theory and Practise, chapter 10, pages 155--172. Kluwer, 2003.
• 8: W. H. Hsu, S. J. Harmon, E. Rodriguez, and C. Zhong. Empirical comparison of incremental reuse strategies in genetic programming for keep-away soccer. In M. Keijzer, editor, Late Breaking Papers at the 2004 Genetic and Evolutionary Computation Conference, Seattle, Washington, USA, 26 July 2004.
• 9: Wojciech Jaskowski , Krzysztof Krawiec , Bartosz Wieloch, Knowledge reuse in genetic programming applied to visual learning, Proceedings of the 9th annual conference on Genetic and evolutionary computation, July 07-11, 2007, London, England [doi>10.1145/1276958.1277318]
• 10: John R. Koza , James P. Rice, Genetic programming (videotape): the movie, MIT Press, Cambridge, MA, 1992
• 11: John R. Koza, Genetic programming II: automatic discovery of reusable programs, MIT Press, Cambridge, MA, 1994
• 12: John R. Koza , Forrest H. Bennett, III , David Andre , Martin A. Keane, Reuse, Parameterized Reuse, and Hierarchical Reuse of Substructures in Evolving Electrical Circuits Using Genetic Programming, Proceedings of the First International Conference on Evolvable Systems: From Biology to Hardware, p.312-326, October 07-08, 1996
• 13: Kentarou Kurashige , Toshio Fukuda , Haruo Hoshino, Reusing Primitive and Acquired Motion Knowledge for Gait Generation of a Six-legged Robot Using Genetic Programming, Journal of Intelligent and Robotic Systems, v.38 n.1, p.121-134, September 2003 [doi>10.1023/A:1026204313001]
• 14: S. Louis and J. McDonnell. Learning with case-injected genetic algorithms. Evolutionary Computation, IEEE Transactions on, 8(4):316--328, 2004.
• 15: S. Luke. ECJ evolutionary computation system, 2002. (http://cs.gmu.edu/ eclab/projects/ecj/).
• 16: Sean Luke , Liviu Panait, Lexicographic Parsimony Pressure, Proceedings of the Genetic and Evolutionary Computation Conference, p.829-836, July 09-13, 2002
• 17: T. M. Mitchell. The discipline of machine learning. Technical Report CMU-ML-06-108, Machine Learning Department, Carnegie Mellon University, July 2006.
• 18: J. O'Sullivan and S. Thrun. A robot that improves its ability to learn, 1995.
• 19: L. Y. Pratt, J. Mostow, and C. A. Kamm. Direct Transfer of Learned Information among Neural Networks. In Proceedings of the Ninth National Conference on Artificial Intelligence (AAAI-91), pages 584--589. AAAI, July 1991.
• 20: Simon C. Roberts , Daniel Howard , John R. Koza, Evolving Modules in Genetic Programming by Subtree Encapsulation, Proceedings of the 4th European Conference on Genetic Programming, p.160-175, April 18-20, 2001
• 21: Justinian P. Rosca , Dana H. Ballard, Discovery of subroutines in genetic programming, Advances in genetic programming: volume 2, MIT Press, Cambridge, MA, 1996
• 22: G. Seront. External concepts reuse in genetic programming. In E. V. Siegel and J. R. Koza, editors, Working Notes for the AAAI Symposium on Genetic Programming, pages 94.98, MIT, Cambridge, MA, USA, 10--12 Nov. 1995. AAAI.
• 23: Ricardo Vilalta , Youssef Drissi, A perspective view and survey of meta-learning, Artificial Intelligence Review, v.18 n.2, p.77-95, October 2002 [doi>10.1023/A:1019956318069]
• 24: D. Wolpert and W. Macready. No free lunch theorems for optimization. IEEE Transactions on Evolutionary Computation, 1(1):67--82, 1997.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.8 Problem Solving, Control Methods, and Search
          Subjects: Heuristic methods

General Terms:
Algorithms

Keywords:
code reuse, genetic programming, multi-task learning