ACM Comm 2016 11 Sex as an Algorithm (Notes)

"Sex as an Algorithm" CACM November 2016

Sex as an Algorithm by Adi Livnat and Christos Papadimitriou, p.84-93 Side Bars Charles Babbage on Evolution The Equation that Reconciled Darwin and Mendel The Experts Problem Glossary The Red-Blue Tree Theorem Appendix

Sex as an Algorithm: The Theory of Evolution Under the Lens of Computation

Looking at the mysteries of evolution from a computer science point of view yields some unexpected insights. A survey article comparing Biological Evolution with Evolutionary Computation and Genetic Algorithms.

The article concludes that evolutionary sex fails to produce outstanding individuals. Idiots, evolutionary sex produces great variety among a population, to meet unknown challenges that population will face in the future.

People

1. Charles Babbage
2. Charles Darwin
3. John H. Holland
4. John von Neumann
5. Richard Dawkins
6. Sewall Wright
7. Ronald Fisher
8. John Haldane

Ideas

1. Turning Space Solutions
2. Darwin Space Solutions
3. Genetic Algorithms, starting in the 1970's
4. Genetics described in mathematics starting in the 1920's, R.A. Fisher, J.B.S. Haldane, S. Wright
5. Even bacteria have sex.
6. Evolutionary Algorithms
7. Some species use both asexual and sexual reproduction. Some yeasts reproduce like this.[1]
8. Evolutionary Computation
9. Multiplicative Weights Update Algorithm
10. Only Know Enough (OKE), about evolution so Mutant OS can run in a laboratory.
11. What role does sex play in evolution?
12. What is evolution optimizing, if anything?
13. The Variation Paradox. More variation in the natural world than current theory predicts. Partial answer, genetic mutation is not constant about a life but varies from one spot in the body to the next. For example, human skin on the face and hands changes faster than on the stomach and back.
14. Are mutations completely random?
15. Reconciling Gregor Mendel's genetics and Charles Darwin's evolution. More about the Three Blind Men and the Elephant. More like, they agree, where, how, and how much do they agree?
16. Computer Scientists were inspired and intrigued by evolution, starting with von Neumann.
17. 1950's. Optimization searches developed heuristics. Papadimitriou and Steiglitz published a survey on this in the 1980s.
18. "The evolutionary fitness of each individual solution in the population (that is, the number of children it will have) is proportional to the quantity being maximized in the underlying problem."
    1. Not quite, the grandchild count is more important. Why else are young couples peppered with reproductive questions? This extension includes grandparents, raising the child, teaching the child, and assisting the child throughout its life.
19. Evolution as searching a solution space for a local optima. "Winner take All" is keeping the successful solutions. This is asexual reproduction.
    1. Sexual reproduction would mix two or more successful solution sets.
20. Evolution does not lend itself to all optimization problems. The Traveling Salesman Problem, for example, optimizes distance, stops, and time for a course, not the many-faceted behaviors needed to survive and reproduce in a changing environment. This puts the Traveling Salesman Problem within the Turning Space but outside the Darwin Space.
21. When mutation and recombination are combined. "The evolutionary fitness of each individual solution in the population (that is, the number of children it will have) is proportional to the quantity being maximized in the underlying problem. After many generations, the population will presumably include some excellent solutions."
22. A population, not an individual, evolves, so the optimal solution might require different new traits in the next generation. Many times the maximized traits needed can not be hosted in a single individual. This requires cooperation among the population and from that social interaction.
23. Asexuals, Obligate, only use asexual reproduction, do not exchange genetic material, are extremely rare, and cannot produce child species.
24. "Coming back to the genetic algorithms, several successes in solving actual optimization problems have been reported in the literature, but the general impression seems to prevail that genetic algorithms are far less successful in practice than local search and simulating annealing. If this is true, it is quite remarkable—a great scientific mystery—because in nature the exact opposite happens: Recombination is successful and ubiquitous, while obligate asexual reproduction is extremely rare and struggling."
    1. Same answer, the search for solution fissions at different scales. One is a person solving a problem for a specific situation for a fixed time-slice. The greater is a society solving many problems that change with time.
25. Much in life orbits around sex. Behavior, physical structures, biological reactions. Why?
26. Simulated annealing local search heuristic that escapes local optima by adopting a disadvantageous mutation, if there is a probability the disadvantage will decrease over time.
27. local optima The population is optimized to the local environment and variation ceases.
28. Go with the winners Keeps a solution space, teleporting the individuals that are stuck at local optima to the more promising spots.
29. Sex builds favorable genotype in one generation and destroys it in the next by mixing it half-and-half with a less favorable genotype.
30. Elitism A genetic algorithms stratagem that allows the most successful individuals into the next generation.
31. Sex Queen of problems” in evolutionary biology See G. Bell below.
32. Selecting an allele for fitness as Game Theory.
    1. The genotype's differential fitness ranges from \([-1,+1]\).
    2. The weak selection assumption was used.
    3. Each gene is a player.
    4. Each player, gene, has the same utility function.
       1. Games with identical utilities are called coordination games in Game Theory, and are the simplest possible kind.
    5. Each gene's alleles are its actions.
       1. Each allele is a 'token' in the game.
    6. Each generation is round in the game.
    7. A gene does not have a brain, mind, or cognition. Therefore the only strategy available is a mechanical shuffling based on weighted probability.
       1. The probability assigned to each allele corresponds to how often the allele occurs in the population during this generation.
    8. Game Theory centers on conflicting objectives among the players.
       1. The players here, in sexual or asexual gene selection, have no conflict in Game Theory terms.
    9. The update rule used is the Multiplicative Weights Update Algorithm (MWU) also known in machine learning as "no-regret learning" or "hedge".
    10. MWU changes the fequencies \(x_{i}\) for the \(i\)-th allele from the gene as follows:
        1. \(x_{i} \leftarrow x_{i} (1+sm_{i})\) Equation (1)
        2. \(m_[i}\) is the mixability for each allele \(i\), its ability to form viable combinations with alleles from other genes in the current genetic mix.
    11. The allele frequencies chosen by gene in Equation (1) optimizes Equation (2), below, optimizes the equation given in the Darwin and Mendel sidebar.
        1. $$\Phi (x) =\sum_{i}x_{i}M_{i}- \frac{1}{s}\sum_{i}x_{i}\ln\:x_{i}\: \text{ Equation (2) Where: }$$
           1. \(M_{i}\) is the cumulative relative fitness for allele \(i\). That is, the sum for \(m_{i}\) in Equation (1) over all generations including \(t-1\).
           2. \(\Phi\) is a strictly concave function with one maximum.
           3. \(\frac{1}{s}\sum_{i}x_{i}\ln\:x_{i}\) is the entropy for \(x\)'s distribution, which measures the distribution's diversity.
        2. This means the utility tests an allele's fitness over all previous generations since it was created.

References

1. Origin of Species - Charles Darwin 1859-72
2. Jong, K.A.D. Evolutionary Computation: A Unified Approach. MIT Press, Cambridge MA, 2006 - Artificial Life as studying evolution by exposing its mechanisms.
3. Leslie Valiant first wrote on his theory of evolvability, another attempt at understanding evolution in computational terms Probably Approximately Correct: Nature’s Algorithms for Learning and Prospering in a Complex World. Basic Books, 2013.
4. Papadimitriou, C. and Steiglitz, K. Combinatorial Optimization: Algorithms and Complexity. Dover, 1998.
5. Bell, G. The Masterpiece of Nature: The Evolution and Genetics of Sexuality. University of California Press, Berkeley, CA, 1982.
6. "In asexual evolution, the best combination of alleles always prevails. In the presence of sex, however, natural selection favors “mixable” alleles, those alleles that, even though they may not participate in any truly great genetic combinations, perform adequately across a wide variety of different combinations. p. 23–26"
7. Mutation distribution throughout a population. In asexual species a mutation continues down one blood-line and not through the entire population. Producing a valid test requires the mutation be inserted many times over many generations. In a sexual species a mutation in one member once, after log n generations, where n is the genes which the allele interacts, all possible genetic combinations that could reasonably be constructed will be sampled. "What is more, evolution under sex not only decides among the competing hypotheses (which allele performs better), but also implements this decision (eventually, and with high probability, it will fix the winner)." Searches, finds the best solution, and implements that solution all at the same time. Godlike efficiency
8. Randomized Algorithms
9. weak selection evolutionary - fitness differences between genotypes are small.
10. Optimized Quantity What quantity does evolution optimize? So far no one has found it. Most likely, it does not optimize any one thing but fitness for the overall population.
11. Livnat, A. Interaction-based evolution: How natural selection and nonrandom mutation work together. Biology Direct 8, 1 (2013), p. 24.
12. Wright, S. The distribution of gene frequencies in populations. In Proceedings of the National Academy of Sciences of the United States of America, 23, 6 (1937), p. 307–320.

Internal Links

Parent Article: Reading Notes