Time to Optimum for an Evolutionary Algorithm Applie to a Separable
Alden H. Wright
Computer Science Dept.
The University of Montana
Missoula, MT 59812-1008
We derive the expected number of iterations needed for a macromutational
hillclimbing algorithm to find a string of optimal fitness for a class
of fitness functions over fixed length binary strings. The
macromutational hillclimbing algorithm (a $1+1$ evolution strategy
algorithm) uses a mutation operator that mutates bits in a substring
of the bit string.
The class of functions is a subclass of the class of block separable
fitness functions. To define a block separable fitness function, we
partition the bit string into nonoverlaping substrings, or blocks.
Then the function can be decomposed into a sum of functions, each of
which depends only on the bits of one of the blocks. These functions
include the deceptive and easy functions used by Goldberg and his
coworkers, and a simple version of the Royal Road fitness function.