Sevan G. Ficici 
Ofer Melnik 
Jordan B. Pollack 
sevan@cs.brandeis.edu  melnik@cs.brandeis.edu  pollack@cs.brandeis.edu 
DEMO Lab

We use evolutionary game theory (EGT) to investigate the dynamics and equilibria of selection methods in coevolutionary algorithms. The canonical selection method used in EGT is equivalent to the standard "fitnessproportional" selection method used in evolutionary algorithms. All attractors of the EGT dynamic are Nash equilibria; we focus on simple symmetric variablesum games that havepolymorphic Nashequilibrium attractors. Against the dynamics of proportional selection, we contrast the behaviors of truncation selection, (mu, lambda)ES, linear ranking, and Boltzmann selection. Except for Boltzmann selection, all of the alternative methods we test unconditionally fail to converge onto polymorphic Nash equilibrium. Instead, we find point attractors that lack gametheoretic justification, cyclic dynamics, or chaos. Boltzmann selection converges onto polymorphic Nash only when selective pressure is sufficiently low; otherwise, we obtain attracting limitcycles or chaos. If our intent is to solve variablesum games with coevolution, then our results show that many selection methods are inappropriate. If our intent is to use coevolution to model another dynamical system, then our results emphasize the degree to which the model's behavior is sensitive to implementation details regarding selection  details that we might not otherwise believe to be critical.
Selection Method 
Pressure Range 
Notes  
Fitness Proportional  Not Applicable  Standard in evolutionary game theory. Nash attractor, as expected.  
Truncation  0 < k < 0.5  Higher values of 'k' give higher selection pressures.  
0.42 <= k <= 0.5  converges to all Hawks, or cycles.  
0.31 <= k <= 0.41  chaos or cyclic behavior.  
0 < k < 0.30  cyclic behavior.  
(Mu, Lamba)ES  0 < k < 1.0  Lower values of 'k' give higher selection pressures.  
0.59 <= k < 1.0  chaos or cyclic behavior.  
0.42 <= k <= 0.58  converges to all Hawks, or cycles.  
0 < k <= 0.41  converges to all Hawks or all Doves, or cycles.  
Linear Rank  Not Applicable  cyclic behavior.  
Boltzman  0 < k  Higher values of 'k' give higher selection pressure. k = 0.05 ESS attractor; k = 0.2 limit cycle; k = 0.5 edge of chaos. 
The map diagram indicates how the proportion of Hawks changes from Time t (xaxis) to Time t+1 (yaxis). Click inside the map diagram to watch an orbit of the dynamical system; the xlocation of the mouse determines the system's initial condition. A cobweb diagram will be made for 500 iterations of the system. Click another position to see the orbit of a different initial condition. Use the 'clear' button to erase all orbits.
The text box below the graph indicates the numerical value of the last orbit's initial condition. You may also specify any desired initial condition by typing directly into this text box. Initial conditions can be specified as floatingpoint numbers, e.g. '0.5', or as fractions, e.g. '1/2'.
Please see paper for details:
Ficici, S.G., Melnik, O., and Pollack, J.B. (2000) "A GameTheoretic Investigation of Selection Methods Used in Evolutionary Algorithms." In Proceedings of the 2000 Congress on Evolutionary Computation. Zalzala, A., et al (eds.). IEEE Press.
Written by Sevan G. Ficici
v0.2 (4/30/2000)
Copyright (C) 2000 by Brandeis University Board of Trustees
Software License