Belgium, Hendrik Blockeel (ed.) Size of Random Programs to ensure Uniformity

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 logN and smaller) are given in [1] for the outputs of five computer models (any, average, cyclic, bit flip and Boolean). Mutation randomises a genetic algorithm population in 1 4 (l + 1)(log(l) + 4) generations. While [2] considers convergence of functions. We restate the results 1 2 N(log(m) + 4) and O(N)–O(N3/2) for a genetic programming (GP) like model. If we generated a large number of random programs and measured their char-acteristics (such as the value they output) this random sample would approximate the characteristics of all programs (Monte Carlo sampling). Instead of actually explicitly generating all these programs, we can apply Markov theory of random processes to random programs, to get properties of the random program and there-fore bulk properties of all programs. Using this we proved that the fitness distribution of sufficiently large programs will eventually converge [3]. However Markov chain theory can also be used to give numeric estimates of the length of random linear genetic programs, such that the distribution of their outputs is independent of their size. The size depend heavily on the type of computer, the fitness function, and scales with the size of the computer’s memory [1]. We have also considered how big programs must be to ensure the proportion of functions they implement is close to the limit [2]