Communications of the ACM
Sex as an Algorithm: The Theory of Evolution Under the Lens of Computation
Credit: Armin Staudt
Look around you, and you will be stunned by the work of evolution. According to Nobel Laureate Jacques Monod, a strange thing about evolution is that all educated persons think they understand it fairly well, and yet very few—if any, one may grumble—actually do. Understanding evolution is essential: "Nothing in biology makes sense except in the light of evolution," famously said the eminent 20th century biologist Theodosius Dobzhansky. And evolution is closer to home than black holes and other mysteries of science—it feels almost like your family history.
Key Insights
More so than most scientific fields, the theory of evolution has a sharp beginning: the publication of Charles Darwin's The Origin of Species in 1859.8 But of course nothing is that simple: during the first half of the 19th century, several scientists were convinced the diversity of life we see around us must be the result of evolution (see the sidebar on Charles Babbage and the accompanying figure). Darwin's immense contribution lies in three things: His identification of natural selection as the engine of evolution; his articulation of the common descent hypothesis, stating that different species came from common ancestors, and further implying that all life came from a common source; and the unparalleled force of argument with which he empowered his theory. But of course The Origin was far from the last word on the subject: Darwin knew nothing about genetics, and had no clue about the role of sex in evolution, among several important gaps. On the ultimate reason for sex, for instance, he wrote, "the whole subject is as yet hidden in darkness."
Comments
CACM Administrator
The following letters were published in the Letters to the Editor in the February 2017 CACM (http://cacm.acm.org/magazines/2017/2/212426).
--CACM Administrator
In "Sex as an Algorithm: The Theory of Evolution Under the Lens of Computation" (Nov. 2016), Adi Livnat and Christos Papadimitriou argued eloquently that the extraordinary success of sexual evolution has not been adequately explained. Somewhat paradoxically, they concluded that sex is not particularly well suited to the task of generating "outstanding individuals." They also said that genetic algorithms are similarly ill suited to this task.
It should be noted that this critique of genetic algorithms widely used derivative free optimization heuristics modeled on recombinative evolution stands in counterpoint to a voluminous empirical record of practical successes. It also speaks to the long-standing absence of consensus among evolutionary computation theorists regarding the abstract workings of genetic algorithms and the general conditions under which genetic algorithms outperform local search. A consensus on these matters promises to shed light on the question the authors originally aimed to answer: Why does recombinative evolution generate populations with outstanding individuals?
Generative hypomixability elimination(1) is a recent theory that addresses this question, positing that genetic algorithms efficiently implement a decimation heuristic that generates fitter populations over time by iteratively eliminating the joint entropy of small collections of "hypomixable loci," or loci in which alleles do not mix well. Recombination, or mixing, allows such loci to go to fixation even as it safeguards the marginal entropy of non-interacting loci.
Taking a step back, one might ask how this theory and the theory proposed by Livnat and Papadimitriou might be evaluated. Proof of soundness, wherever possible, is always desirable, but end-to-end proof can be elusive when analyzing computation in biological systems like brains and evolving populations. We must instead use the scientific method(2), an approach undergirded by the following rule:
hypothesis ==> prediction prediction ==> hypothesis
Unlike the foundations of, say, physics, the foundations of computer science are logically verifiable; hypotheses play no part. So, while computer scientists have seen engineering revolutions aplenty, they have seen nothing like the transition from a Newtonian universe to an Einsteinian universe or from the phlogiston theory of combustion to Lavoisier's oxygen-based theory or any of the other foundational shifts described in Thomas Kuhn's Structure of Scientific Revolutions. Theoretical physicists, chemists, and biologists trained informally, if not formally, in the application of the scientific method know how to evaluate and work with competing hypotheses. The same cannot be said of theoretical computer scientists today. For them, the scientific method is unfamiliar terrain, with different rules and alternate notions of rigor. For example, assumptions must be weak, and hypotheses testable.
For all computer science as a field has to contribute to the natural sciences, it also has much to learn.
Keki M. Burjorjee
Berkeley, CA
----------------------------------------------------
REFERENCES
(1) Burjorjee, K.M. Hypomixability elimination in evolutionary systems. In Proceedings of the 13th Foundations of Genetic Algorithms Conference (Aberystwyth, U.K., Jan. 1720). ACM Press, New York, 2015, 163175.
(2) Popper, K. The Logic of Scientific Discovery. Routledge, London, U.K., 2007.
----------------------------------------------------
While Adi Livnat and Christos Papadimitriou's article (Nov. 2016) provided the rationale for a provocative magazine cover, the article itself began with a false claim and ignored a much simpler explanation for the success of sexual evolution. Shortly after life appeared on Earth, approximately 3.8 billion years ago, evolution began diversifying lifeforms in a very pragmatic way, with mutations that increased the ability of individuals to survive and reproduce being passed along to future generations, whereas those that were disadvantageous were naturally dropped. This process soon discovered that sexual reproduction worked better than simply subdividing, in that it allows advantageous mutations that occur in different families to be combined, allowing evolution to proceed more rapidly, whereas subdividing does not allow it. Sexual reproduction thus became dominant.
Nevertheless, the article said, "What is the role of sex in evolution? Reproduction with recombination is almost ubiquitous in life (even bacteria exchange genetic material), while obligate asexual species appear to be rare evolutionary dead ends. Yet there is no agreement among the experts as to what makes sex so advantageous."
How can there be no agreement when the reason for sexual evolution is so obvious? In order for sexual evolution to work, each generation must die, which some people view as inconvenient, prompting them to imagine an afterlife. Subdividing, on the other hand, produces potential immortals who are naturally less diverse because they mutate less radically than the sexy species.
Lester Earnest
Stanford, CA
P.S. I do not hold any of this against Christos Papadimitriou, who I have known for 50 years.
----------------------------------------------------
AUTHORS' RESPONSE
Earnest's idea, first proposed by R.A. Fisher (1930) and H.J. Muller (1932), does not solve the problem and is referenced in our online appendix where the interested reader can begin to explore this fascinating topic. The debate among experts is ongoing, and our recent article contributed a fresh idea to it. Burjorjee did not back up with evidence his claim of empirical success of genetic algorithms, compared to, say, simulated annealing. And a propos philosophy of science, he may refer to Papadimitriou's 1995 article "Database Metatheory: Asking the Big Queries" (http://dl.acm.org/citation.cfm?id=211547) with its sections on T. Kuhn, K.R. Popper, and P. Feyerabend, and their relevance to computer science.
Adi Livnat
Haifa, Israel
Christos Papadimitriou
Berkeley, CA
CACM Administrator
The following letter was published in the Letters to the Editor in the February 2017 CACM (http://cacm.acm.org/magazines/2017/2/212426).
--CACM Administrator
I am writing to express my dismay and disappointment at the cover of the November 2016 issue introducing the article "Sex as an Algorithm: The Theory of Evolution Under the Lens of Computation" by Adi Livnat and Christos Papadimitriou, finding it offensive and attention-grabbing in a way that is inconsistent with ACM's public mission.
While I would guess that most readers either do not care or thought the cover "funny" or "cute," I have talked to enough of my colleagues, who describe their reaction as "shocked," "appalled," "offended," and "embarrassed," to believe it is a serious issue that warrants further reflection.
Specifically, is it really appropriate for ACM, a professional organization that purports to represent and support all its members and all members of the computing discipline, to distribute an issue that some are embarrassed to receive in our mailbox, display on our desks or conference tables, or look at on our computers if somebody might be looking over our shoulders?
First, the research in question is not about sex but about sexual reproduction and its effect on diversity in populations. There is a major difference, and conflating the two in this way comes across as juvenile. I cannot help think of "locker room talk."
Second, placing the huge, bold-faced word "Sex" on a hot pink cover creates an obvious and immediate association with women. Given the under-representation of women in the field, this kind of message is completely counterproductive and particularly reminds young women, who may be less certain about how welcome they are in the field, that they are to be associated with sex, not science.
Third, the unfortunate timing of this issue, which arrived during National Breast Cancer Awareness Month, was undoubtedly unintentional, but to those of us who have lost loved ones to breast cancer, the hot pink cover felt disrespectful and insensitive.
This may not seem like a big deal, and I am sure some readers are thinking I am overly sensitive and humorless. But quite honestly, it is tough enough being a woman in an extremely male-dominated field without feeling embarrassed and awkward about displaying my own professional organization's magazine in public.
In the end, I dropped it into the recycling bin without reading it.
Marie des Jardins
Baltimore, MD
----------------------------------------------------
EDITOR-IN-CHIEF'S RESPONSE:
The cover in question, for which I am ultimately responsible, was meant to be humorous. Since several readers were offended by it, it is clear in retrospect the humor was misguided. For that, I sincerely apologize. This has been discussed by the design team, and we hope to learn from this mistake.
Moshe Y. Vardi
Editor-in-Chief
CACM Administrator
The following letter was published in the Letters to the Editor in the March 2017 CACM (http://cacm.acm.org/magazines/2017/3/213824).
--CACM Administrator
Adi Livnat and Christos Papadimitriou review article "Sex as an Algorithm" (Nov. 2016) was fascinating but mistitled. It discussed the benefits of conjugality. George C. Williams in Sex and Evolution distinguished the more general concept conjugality from (eu)sexuality, in which the number of conjugal strains in the species is equal to the number of individuals participating in conjugation two, in all conjugal species on this planet. This seems an important distinction, and I suggest the cover of Communications was misleading. In my own book Albatross I emphasized this and other distinctions, aiming to avoid nonsensical talk, as in that arising from "the gostak distims the doshes" in The Meaning of Meaning by C.K. Ogden and I.A. Richards.
Livnat's and Papadimitriou's reference to their non-coverage of heterozygosity was revealing. I rather suspect heterozygosity is a prerequisite for sexuality proper; certainly a lot of sexual species are haploid in the gametic generation and diploid in the others.
Some of the mathematics as to the binarity of conjugation might be interesting. What are the chances that on some other world there may have evolved life with a triple helix, ternary conjugation and so trisexuality?
John A. Wills
Oakland, CA
Displaying all 3 comments