Evolution Icon Evolution

What Can and Can’t Darwin’s Algorithm Compute?

July 14, 2020, 2:08 PM
Charles Darwin
Photo: Charles Darwin in 1855, by Maull and Polyblank, Literary and Scientific Portrait Club, via Wikimedia Commons.

Editor’s note: We are delighted to welcome a new contributor, Roman V. Yampolskiy, Associate Professor in the department of Computer Engineering and Computer Science at the Speed School of Engineering, University of Louisville. In a new series, Dr. Yampolskiy asks: “What Can and Can’t Darwin’s Algorithm Compute?”

In 1859 Charles Darwin1 and many scholars before him2, 3 have proposed theories to explain the origins of complex life forms via natural selection and modification. Scientific theories are algorithms which, given starting conditions as input, make statistically accurate predictions of the future state of the system. For example, computer simulations of continental drift give us positions of continents at some time t. I have emphasized the importance of such simulations: 

A scientific theory cannot be considered fully accepted until it can be expressed as an algorithm and simulated on a computer. It should produce observations consistent with measurements obtained in the real world, perhaps adjusting for the relativity of time scale between simulation and the real world. In other words, an unsimulatable hypothesis should be considered significantly weaker than a simulatable one. It is possible that the theory cannot be simulated due to limits in our current computational capacity, hardware design, or capability of programmers and that it will become simulatable in the future, but until such time, it should have a tentative status.4 

Simulations of Darwinian algorithm on a computer are known as Evolutionary Algorithms (EA) and have been around since the early days of computer science5, 6, with popular sub-fields such as Genetic Algorithms (GA), Genetic Programming (GP), Evolutionary Strategy (ES), and Artificial Life (AL). Currently, the state of performance in all of the above-mentioned areas is orders of magnitude less complex than what we observe in the natural world. But why? 

Evolution as a Computational Process

A number of seminal papers have been published attempting to formalize Darwin’s biological theory from the point of view of computational sciences. Such works essentially see biological evolution as a computational process running on a carbon-based substrate, but which can be run on other substrates. 

Valiant in his work on evolvability7 treats Darwinian evolution as a learning process over mathematical functions and attempts to explain quantitatively which artifacts can be evolved with given resources, and which can not. Likewise, Chaitin in his work on metabiology8, 9 attempts to develop an abstract fundamental mathematical theory of evolution. Wolfram, in A New Kind of Science10, attempts to show how rules of a computational universe of simple programs can be used to explain some of the biological complexity we observe. Livnat and Papadimitriou analyze sex as an algorithm, in their work on the theory of evolution viewed through the lens of computation11. 

Tomorrow, “On Evolutionary Computation.”

References:

  1. Darwin, C., On the origin of species by means of natural selection, or. The Preservation of Favoured Races in the Struggle for Life, London/Die Entstehung der Arten durch natürliche Zuchtwahl, Leipzig oJ, 1859.
  2. Lamarck, J.-B.-P., Philosophie zoologique. 1809.
  3. Chambers, R., Vestiges of the natural history of creation. 1853: J. Churchill.
  4. Yampolskiy, R.V., What are the ultimate limits to computational techniques: verifier theory and unverifiability. Physica Scripta, 2017. 92(9): p. 093001.
  5. Fogel, L.J., A.J. Owens, and M.J. Walsh, Artificial intelligence through simulated evolution. 1966.
  6. Barricelli, N.A., Symbiogenetic evolution processes realized by artificial methods. Methodos, 1957. 9(35-36): p. 143-182.
  7. Valiant, L.G., Evolvability. Journal of the ACM (JACM), 2009. 56(1): p. 3.
  8. Chaitin, G., Life as evolving software, in A Computable Universe: Understanding and Exploring Nature as Computation. 2013, World Scientific. p. 277-302.
  9. Chaitin, G., Proving Darwin: making biology mathematical. 2012: Vintage.
  10. Wolfram, S., A New Kind of Science. May 14, 2002: Wolfram Media, Inc.
  11. Livnat, A. and C. Papadimitriou, Sex as an algorithm: the theory of evolution under the lens of computation. Communications of the ACM, 2016. 59(11): p. 84-93.