A Comparative Study of an Evolvability Indicator and a Predictor of Expected Performance for Genetic Programming

Leonardo Trujillo 1 Yuliana Martinez 1 Edgar Galvan-Lopez 2 Pierrick Legrand 3, 4
2 School of Computer Science and Electronic Engineering
CSEE - School of Computer Science and Electronic Engineering [Essex]
4 ALEA - Advanced Learning Evolutionary Algorithms
Inria Bordeaux - Sud-Ouest, UB - Université de Bordeaux, CNRS - Centre National de la Recherche Scientifique : UMR5251
Abstract : One of the main open problems within Genetic Programming (GP) is to meaningfully characterize the difficulty (or hardness) of a problem. The general goal is to develop predictive tools that can allow us to identify how difficult a problem is for a GP system to solve. In this work, we identify and compare two main approaches that address this question. We denote the first group of methods as Evolvability Indicators (EI), which are measures that attempt to capture how amendable the fitness landscape is to a GP search. The best examples of current EIs are the Fitness Distance Correlation (FDC) and the Negative Slope Coefficient (NSC). The second, more recent, group of methods are what we call Predictors of Expected Performance (PEP), which are predictive models that take as input a set of descriptive attributes of a particular problem and produce as output the expected performance of a GP system. The experimental work presented here compares an EI, the NSC, and a PEP model for a GP system applied to data classification. Results suggest that the EI fails at measuring problem difficulty expressed by the performance of the GP classifiers, an unexpected result. On the other hand, the PEP models show a very high correlation with the actual performance of the GP system. It appears that while an EI can correctly estimate the difficulty of a given search, as shown by previous research on this topic, it does not necessarily capture the difficulty of the underlying problem that GP is intended to solve. Conversely, while the PEP models treat the GP system as a computational black-box, they can still provide accurate performance predictions.
Type de document :
Communication dans un congrès
GECCO, Jul 2012, Philadelphie, United States. 2012
Liste complète des métadonnées

Littérature citée [11 références]  Voir  Masquer  Télécharger

Contributeur : Pierrick Legrand <>
Soumis le : lundi 26 novembre 2012 - 16:43:43
Dernière modification le : jeudi 11 janvier 2018 - 06:22:36
Document(s) archivé(s) le : samedi 17 décembre 2016 - 15:18:26


Fichiers produits par l'(les) auteur(s)


  • HAL Id : hal-00757266, version 1



Leonardo Trujillo, Yuliana Martinez, Edgar Galvan-Lopez, Pierrick Legrand. A Comparative Study of an Evolvability Indicator and a Predictor of Expected Performance for Genetic Programming. GECCO, Jul 2012, Philadelphie, United States. 2012. 〈hal-00757266〉



Consultations de la notice


Téléchargements de fichiers