Local regularity of fitness landscapes and the performance of a simple ES

We present a theoretical and experimental analysis of the influence of the local irregularity of the fitness function on the behavior of an (1+1)ES. Previous work on this subject suggests that the performance of an EA strongly depends on the irregularity of the fitness function. Several irregularity measures have been derived for discrete search spaces, in order to numerically characterize this type of difficulty for EA. These characterizations are mainly based on Holder exponents. Previous studies used however a global characterization of fitness regularity (the global Holder exponent), with experimental validations being conducted on test functions with uniform regularity. This work is extended here in two ways: Results are now stated for continuous search spaces, and pointwise instead of global irregularity is considered. In addition, we present a way to modify the genetic topology to accommodate for variable regularity: the mutation radius, which controls the size of the neighbourhood of a point, is allowed to vary according to the local irregularity of the fitness function. These results are explained through a simple theoretical analysis which gives a relation between the pointwise Holder exponent and the optimal mutation radius. Several questions connected to on-line measurements and usage of regularity in EAs are raised.