Use the Scientific Method in Computer Science - ACM - Computers in ...

Feb 2, 2017 - For example, assumptions must be weak, and hypotheses testable. For all computer science as a field has to contribute to the natural scienc-.
470KB Sizes 2 Downloads 287 Views
letters to the editor DOI:10.1145/3032965

Use the Scientific Method in Computer Science

I

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 elimination1 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 N “S E X A S A N ALG ORITH M :

8

COMMUNICATIO NS O F THE ACM

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. References 1. Burjorjee, K.M. Hypomixability elimination in evolutionary systems. In Proceedings of the 13th Foundations of Genetic Algorithms Conference (Aberystwyth, U.K., Jan. 17–20). ACM Press, New York, 2015, 163–175. 2. Popper, K. The Logic of Scientific Discovery. Routledge, London, U.K., 2007.

Keki M. Burjorjee, Berkeley, CA

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

| F EBR UA RY 201 7 | VO L . 60 | NO. 2

the ability of indi