acm - an acm publication

Articles

Ubiquity symposium: Evolutionary computation and the processes of life
evolutionary computation and evolutionary game theory: expecting the unexpected

Ubiquity, Volume 2013 Issue January, January 2013 | BY David B. Fogel 

|

Full citation in the ACM Digital Library  | PDF


Ubiquity

Volume 2013, Number January (2013), Pages 1-6

Ubiquity symposium: Evolutionary computation and the processes of life: evolutionary computation and evolutionary game theory: expecting the unexpected
David B. Fogel
DOI: 10.1145/2434536.2406360

In this article, David Fogel discusses the relationship between evolutionary computation and evolutionary game theory. The mathematics of evolutionary game theory relies on assumptions that often fail to describe the real-world conditions that the theory is intended to model. This article highlights those assumptions and suggests evolutionary computation may ultimately serve as a more useful approach to understanding complex adaptive systems in nature.

Editor

Evolutionary computation, the field of simulating evolutionary on computers, has a long history dating at least into the 1950s. From some of the earliest experiments of Alex Fraser [1, 2] to the artificial intelligence research of Lawrence Fogel [3, 4] and the modeling of evolving ecosystems by Michael Conrad [5, 6], there has been a longstanding view of evolution as a means for creating new solutions to challenging problems while also gaining a better understanding of the evolutionary process itself. There were many successful early applications of evolutionary principles to problem solving, including the design of hardware [7, 8, 9, 10], controlling the operations of industrial factories [11], generalized function optimization [12], and playing games [13, 14].

About the same time as evolutionary computation was being applied to games, such as the prisoner's dilemma and two-player combat [15, 16], the idea of using mathematical game theory to better understand evolution in nature was also emerging [17]. The idea was, and still remains, to view animal behaviors in terms of tactical actions that generate certain rewards or penalties, described also as "payoffs." If these payoffs can be well modeled, it may be possible to apply the theory of games and rational behavior to anticipate the likelihood of observing different behaviors in varying environments.

One common approach in evolutionary game theory relies on what is known as "evolutionary stable strategies." The idea is that animal behaviors are modeled as alternative plays in a game. For example, in a "hawk-dove" game, hawks are aggressive and fight for resources, while doves are passive and do not fight. Payoffs can be described on average for each possible type of encounter between birds in this game. When a hawk meets a dove, the dove declines to engage the hawk and thus the hawk gets the resource and the dove gets nothing. When two hawks meet, they fight until one is injured and the other gets the resource. Finally, when two doves meet, each stands around passively until one tires and the other gets the resource. Common values ascribed in the game are +50 for the resource, -100 for being injured, and -10 for wasting time.

The concept of evolutionary stability suggests that the likely outcome of these hawks and doves will place their relative payoffs in equilibrium. Otherwise, so the theory goes, if there are too many hawks then the hawks will be more likely to get injured fighting other hawks, and if there are too many doves, then more hawks can easily take advantage of them. Thus, the balancing equation for hawks (H) and doves (D) is:

E(H,H) P(H) + E(H,D) (1-P(H)) = E(D,D) (1-P(H)) + E(D,H) P(H)

where E(A,B) is the expected payoff to A given an encounter with B, and P(H) is the fraction of hawks in the population of birds. E(H,H) = -25, E(H,D) = +50, E(D,D) = +15, and E(D,H) = 0. Here, the value of P(H) that balances the equation is 7/12, meaning that the payoffs to hawks and doves on average are the same if hawks and doves are in the ratio 7:5.

The notion of stability at an equilibrium point is central to game theory. It has been exapted (that is, used for a function other than for which it was developed originally) as being central in evolutionary game theory as well, so much so that some have offered that everything in animal behavior must be an evolutionary stable strategy of some sort, otherwise it would not be present for us to observe [18]. Unfortunately, the congruence between evolutionary game theory's prediction and real-world condition has been mixed at best, often lacking but mostly missing. Compared to the very few attempts to validate evolutionary game theory in the real world, the attempts to extend the theory in increasingly abstract constructs has been voluminous.

It's possible to use evolutionary computation to explore the ability to use evolutionary game theory to make predictions about the dynamics of complex adaptive systems. Interestingly, even in simple games such as the hawk-dove game described above, simulations of evolution in these game dynamics do not correspond well with the expectations of evolutionary game theory, particularly when the population size is on the order of that found in many real conditions (i.e., 50 to 500 individuals). Examples include Fogel and Fogel [19, 20, 21] and Ficici [22]. Rather than settle at equilibria, the population of hawks and doves can cascade around apparent limit cycles or act in other ways associated with chaotic systems. Evolutionary stability appears absent in these results.

Evolutionary game theory relies on assumptions of infinite populations and zero mutation between parents and offspring. Neither of these occurs in real settings. Some have tried to relax the assumption about infinite populations by applying correcting factors [23], but still utilize the expected payoff structure provided earlier. That is, say for the case of the hawk-dove game, when two hawks meet, each receives -25 points, which is the average of +50 for the victor and -100 for the vanquished. This is entirely inappropriate for understanding the dynamics of systems that involve culling losers (i.e., those that involve "natural selection"). When two hawks meet, one wins and the other loses; even a cursory examination of the physical condition of losers in contests such as these reveals that winners fare much better than losers. By averaging out these very real effects, evolutionary game theory leads inexorably to answers that are "right on the average" but wrong just about everywhere else.

Evolutionary computation offers the promise of being able to simulate real-world evolutionary dynamics with sufficient fidelity to make testable predictions about animal behaviors. To date, such efforts are just in their infancy. It will be interesting to determine if evolutionary computation can provide more accurate predictions than evolutionary game theory, and help codify what elements of given evolutionary models are truly most relevant. This may help us to better understand the individual organisms in ecosystems of concern, and help us to maintain their viability in the long run.

References

1. Fraser, A.S. Simulation of genetic systems by automatic digital computers I. Introduction. Australian J. Biological Sciences 10, 4 (1957), 484–491.

2. Fraser, A.S. "The evolution of purposive behavior," in Purposive Systems, H. von Foerster, J.D. White, L.J. Peterson, and J.K. Russell (eds.). Spartan Books, Washington D.C., 1968, 15–23.

3. Fogel, L.J. Autonomous Automata. Industrial Review 4, 2 (1962), 14–19.

4. Fogel, L.J., Owens, A.J., and Walsh, M.J. Artificial Intelligence through Simulated Evolution. John Wiley, New York, 1966.

5. Conrad, M. Computer experiments on the evolution of coadaptation in a primitive ecosystem. Ph.D. dissertation, Stanford University, 1969.

6. Conrad, M. "Evolution on the adaptive landscape," in Theoretical Approaches to Complex Systems, R. Heim and G. Palm (eds.), Springer Lecture Notes on Biomathematics, No. 21, Springer, Heidelberg, Germany, 1978, 147–169.

7. Friedman, G.J. Selective feedback computers for engineering synthesis and nervous system analogy. M.S. thesis, UCLA, 1956.

8. Dunham, B., Fridshal, D., Fridshal, R., and North, J.H. Design by natural selection. Synthese 15 (1963), 254–259.

9. Rechenberg, I. Cybernetic solution path of an experimental problem. Royal Aircraft Establishment, Library Translation 1122, 1965.

10. Schwefel, H.-P. Experimentelle optimierung einer zweiphasenduse tell 1. AEG Research Institute Project MHD-Staustrahlrohr 11034/68, Technical report 35, 1968.

11. Box, G.E.P. Evolutionary operation: A method for increasing industrial productivity. Applied Statistics 6, 2 (1957), 81–101.

12. Bremermann, H.J., Rogson, M., and Salaff, S. "Global Properties of Evolution Processes" in Natural Automata and Useful Simulations, H.H. Pattee, E.A. Edlsack, L. Fein, and A.B. Callahan (eds.). Spartan Books, Washington D.C., 1966, 3–41.

13. Barricelli, N.A. Numerical testing of evolution theories. Part II: Preliminary tests of performance, symbiogenesis and terrestrial life. Acta Biotheoretica 16, 3–4 (1963), 99–126.

14. Reed, J., Toombs, R., and Barricelli, N.A. Simulation of biological evolution and machine learning. I: Selection of self-reproducing numeric patterns by data processing machines, effects of hereditary control, mutation type and crossing. J. Theoretical Biology 17, 3 (1967), 319–342.

15. Fogel, L.J., and Burgin, G.H. Competitive goal-seeking through evolutionary programming. Final report, Contract AF 19(628)-5927, Air Force Cambridge Research Laboratories, 1969.

16. Burgin, G.H. On playing two-person zero-sum games against non-minimax players. IEEE Trans. Systems Science and Cybernetics Vol. SSC-5, 4 (1969), 369–370.

17. Maynard Smith, J. and Price, G.R. The logic of animal conflict. Nature 246, 5427 (1973), 15–18.

18. Dawkins, R. The Selfish Gene, 2nd edition, Oxford University Press, Oxford, 1989.

19. Fogel, D.B., Fogel, G.B., and Andrews, P.C. On the instability of evolutionary stable strategies. BioSystems 44, 2 (1997), 135–152.

20. Fogel, G.B., Andrews, P.C., and Fogel, D.B. On the instability of evolutionary stable strategies in small populations. Ecological Modelling 109, 3 (1998), 283–294.

21. Fogel, G.B., and Fogel, D.B. Simulating natural selection as a culling mechanism on finite populations with the hawk-dove game. BioSystems 10, 1 (2011), 57–62.

22. Ficici, S.G. Solution concepts in coevolutionary algorithms. Doctoral dissertation, Brandeis Univ., 2004.

23. Schaffer, M.E. Evolutionary stable strategies for a finite population and a variable contest size. J. Theoretical Biology 132, 4 (1988), 469–478.

Author

Dr. David Fogel is president of Natural Selection, Inc. He received his Ph.D. in engineering from UCSD and is the author of more than 200 technical publications and six books, including Evolutionary Computation: Toward a New Philosophy of Machine Intelligence (published in three editions, IEEE Press). Dr. Fogel was the founding editor-in-chief of the IEEE Transactions on Evolutionary Computation (1996–2002) and editor-in-chief of BioSystems (2000–2008). Dr. Fogel is an IEEE Fellow and has received numerous recognitions including the 2004 IEEE Kiyo Tomiyasu Technical Field Award and the 2008 IEEE Computational Intelligence Society Evolutionary Computation Pioneer Award. Dr. Fogel was named one of the top-100 most influential alumni in the 50-year history of UCSD in 2009. He also received the 2012 CajAstur Mamdani Prize in Soft Computing from the European Soft Computing Centre.

©2013 ACM  $15.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 © 2013 ACM, Inc.

COMMENTS

POST A COMMENT
Leave this field empty