Fun fact: in the field of optimization there are heuristics which are modeled after evolutionary principles. These “evolutionary algorithms” also work with populations, offspring generation through mutation and mating, selective pressure, diversity preservation, and so on.
As a rule of thumb, these algorithms also work better when sexual reproduction is used. For example, a standard theoretical benchmark are monotone functions on bit-strings, where each gene takes only two values zero and one, and flipping a zero into a one gives higher fitness in all situations and environments. This seems like an easy situation to optimize, but asexual algorithm don’t find the optimum (where all genes are one) for exponential time (in the number n of genes) if the mutation rate is large. Algorithms which use mating have no trouble. This comes from Muller’s ratchet. [1]
More remarkably, even if the mutation rate is arbitrarily small, asexual algorithms don’t find the optimum for exponential time if they use populations, where in each round they produce a new offspring and prune the least fit individual. Again, algorithms with mating don’t have these problems. This also comes from a version of Muller’s ratchet, but on population level. Essentially, if there is a beneficial mutation then other mutations have time to accumulate until the beneficial mutation has taken over the whole population, and this takes long enough to accumulate very many bad mutations, even for extremely low mutation rates. [2]
Fun fact: in the field of optimization there are heuristics which are modeled after evolutionary principles. These “evolutionary algorithms” also work with populations, offspring generation through mutation and mating, selective pressure, diversity preservation, and so on.
As a rule of thumb, these algorithms also work better when sexual reproduction is used. For example, a standard theoretical benchmark are monotone functions on bit-strings, where each gene takes only two values zero and one, and flipping a zero into a one gives higher fitness in all situations and environments. This seems like an easy situation to optimize, but asexual algorithm don’t find the optimum (where all genes are one) for exponential time (in the number n of genes) if the mutation rate is large. Algorithms which use mating have no trouble. This comes from Muller’s ratchet. [1]
More remarkably, even if the mutation rate is arbitrarily small, asexual algorithms don’t find the optimum for exponential time if they use populations, where in each round they produce a new offspring and prune the least fit individual. Again, algorithms with mating don’t have these problems. This also comes from a version of Muller’s ratchet, but on population level. Essentially, if there is a beneficial mutation then other mutations have time to accumulate until the beneficial mutation has taken over the whole population, and this takes long enough to accumulate very many bad mutations, even for extremely low mutation rates. [2]
[1] https://link.springer.com/chapter/10.1007/978-3-319-99259-4_1
[2] https://www.sciencedirect.com/science/article/abs/pii/S030439752100178X
(free preprints available on arxiv)
Cool to know, thanks!
Also, free published prints available on sci-hub:
A General Dichotomy of Evolutionary Algorithms on Monotone Functions
Exponential slowdown for larger populations: The (μ + 1)-EA on monotone functions