On Evolvability: The Swapping Algorithm,
Product Distributions, and Covariance
- Gyorgy Turan
||Valiant recently introduced a learning theoretic framework for
evolution, and showed that his swapping algorithm evolves monotone
conjunctions efficiently over the uniform distribution. We continue
the study of the swapping algorithm for monotone conjunctions. A modified
presentation is given for the uniform distribution, which leads to a
characterization of best approximations, a simplified analysis and
improved complexity bounds. It is shown that for product distributions
a similar characterization does not hold, and there may be local optima
of the fitness function. However, the characterization holds if the
correlation fitness function is replaced by covariance. Evolvability
results are given for product distributions using the covariance fitness
function, assuming either arbitrary tolerances, or a non-degeneracy
condition for the distribution and a size bound on the target.
Key words: learning, evolution.
Last updated: November 7, 2009.