Autori: Giancarlo Mauri and Leonardo Vanneschi
Titolo: Measures to Characterize Search in Evolutionary Algorithms
QD Quaderni – Department of informatics, systems and communication- Research Report n. 3 Novembre 2007
Collana: Tesi e Ricerca
Genere: Informatica
The ability of evolutionary algorithms to solve a combinatorial optimization problem is often very hard to verify. Thus, it would be very useful to have one or more numeric measures able to quantify the ability of evolutionary algorithms to find good quality solutions to a given problem from its high level specifications. In this paper, two difficulty measures are presented: fitness distance correlation and negative slope coefficient. Advantages and drawbacks of both these measures are presented both from a theoretical and empirical point of view for genetic programming. Furthermore, to analyse various properties of the search process of evolutionary algorithms, it is useful to quantify the distance between two individuals. Using operator-based distance measures can make this analysis more accurate and reliable than using distance measures which have no relationship with the genetic operators. This paper also presents a pseudo-distance measure based on subtree crossover for genetic programming. Empirical studies are presented that show the suitability of this measure to dynamically calculate the fitness distance correlation during the evolution, to construct a fitness sharing system for genetic programming and to measure genotypic diversity in the population. Experiments have been performed on a set of well-known hand-tailored problems and “real-life-like” GP benchmarks.
