Fitness landscapes and problem hardness in genetic programming

ABSTRACT

The performance of searching agents, or metaheuristics, like evolutionary algorithms (genetics algorithms, genetic programming, etc.) or local search algorithms (simulated annealing, tabu search, etc.) depend on some properties of the search space structure. One concept that allows us to analyse the search space is the fitness landscape. In the case of Genetic Programming, defining and handling fitness landscapes is a particularly hard task, given the complexity of the structures being evolved of the genetic operators used. This tutorial presents some general definitions of fitness landscape. Subsequently, we will try to instantiate the concept of fitness landscape to Genetic Programming, discussing problems. The concept of landcsape geometry will be introduced and some of the most common landscape geometries and the dynamics of Genetic Programming on those landscapes will be discussed. After that, the binding between fitness landscapes and problem difficulty will be discussed and a set of measures that characterize the difficulty of a metaheuristic in searching solutions in a fitness landscape are analysed. Among those measures, particular relevance will be given to Fitness Distance Correlation (FDC), Negative Slope Coefficient (NSC), a set of measures bound to the concept of Neutrality and some distance metrics and/or similarity measures that are consistent with the most commonly used genetic operators (in particular the recently defined subtree crossover based distance). Finally, some open questions about fitness landscapes are discussed.

REFERENCES

• 1: Jason M. Daida , Robert R. Bertram , Stephen A. Stanhope , Jonathan C. Khoo , Shahbaz A. Chaudhary , Omer A. Chaudhri , John A. Ii Polito, What Makes a Problem GP-Hard? Analysis of a Tunably Difficult Problem in Genetic Programming, Genetic Programming and Evolvable Machines, v.2 n.2, p.165-191, June 2001 [doi>10.1023/A:1011504414730]
• 2: J. M. Daida, H. Li, R. Tang, A. M. Hilss What makes a problem GP-hard? Validating a hypothesis of structural causes. In R. Poli et al. editors Genetic and Evolutionary Computation - GECCO-2003, volume 2724 of LNCS, pages 1665-1677. Springer-Verlag, Berlin.
• 3: K. E. Kinnear Fitness landscapes and difficulty in genetic programming. In Proceedings of the First IEEE Conference on Evolutionary Computing, pages 142-147. IEEE Press, Piscataway, NY.
• 4: John R. Koza , James P. Rice, Genetic programming (videotape): the movie, MIT Press, Cambridge, MA, 1992
• 5: Foundations of genetic programming, Springer-Verlag New York, Inc., New York, NY, 2002
• 6: Nikolay I. Nikolaev , Vanio Slavov, Concepts of Inductive Genetic Programming, Proceedings of the First European Workshop on Genetic Programming, p.49-59, April 14-15, 1998
• 7: Marco Tomassini , Leonardo Vanneschi , Philippe Collard , Manuel Clergue, A Study of Fitness Distance Correlation as a Difficulty Measure in Genetic Programming, Evolutionary Computation, v.13 n.2, p.213-239, June 2005 [doi>10.1162/1063656054088549]
• 8: L. Vanneschi, M. Tomassini, P. Collard, S. Verel Negative Slope Coefficient. A measure to characterize genetic programming fitness landscapes In P. Collet et al. editors, Genetic Programming, 9th European Conference, EuroGP 2006, pages 178-189, Lecture Notes in Computer Science. 2006.
• 9: L. Vanneschi, S. Gustafson, G. Mauri Using subtree crossover distance to investigate genetic programming dynamics In P. Collet et al. editors, Genetic Programming, 9th European Conference, EuroGP 2006, pages 238-249, Lecture Notes in Computer Science. 2006.
• 10: Tina Yu , Julian F. Miller, Neutrality and the Evolvability of Boolean Function Landscape, Proceedings of the 4th European Conference on Genetic Programming, p.204-217, April 18-20, 2001
• 11: W. B. Langdon and R. Poli, Why Ants are Hard. In Genetic Programming 1998: Proceedings of the Third Annual Conference Morgan Kaufmann, J. R. Koza et al. editors, pages = 193-201, 1998.
• 12: Steven Gustafson , Anikó Ekárt , Edmund Burke , Graham Kendall, Problem Difficulty and Code Growth in Genetic Programming, Genetic Programming and Evolvable Machines, v.5 n.3, p.271-290, September 2004 [doi>10.1023/B:GENP.0000030194.98244.e3]

INDEX TERMS

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

General Terms:
Algorithms, Performance, Theory

Keywords:
fitness landscapes, genetic programming, problem hardness