Skip to Main content Skip to Navigation
Conference papers

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.
Complete list of metadata

Cited literature [11 references]  Display  Hide  Download
Contributor : Pierrick Legrand Connect in order to contact the contributor
Submitted on : Monday, November 26, 2012 - 4:43:43 PM
Last modification on : Friday, December 3, 2021 - 12:20:04 PM
Long-term archiving on: : Saturday, December 17, 2016 - 3:18:26 PM


Files produced by the author(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. ⟨hal-00757266⟩



Les métriques sont temporairement indisponibles