The Negative Slope Coefficient (nsc) is an empirical measure of problem hardness based on the analysis of offspring-fitness vs. parent-fitness scatterplots. The nsc has been tested empirically on a large variety problems showing considerable reliability in distinguishing easy from hard problems. However, neither a theoretical justification nor a theoretical analysis of the nsc have ever been given. This paper presents a modification of nsc, the fitness-proportional negative slope coefficient (fpncs), for which it is possible to give a theoretical explanation and analysis. To illustrate the approach we compute fpnsc theoretically for the class of invertible functions of unitation, and for two mutation operators. We apply the theory to compute fpnsc for three benchmark functions: Onemax, Trap and Onemix. We then compare the predictions of fpnsc with the success probability recorded in actual runs. The results suggest that fpnsc is able to broadly discriminate between easy and hard GA problems. Copyright 2007 ACM.
|Citazione:||Poli, R., & Vanneschi, L. (2007). Fitness-proportional negative slope coefficient as a hardness measure for genetic algorithms. In Genetic and Evolutionary Computation Conference - GECCO 2007 (pp.1335-1342).|
|Carattere della pubblicazione:||Scientifica|
|Titolo:||Fitness-proportional negative slope coefficient as a hardness measure for genetic algorithms|
|Autori:||Poli, R; Vanneschi, L|
|Data di pubblicazione:||2007|
|Nome del convegno:||Genetic and Evolutionary Computation Conference - GECCO 2007|
|Appare nelle tipologie:||02 - Intervento a convegno|