A discipline of evolutionary programming

Genetic fitness optimization using small populations or small population up dates across generations generally suffers from randomly diverging evolutio ns. We propose a notion of highly probable fitness optimization through fea sible evolutionary computing runs on small-size populations. Based on rapid ly mixing Markov chains, the approach pertains to most types of evolutionar y genetic algorithms, genetic programming and the like. We establish that f or systems having associated rapidly mixing Markov chains and appropriate s tationary distributions the new method finds optimal programs (individuals) with probability almost 1. To make the method useful would require a struc tured design methodology where the development of the program and the guara ntee of the rapidly mixing property go hand in hand. We analyze a simple ex ample to show that the method is implementable. More significant examples r equire theoretical advances, for example with respect to the Metropolis fil ter. (C) 2000 Elsevier Science B.V. All rights reserved.