Background
Today I read an article from the November issue of Communications of the ACM, Sex As An Algorithm: The theory of evolution under the lens of computation by Adi Livnat and Chistos Papadimitriou.
In the online edition, the article is accompanied by this video:
Biology
The authors begin with a brief history of the theories of evolution. Of course the first name was Charles Darwin, who delivered three contributions: the insight that evolution is driven by natural selection; the articulation of the hypothesis of common descent (the idea that multiple species come from a single species.); and a forceful and persuasive argument in his book, On the Origin of Species by Means of Natural Selection. Darwin, however, knew nothing about genetics, and he wrote about the reason for sex that it is, "the whole subject is as yet hidden in darkness."
The next big leap was Mendel, who discovered genes. This led to a puzzle forty years later when Mendel's description of genes seemed to be in conflict with Darwin's ideas. The puzzle, however, was resolved by Fisher, Haldane, and Wright, who developed equations to predict changes to populations over time using Mendel's ideas. These equations reconciled the seeming discrepancies between Darwin and Mendel.
Even after decades of refinement of these ideas, there are still open questions. The authors listed four of them:
What is the role of sex in evolution.
Sex is virtually ubiquitous in nature, in fact, from birds' courtship dances to stag fights to all the drama surrounding human relationships, sex is centrally positioned throughout life, but experts cannot agree on its purpose. In evolutionary biology, this has been referred to as, "The Queen of Problems."What exactly is evolution optimizing if anything?
This question is of interest to computer scientists as well as biologists, because of the field of study known as evolutionary algorithms.Why does the paradox of variation exist?
The variation of nature is higher than what the mathematical theory predicts. Why?Are mutations completely random?
It is apparent that mutations have non-uniform distributions, but it's not clear whether that is completely random.
Computer Science
Computer scientists have been inspired by biological evolution since the beginning of the field, perhaps beginning with John Von Neumann. Early versions of mutation were applied to local search optimizations for problems like the Travelling sales person (TSP). Computer scientists would throw populations of solvers at the problem, then in order to get "unstuck", they adopted various mechanisms. These included random starting points, simulated annealing, and eventually "go with the winners." It is noteworthy, however, that these solutions are all asexual.
In the 1970s, computer scientists began experimenting with genetic algorithms, also known as evolutionary algorithms or evolutionary computation. These algorithms were sexual in nature, in that they depended on mutation and recombination of algorithms. This spread widely and was found to be useful for studying evolution, but recombination is difficult, and the technique was not often successful for optimization problems like the TSP. This leads back to one of the author's four questions. Why is sexual evolution so common in nature when it doesn't seem to be good at optimization? Why does sex even need to exist, let alone be so prevalent?
Eventually, Valiant developed a theory of evolvability, which is an attempt to see evolution in computational terms. Under this paradigm, evolution is viewed as an approximation to an ideal fitness function in a particular type of population over many generations. Two noteworthy aspects of this theory are that it did not incorporate recombination (sex) and it applies to statistical learning functions.
Game Theory
On Sex as a Randomized Algorithm
One theory of why sex is used is to find favorable gene combinations, but the problem with that theory is that, once found, the technique also destroys favorable gene combinations.
Against that backdrop, the authors collaborated with biologists and computer scientists and examined the standard equations for evolution and they uncovered some interesting and surprising findings. By examining the equations in their standard forms, the authors were able to determine that asexual reproduction optimizes alleles (mutated genes) that are particularly well suited for a purpose, whereas sexual reproduction promotes a diverse set of alleles that are "good enough" - The "jack of all trades, master of none" - so to speak. So sexual reproduction produces the higher average level of fitness, although it may not produce as many top-performers.
So the authors came to view sex as a randomized algorithm, and it just so happens that computer scientists are often very fond of randomized algorithms. These algorithms can be used to avoid worst case solutions, to create variety, and to force decisions between comparable choices. And this begins to explain why sexual reproduction might be favored by nature. Testing mutations through asexual reproduction requires an exhaustive search. It is computationally expensive. In contrast, randomness means that testing mutations through sexual reproduction is computationally efficient. As the authors put it,
Sex enables evolution to sample quickly from the entire space of genetic computations, in the distribution under which they appear in the population. What is more, evolution under sex not only decides among the competing hypotheses, but also implements this decision.
On Sex as a Game Between Genes
The authors found that if they viewed the standard equations for evolution with a particular assumption (the weak selection assumption), it leads to a description of a novel process which describes a "game" in the context of game theory, and which provides some new insight.
In this game, the players are the alleles. They all have the same utility function, and they follow the following process:
- The game is carried out between many genes, and it's repeated over many rounds.
- Each round, each gene chooses and plays a randomized mixing strategy.
- Players must update their strategy from one round to the next.
And it was at this point that the authors found a big surprise. The update strategy that's used in the game is identical to a well-known, widely-studied learning algorithm, known as the multiplicative weights update (MWU) algorithm. What a surprise to be studying biology and find something from a totally independent area of computer science!
By placing evolution in the context of the MWU equations, the authors were able to make some progress on one of our open questions from the beginning: "What exactly is evolution optimizing if anything?" While they did not find what is being optimized, they were able to conclude that whatever is optimized is optimized for diversity. Another surprising insight from the MWU equation is that current generations retain memories of the performance from past generations.
One final fact also caught my attention. The number of generations through all of life's 3.5 billion years is thought to be one trillion. Now, this is a big number, but computers routinely run trillions of simulations. In computational terms, it's really not very big. How amazing is it that a randomized algorithm is powerful enough to produce all of the complexity and diversity that we see in nature?
