Research Projects

Computational Complexity Analysis of Genetic Programming

One of the challenges of computer science is to get a computer to do what needs to be done, without telling it how this can be accomplished. Genetic Programming addresses this challenge by providing a scheme for automatically building computer programs from a high-level statement of the problem. This is achieved by "breeding" a population of computer programs using the principles of Darwinian natural selection and biologically inspired operations. We refer the interest reader to A Field Guide To Genetic Programming (Poli et al.) for a detailed presentation of GP.

In the last decade, Genetic Programming algorithms have found various applications in a number of domains, such as symbolic regression, financial trading, and bioinformatics. Because of the complexity of genetic programming variants and the challenging nature of the problems they address, it is arguably impossible in most cases to make formal guarantees about the number of fitness evaluations needed for an algorithm to find an optimal solution.

Recently, the first computational complexity results have been presented for simple genetic programming algorithms. Together with researchers at the Massachusetts Institute of Technology and the Max Planck Institute for Informatics, we contribute to the theoretical understanding of genetic programming algorithms, by analyzing the influence of acceptance criteria, mutation behavior, and population sizes on the optimization time needed for different problems.

Software

GPFramework (0.1) is a Java framework for rapid prototyping of mutation-only Genetic Programming systems (mostly, but not exclusively, with the goal to assess their computational complexity). Hosted at: BitBucket (Mercurial), GitHub (Git), and Google Code (Subversion).

Publications

• M. Wagner and F. Neumann (2014): Single- and Multi-Objective Genetic Programming: New Runtime Results for SORTING.
  In: IEEE World Congress on Computational Intelligence: Congress on Evolutionary Computation, WCCI/CEC 2014. (to appear)
  
• A. Q. Nguyen, T. Urli and M. Wagner (2013): Improved Computational Complexity Results for Weighted ORDER and MAJORITY.
  In: Foundations of Genetic Algorithms XII, FOGA 2013.
  
• M. Wagner, F. Neumann (2012): Parsimony Pressure versus Multi-Objective Optimization for Variable Length Representations.
  In: Parallel Problem Solving From Nature, PPSN 2012.
  Available: [Springer]
• T. Urli, M. Wagner, F. Neumann (2012): Experimental Supplements to the Computational Complexity Analysis of Genetic Programming for Problems Modelling Isolated Program Semantics.
  In: Parallel Problem Solving From Nature, PPSN 2012.
  Available: [Springer]
• F. Neumann (2012): Computational complexity analysis of multi-objective genetic programming.
  In: Genetic and Evolutionary Computation Conference, GECCO 2012 (to appear).
  Available: [CoRR abs/1203.4881]
• T. Kötzing, A. M. Sutton, F. Neumann, U.-M. O'Reilly (2012): The Max Problem revisited: the importance of mutation in genetic programming.
  In: Genetic and Evolutionary Computation Conference, GECCO 2012.
  Available: [ACM Digital Library]
• F. Neumann, U.-M. O’Reilly, M. Wagner (2011): Computational complexity analysis of genetic programming - initial results and future directions.
  In: R. Riolo, E. Vladislavleva, J. H. Moore (Eds.): Genetic Programming Theory and Practice IX, Springer, pages 113-128. Final Version
• T. Kötzing, F. Neumann, R. Spöhel (2011): PAC learning and genetic programming.
  In: Genetic and Evolutionary Computation Conference, GECCO 2011.
  Available: [ACM Digital Library]
• M. Wagner, F. Neumann (2011): Computational Complexity Results for Genetic Programming and the Sorting Problem
  Technical Report
  Available: [CoRR abs/1103.5797]
• G. Durrett, F. Neumann, U.-M. O'Reilly (2011): Computational complexity analysis of simple genetic programming on two problems modeling isolated program semantics.
  In: Foundations of Genetic Algorithms XI, FOGA 2011.
  Available: [CoRR abs/1007.4636]