|
NeuroCOLT
Technical Report NC-TR-97-005
Genetic
Fitness Optimization
Using Rapidly Mixing Markov Chains
Paul
Vitänyi
CWI, Amsterdam
The Netherlands
Abstract
A notion of highly probable fitness optimization through evolutionary
computing runs on small size populations in a very general setting
is proposed. This has applications to evolutionary learning. Based
on rapidly mixing Markov chains, the approach pertains to most types
of evolutionary genetic algorithms, genetic programming and the like.
For systems having associated rapidly mixing Markov chains and appropriate
stationary distributions the new method finds optimal programs (individuals)
with probability almost 1. Algorithmically, the novel approach prescribes
a strategy of executing many short computation runs, rather than one
long computation run. Given an arbitrary evolutionary program it may
be infeasible to determine whether its associated matrix is rapidly
mixing. In our proposed structured evolutionary program discipline,
the development of the program and the guaranty of the rapidly mixing
property go hand in hand. We conclude with a tentative toy example.
Download Compressed Postscript
|