Limitations of the fitness-proportional negative slope coefficient as a difficulty measure

ABSTRACT

Fitness-Proportional Negative Slope Coefficient is a fitness landscapes measure that has recently been introduced as a potential indicator of problem hardness for optimisation. It is inspired to an older measure, the Negative Slope Coefficient, and it has been theoretically modelled. Preliminary experiments have suggested that it may be a good predictor of problem hardness. However, this measure has not undergone any convincing and comprehensive empirical testing. Our objective is to fill this gap. So, we perform empirical tests using a large set of invertible functions of unitation. We find that while this measure may correctly predict the degree of evolvability of a landscape, this does not necessarily correlate with the difficulty of problems. Some landscapes may show, for example, limited evolvability and yet be easy to solve because either solutions are already present in the initial population or the computational resources provided exceed evolvability obstacles. Or it may be impossible to solve them irrespective of their evolvability simply because they are far too vast for the computational resources provided. These situations are hardly captured by the Fitness-Proportional Negative Slope Coefficient.

REFERENCES

• 1: Terry Jones , Stephanie Forrest, Fitness Distance Correlation as a Measure of Problem Difficulty for Genetic Algorithms, Proceedings of the 6th International Conference on Genetic Algorithms, p.184-192, July 15-19, 1995
• 2: Riccardo Poli , Leonardo Vanneschi, Fitness-proportional negative slope coefficient as a hardness measure for genetic algorithms, Proceedings of the 9th annual conference on Genetic and evolutionary computation, July 07-11, 2007, London, England [doi>10.1145/1276958.1277209]
• 3: L. Vanneschi. Theory and Practice for Efficient Genetic Programming. Ph.D. thesis, Faculty of Science, University of Lausanne, Switzerland, 2004. Downlodable version at: http://personal.disco.unimib.it/Vanneschi.
• 4: S. Verel. Étude et Exploitation des Réseaux de Neutralité dans les Paysages Adaptatifs pour l'Optimisation Difficile. PhD thesis, University of Nice -- Sophia Antipolis, France, 2005. In French Language.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.2 Automatic Programming
          Subjects: Program synthesis

General Terms:
Algorithms, Performance

Keywords:
fitness clouds, fitness landscapes, fitness-proportional negative slope coefficient, problem difficulty