Evolution with Recombination

Valiant (2007) introduced a computational model of evolution and suggested that Darwinian evolution be studied in the framework of computational learning theory. Valiant describes evolution as a restricted form of learning where exploration is limited to a set of possible mutations and feedback is received through the survival of the fittest mutation. In subsequent work Feldman (2008) showed that evolvability in Valiant's model is equivalent to learning in the correlational statistical query (CSQ) model. We extend Valiant's model to include genetic recombination and show that in certain cases, recombination can significantly speed-up the process of evolution in terms of the number of generations, though at the expense of population size. This follows via a reduction from parallel-CSQ algorithms to evolution with recombination. This gives an exponential speed-up (in terms of the number of generations) over previous known results for evolving conjunctions and half spaces with respect to restricted distributions.

Authors

• Varun Kanade

Keywords

• Polynomials
• Evolution (biology)
• Computational modeling
• Evolutionary computation
• Program processors
• Genetics
• Biological system modeling
• Model Of Evolution
• Evolvability
• Survival Of The Fittest
• Computational Theory
• Darwinian Evolution
• Learning Algorithms
• Population Genetic
• Parallelization
• Evolutionary Algorithms
• Steps Of Development
• Sexual Reproduction
• Deleterious Mutations
• Members Of Population
• Valid Responses
• Fraction Of Population
• Recombination Process
• End Of Step
• Beneficial Mutations
• Parallel Algorithm
• Neutral Mutations
• Parallel Steps
• Boolean Function
• Concept Of Class
• Turing Machine
• Symmetric Product
• Asexual Reproduction
• Real-valued Function
• Natural Selection
• computational learning theory