Communications of the ACM
News
Sharing Computational Perspectives
In the Avida artificial life software program, bits of code act as organisms. As new computationally beneficial genotypes evolve, their fitness rises and they sweep through the population (hence the general height and color increase over time).
Credit: Courtesy of David M. Bryson
Why bother with sex? Venturing forth in search of a mate can be dicey business, and even if you succeed, you can pass on only half of your genes, which are randomly combined with half of your mate's, to your offspring. For more than a century, biologists have suggested that mixing up genes is exactly what sexual reproduction contributes to evolution, making it easier for novel gene combinations to appear. But the downside, also long understood by biologists, is that what gene mixing gives, it also takes away: Sexual reproduction can break up a winning gene combination as easily as it can create one.
Nonetheless, among plants, fungi, and animals, sexual reproduction is far more popular than asexual reproduction, a fact for which biologists have no thoroughly satisfactory explanation. In the December 2008 issue of Proceedings of the National Academies of Science, computer scientist Christos Papadimitriou and biologist Adi Livnat of the University of California, Berkeley teamed with biologists Jonathan Dush-off of McMaster University and Marcus Feldman of Stanford University to offer a mathematical model that sheds some light on this puzzle. They imagined a simple system with two genes, each of which comes in three versions, and with different fitnesses (that is, survival values) assigned to the nine possible combinations of the two genes. From a starting population in which all gene combinations are equally likely, the model found that asexual reproduction, which gives offspring the same genes as their parents, quickly led to the domination of the particular gene combination with the greatest fitness. But sexual reproduction, which switches genes from one generation to the next, leads to a different outcome: the gene versions that dominate are those that give the greatest average fitness no matter which other gene version they are paired with.
Sex, in other words, promotes genes that are good mixers with other genes, and a versatile gene may be more valuable, from an evolutionary perspective, than one that works very well in some combinations but much worse in others. Hence, the new model provides a specific and quantitative accounting of one useful aspect of sex.
Today, computer scientists are doing far more than helping other scientists run their numerical models more effectively. The theory of computation has become such a sophisticated science in its own right that computer scientists are now making intellectual contributions to a wide range of other disciplines, including evolutionary theory, physics, and economics.
Evolutionary Theory
Over the years, evolutionary theory has drawn on ideas from engineering, mathematics, and physics, so it's hardly surprising that computer scientists are now also making substantial contributions. "Evolution is such a broad topic [that] it really benefits from a range of approaches," says Sally P. Otto, an evolutionary biologist at the University of British Columbia. One noteworthy example of collaboration by biologists and computer scientists Otto cites is the artificial life software platform Avida, in which bits of code act as "organisms" able to replicate and evolve. If the model is setup so that digital organisms gain more processing speed by being able to add two numbers, for example, then the ability to add appears and proliferates, even though it was not specifically programmed in.
Evolutionary theory has drawn on ideas from engineering, mathematics, and physics. Now computer scientists are also making substantial contributions.
But if computer science is addressing the puzzle of sex, then sex has also done something for computer science, in the form of genetic algorithms that address optimization problems by evolving candidate solutions in a manner inspired by genetic recombination. However, these algorithms are not always good at reaching the solution a computer scientist wants. "Nature's favorite trick yields bad optimizers," says Papadimitriou, and it is this mystery that got him started on the research that led him to conclude that sex promotes mixability, not fitness. That distinction illustrates a difference in perspective; to a computer scientist, an algorithm has performed its job once it has produced a solution. To a biologist, on the other hand, a "solution" is a stable configuration that doesn't just appear once, but survives and prospers over many generations. Because evolution is so complex and, by definition, an ongoing process, "biologists have given up on having complete solutions," Otto says.
Solving difficult problems, of course, is a basic aim of computer science, whose defining characteristic is "conquering complexity," says Papadimitriou. The theory of computational complexity, which classifies problems by the resources needed to solve them, was pioneered by computer scientists in the face of general indifference from traditional mathematicians. The discovery of depth in computation, says Papadimitriou, allowed computer science to give birth to big questions, bestowing it with an intellectual respectability that mathematicians now fully embrace.
Insights from computer science have illuminated the mathematical properties of networks, broadly defined, leading to applications ranging from sociology to physics. Networks can exhibit phase transitions—changes from one kind of macroscopic behavior to another—that share deep similarities to phase transitions in physics, such as a liquid freezing into a solid. Belief propagation, for example, is an algorithm for performing statistical inferences that turns out to contain concepts closely related to fundamental principles of statistical thermodynamics, so that knowledge gained by physicists has influenced how computer scientists understand some types of computation.
Economics and Game Theory
Early on, computer scientists appreciated game theory and economic modeling. That connection dates to at least the 1940s and the pioneering work of John von Neumann, but has grown much deeper in recent decades. Economists talk of Pareto optimums, in which no participant in a system can perform better without making another participant worse off, and of Nash equilibria, in which no participant can make a unilateral change of strategy that will bring an advantage, and they have proved theorems showing that, under certain assumptions, Pareto optimums and Nash equilibria must exist. But the existence of such a state is no guarantee that a realistic system can actually attain it. For example, computer scientists have shown that Nash equilibria are computationally intractable problems, meaning not only that mathematical models of economic markets are hard to solve, but that the extent to which human behavior can move a market toward a Nash equilibrium becomes questionable.
Moreover, Pareto optimality and Nash equilibria do not necessarily connote social or political desirability. Nash equilibrium represents the best that participants in a market can do by pursuing a wholly selfish strategy. Papadimitriou has coined the term "price of anarchy" for the fact that Nash equilibrium often gives participants a poorer outcome than the best they could have obtained through collaboration, while work by other computer scientists not only shows how to calculate this price, in certain models, but also indicates that the price may not be too high.
There are challenges, however, in getting academic disciplines to collaborate, says Lance Fortnow, a professor of electrical engineering and computer science at Northwestern University. "Computer scientists want to impress other computer scientists," Fortnow says, and economists possess the same attitude. But cooperation between the two fields is growing, and an increasing number of economists see computer science as offering ideas they can draw from, not only in the technical matter of making mathematical models work efficiently, but also as a source of insight into the behavior and properties of those models.
Fortnow notes that companies like Google, Microsoft, and Yahoo! have understood the importance of economics and computer science in developing products and services, and have assembled teams in which both types of scientists work side by side. This mixing of talents is happening at some universities, and the National Science Foundation is considering a new program in economics and computer science.
Certain ideas of computer scientists are catching on among economists, says Fortnow. He cites the auctioning of sections of the radio spectrum by the Federal Communications Commission as the type of economic game in which "computational issues get nasty," because different players want different parts of the spectrum for a variety of exclusive purposes. Computer science can explain how complexity manifests itself in such a situation, and can suggest mechanisms to make an auction more orderly and useful. Thus far, however, it's hard to make the case that computer science has changed economic theory in any significant ways but, Fortnow urges, "give it time!"
Further Reading
Otto, S.P.
The evolutionary enigma of sex, The American Naturalist 174, S1, July 2009.
Lenski, R.E., Ofria, C., Pennock, R.T., and Adami, C.
The evolutionary origin of complex features, Nature 423, 139, May 8, 2003.
Yedidia, J., Freeman, W.T., and Weiss, Y.
Understanding belief propagation and its generalizations, Exploring Artificial Intelligence in the New Millennium, Lakemeyer, G., Nebel, B. (eds), Morgan Kaufmann Publishers, San Francisco, CA, 2003.
Fortnow, L. and Gasarch, B.
Computational Complexity blog http://blog.computationalcomplexity.org/
Kalai, E., Jackson, M.O., Lehrer, E., Palfrey, T.R., and Parkes, D.C. (eds.)
Games and Economic Behavior http://www.elsevier.com/wps/locate/geb
Figures
Figure. In the Avida artificial life software program, bits of code act as organisms. As new computationally beneficial genotypes evolve, their fitness rises and they sweep through the population (hence the general height and color increase over time).
©2010 ACM 0001-0782/10/0700 $10.00
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. To copy otherwise, to republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee.
The Digital Library is published by the Association for Computing Machinery. Copyright © 2010 ACM, Inc.
No entries found