- author = "Mario Graff-Guerrero",
- title = "Models of the Performance of Evolutionary Program Induction Algorithms",
- school = "Department of Computing Science and Electronic Engineering, University of Essex",
- year = "2010",
- address = "UK",
- month = oct,
- keywords = "genetic algorithms, genetic programming, Gene Expression Programming, Cartesian Genetic Programming",
-
URL = "
http://lsc.fie.umich.mx/~mgraffg/phd_thesis.pdf",
- size = "142 pages",
-
abstract = "Evolutionary computation techniques have seen a
considerable popularity as problem solving and
optimisation tools in recent years. Theoreticians have
developed a variety of both exact and approximate
models of evolutionary algorithms. However, these
models are often criticised for being only applicable
to simplistic problems or algorithms with unrealistic
parameters.
Here, we start rectifying this situation in relation to what matters the most to practitioners and users of program induction systems: performance. That is, we introduce some simple and practical models for the performance of program-induction algorithms. To test our approach, we consider two important classes of problems, symbolic regression and Boolean function induction, and we model different versions of Genetic Programming, Gene Expression Programming, Cartesian Genetic Programming and Stochastic Iterated Hill Climbers.
In all cases our models are able to accurately predict the performance of each algorithm on unseen problems. This allows, for example, the use of our models to solve the algorithm selection problem (i.e., the problem of deciding which is the best algorithm to solve a problem) for program induction. Besides performing accurate predictions, we show that our models can help in the analysis and comparison of different algorithms and/or algorithms with different parameters setting. This process, too, can be automatised. We illustrate this via the automatic construction of a taxonomy for the stochastic program induction algorithms considered in this study.
Although our approach was initially aimed at modelling evolutionary program induction algorithms, it is in fact very general and, in principle, can be used to predict the performance of non-evolutionary learning algorithms and problem solvers. To illustrate this, we modelled one well-known training algorithm for artificial neural networks and two common heuristics of the off-line bin packing problem with very encouraging results.",
- notes = "supervisor Riccardo Poli",
