Bitwise regularity and GA-hardness

Presents a theoretical analysis that relates an irregularity measure of a fitness function to the so-called GA (genetic algorithm) deception. This approach is a continuation of the work of Lutton and Le´vy-Ve´hel (1995) that has presented a deception analysis of Hölder functions. The analysis developed in this paper is a generalization of this work in two ways: first, we use a “bitwise regularity” instead of a Hölder exponent as a basis for our deception analysis; and second, we perform a similar deception analysis of a GA with uniform crossover. We finally propose to use the bitwise regularity coefficients in order to analyse the influence of chromosome encoding on the GA efficiency, and we present experiments with Gray encoding