Practical performance models of algorithms in evolutionary program induction and other domains Original Research Article

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 for evolutionary program induction algorithms. However, these models are often criticised for being only applicable to simplistic problems or algorithms with unrealistic parameters. In this paper, 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 a simple and practical model 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 and stochastic iterated hill climbing in program space. We illustrate the generality of our technique by also accurately modelling the performance of a training algorithm for artificial neural networks and two heuristics for the off-line bin packing problem.