CENTRE DE MATHEMATIQUES APPLIQUEES 
         C.M.A.P.  

Some Facts about So Called GA-Hardness Measures
Bart NaudtsLeila Kallel

In this paper we take a closer look at a number of so called
GA-hardness measures, amongst which epistasis variance and fitness
distance correlation are the better known.

By generalizing the reference classes of the latter two measures, we
are able to overcome their sensitivity to non-linear scaling. This
results in the definition of measure which is more realistic with
respect to the behavior of a genetic algorithm (GA).

We show that the values of epistasis variance, epistasis correlation,
fitness distance correlation and the site-wise optimization measure
can be unreliable and entirely uncorrelated to convergence quality and
convergence speed of the genetic algorithm on the fitness function in
question, irrespective of the latter being an easy or a hard one.

We give an overview of the relation between the reference classes of
the four measures and a number of intuitive GA-easiness classes, in
which we also locate our examples.
 

The whole paper is available as a compressed Postscript file by internet
procedure FTP anonymous on host barbes.polytechnique.fr ( 129.104.4.100)
in the directory pub/RI/1998 under the name

        naudts_kallel_379.mars.ps
or by Netscape or any other www client
via the CMAP www server http://www.cmap.polytechnique.fr