Research Repository

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

Graff, Mario and Poli, Riccardo (2010) 'Practical performance models of algorithms in evolutionary program induction and other domains.' Artificial Intelligence, 174 (15). pp. 1254-1276. ISSN 0004-3702

Full text not available from this repository.


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. © 2010 Elsevier B.V. All rights reserved.

Item Type: Article
Uncontrolled Keywords: Evolution algorithms; Program induction; Performance prediction; Algorithm taxonomies; Algorithm selection problem
Subjects: Q Science > QA Mathematics > QA75 Electronic computers. Computer science
Q Science > QH Natural history > QH426 Genetics
Divisions: Faculty of Science and Health
Faculty of Science and Health > Computer Science and Electronic Engineering, School of
SWORD Depositor: Elements
Depositing User: Elements
Date Deposited: 05 Mar 2013 14:58
Last Modified: 18 Aug 2022 11:13

Actions (login required)

View Item View Item