event
Thursday 06 Feb 2014: Evolution: An Algorithmic Perspective
Dr Per Kristian Lehre - University of Nottingham
Harrison 103 15:00-16:00
Computer scientists have decades of experience in simulating
evolutionary processes. Such simulations, often called evolutionary
algorithms, are usually carried out to find solutions to a wide range of
real-world problems, such as vehicle routing problems, timetabling
problems, and other hard combinatorial optimisation problems.
The theory of evolutionary algorithms which has been developed over the
last ten years differs significantly from population genetics and other
theories of evolution. Rooted in the analysis of algorithms and
computational complexity theory, it mainly focuses on the speed of
adaptation. In particular, the theory attempts to characterise the
conditions under which evolutionary algorithms can find good solutions
to optimisation problems efficiently. Such an algorithmic perspective
may give new insights into evolution in general.
In this talk, we approach the problem of quantifying the amount of
information required for a population to efficiently adapt to its
environment. Two information-restricted scenarios are considered. In
partial evaluation of individuals, the fitness of an individual is
determined only by a restricted number of randomly selected
characteristics of the individual. In partial evaluation of
populations, every individual in the population has the same fitness,
except a few randomly selected individuals who must compete for
resources. In both scenarios, the fitness of an individual correlates
only weakly with how well it is adapted to its environment, thus
restricting the amount of information available. We prove that given a
sufficiently large population and a sufficiently small mutation rate,
asexually reproducing populations can adapt efficiently to the
environment, even when arbitrary little information is available.
