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. R. Caruana. Multitask learning. Mach. Learn., 28(1):41--75, 1997.
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. G. S. Hornby and J. B. Pollack. Creating high-level components with a generative representation for body-brain evolution. Artif. Life, 8(3):223--246, 2002.
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. W. Jaffkowski, K. Krawiec, and B. Wieloch. Knowledge reuse in genetic programming applied to visual learning. In D. Thierens, editor, Genetic and Evolutionary Computation Conference GECCO, pages 1790--1797. Association for Computing Machinery, 2007.
10. J. Koza. Genetic Programming. MIT Press, Cambridge, MA, 1992.
11. J. R. Koza. Genetic Programming II: Automatic Discovery of Reusable Programs. MIT Press, Cambridge Massachusetts, May 1994.
12. J. R. Koza, F. H. Bennett III, D. Andre, and M. A. Keane. Reuse, parameterized reuse, and hierarchical reuse of substructures in evolving electrical circuits using genetic programming. In T. H. et al., editor, Proceedings of International Conference on Evolvable Systems: From Biology to Hardware (ICES-96), volume 1259 of Lecture Notes in Computer Science. Springer-Verlag, 1996.
13. K. Kurashige, T. Fukuda, and H. Hoshino. Reusing primitive and acquired motion knowledge for gait generation of a six-legged robot using genetic programming. Journal of Intelligent and Robotic Systems, 38(1):121--134, Sept. 2003.
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. S. Luke and L. Panait. Lexicographic parsimony pressure. 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, editors, GECCO 2002: Proceedings of the Genetic and Evolutionary Computation Conference, pages 829--836, New York, 9--13 July 2002. Morgan Kaufmann Publishers.
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. S. C. Roberts, D. Howard, and J. R. Koza. Evolving modules in genetic programming by subtree encapsulation. In J. F. M. et al., editor, Genetic Programming, Proceedings of EuroGP'2001, volume 2038 of LNCS, pages 160--175. Springer-Verlag, 2001.
21. J. P. Rosca and D. H. Ballard. Discovery of subroutines in genetic programming. In P. J. Angeline and K. E. Kinnear, Jr., editors, Advances in Genetic Programming 2, chapter 9, pages 177--202. MIT Press, Cambridge, MA, USA, 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. R. Vilalta and Y. Drissi. A perspective view and survey of meta-learning. Artif. Intell. Rev., 18(2):77--95, 2002.
24. D. Wolpert and W. Macready. No free lunch theorems for optimization. IEEE Transactions on Evolutionary Computation, 1(1):67--82, 1997.

Index Terms

• Computing methodologies

  • Artificial intelligence

    • Search methodologies

      • Heuristic function construction