Convergence Rates For The Distribution Of Program Outputs
William B. Langdon · 2002
Fitness distributions (landscapes) of programs tend to a limit as they get bigger. Markov chain convergence theorems give general upper bounds on the linear program sizes needed for convergence. Tight bounds (exponential in N, N log N, and smaller) are given for five computer models (any, average, cyclic, bit flip and Boolean). Mutation randomizes a genetic algorithm population in 0.25 (l+1)(log(l)+4) generations. Results for a genetic programming (GP) like model are confirmed by experiment.