- author = "Mario Graff and Riccardo Poli",
- title = "Practical performance models of algorithms in evolutionary program induction and other domains",
- journal = "Artificial Intelligence",
- volume = "174",
- number = "15",
- pages = "1254--1276",
- year = "2010",
- ISSN = "0004-3702",
-
DOI = "
doi:10.1016/j.artint.2010.07.005",
-
URL = "
http://www.sciencedirect.com/science/article/B6TYF-50KWG15-1/2/3fb87252c46b990fe9a47f5dbd261a82",
- keywords = "genetic algorithms, genetic programming, Evolution algorithms, Program induction, Performance prediction, Algorithm taxonomies, Algorithm selection problem",
-
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 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.
We show that our models, besides performing accurate predictions, can help in the analysis and comparison of different algorithms and/or algorithms with different parameters setting. We illustrate this via the automatic construction of a taxonomy for the stochastic program-induction algorithms considered in this study. The taxonomy reveals important features of these algorithms from the performance point of view, which are not detected by ordinary experimentation.",
