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.