Time to Optimum for an Evolutionary Algorithm Applie to a Separable Fitness Functions

Alden H. Wright
Computer Science Dept. 
The University of Montana 
Missoula, MT 59812-1008 
wright@cs.umt.edu

INTRODUCTION:

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.