LSCITS home University of Bristol Department of Computer Science John Cartlidge - home
 
 Home 
 
 Publications 
 
 BriCS 
 
 CReST 
 
 ExPo 
 
 EStA 

  EStA

  The Evolutionary Steering App
 
 

Copyright © John Cartlidge 2011



Using EStA: The Evolutionary Steering App

EStA is a research and teaching tool that allows users to “steer” a coevolutionary system during runtime [1]. Two populations (hosts and parasites) are coevolving. Each generation individuals play the “Greater Than” game, a simple game where two players compare the number of 1s in their genetic bitstrings [2]. The player with the greatest number of 1s is the winner and scores 1 point. The loser receives nothing. Individuals are selected to breed based on their total scores against a “sample” of opponents from the opposing population. At the start, all individuals are initialised with all bits zeroed. The goal is to evolve “optimal” individuals containing all (100) bits set to 1.

The “absolute” fitness of every individual (the number of 1s contained in the genotype) is plotted in the top-right panel. This allows us to view progress [3]. However, the evolutionary mechanism does not have direct access to these values. Rather, when selecting which individuals to breed, evolution must use the scores calculated by playing the Greater Than game. For each population, the average of these scores is plotted in the bottom-right panel as “mean relative fitness”.

Sometimes, all individuals in one population are able to beat (are “Greater Than”) all individuals in the opposing population. When this happens, populations are said to have “disengaged”. Disengagement can affect progress and may stop the discovery of optimal individuals as the removal of (co)evolutionary pressures causes the population to randomly “drift” around genotype space [4].

Disengagement is more likely to occur when one population has an advantage over another. You can control the advantage that one population has by using the parasite bias slider. Values greater than 0.5 favour parasites, while values less than 0.5 favour hosts. A value of 0.5 produces an unbiased coevolutionary system, where both populations have an equal 50 chance of flipping a 1 or a 0 each time a mutation event occurs. The host population mutation bias is always fixed at 0.5. Thus, with no selection pressure, a host population will naturally drift toward individuals with an “absolute fitness” of 50 (represented on the absolute fitness graph as a solid black line). In contrast, the parasite population will naturally drift toward individuals with an absolute fitness of 100 x Parasite Bias (represented on the absolute fitness graph as a black dotted line). Hence, if populations have an absolute fitness above their respective “drift” lines, it must be due to coevolutionary competition driving evolution [5].

“Virulence” can be used to counter the effects of bias [6]. You can use the sliders below the virulence panels to set the virulence of each population. Reducing virulence helps to stop disengagement [7]. However, reducing virulence can also slow evolutionary progress. Selecting an appropriate virulence is a balancing act. You can see this for yourself by trying to evolve optimal solutions under different bias levels. See what happens when you vary bias during a run. Is it harder? The distribution of individuals' Greater Than scores are plotted as error bars on the virulence curves of each population. Is this information useful in guiding your choice of virulence? [3]

“AVA” (Autonomous Virulence Adaptation) is an automated process for setting the virulence levels of a population [8]. If you switch AVA on, you will see virulence automatically vary over time. How does AVA perform? Are you able to steer the system better than AVA can? To see “under the hood” of AVA and alter setting, select the AVA tab an alter the settings.

Finally, why not see the effect that other parameters have on the system? “Random parasites” is the equivalent of evolution against a random set of opponents. How does this compare with coevolution? What is the effect of “elitism”, “noise”, and a mutation rate that falls over time? [4,5,6]

Further Reading

  1. EStA was first developed at the University of Leeds in 2002 by John Cartlidge and Martin Thompson. EStA has subsequently been developed and maintained by John Cartlidge. For full details and further reading on EStA, and the concept of “steering” a coevolutionary system, please refer to: S. Bullock, J. Cartlidge, & M. Thompson, (2002), “Prospects for computational steering of evolutionary computation,” in Workshop Proc. 8th Int. Conf. Artif. Life, E. Bilotta et al., Eds. Sydney, Australia: MIT Press, Dec. 2002, pp. 131–137. [Available Online] [Bibtex] [Abstract] [Conference Link] (7 pages, approx. 4,500 words).

  2. Coevolving populations are playing the “Greater Than Game” (GTG). For full details and further reading on the GTG, please refer to: R. A. Watson & J. B. Pollack, (2011) “Coeovlutionary dynamics in a minimal substrate,” in Proc. Genetic and Evolutionary Computation Conference (GECCO), L. Spector et al. (eds), Morgan Kauffmann, Jul. 2001, pp. 702-709.

  3. Visualising “progress” in a coevolutionary system is notoriously difficult. For a further reading, refer to: J. Cartlidge & S. Bullock, (2004), “Unpicking tartan CIAO plots: Understanding irregular coevolutionary cycling,” Adaptive Behaviour, vol. 12, no. 2, pp. 69–92, Jun. 2004. [Available Online] [Bibtex] [Abstract] [Journal Link] doi:10.1177/105971230401200201 (24 pages, approx. 14,000 words).

  4. For a comprehensive discussion on disengagement in coevolutionary systems, refer to: J. Cartlidge, (2004), “Rules of Engagement: Competitive Coevolutionary Dynamics in Computational Systems,” PhD thesis, Sch. Comput., Univ. Leeds, UK. [Available Online] [Bibtex] [Abstract] [Department Link] (210 pages, approx. 75,000 words).

  5. For a discussion on the dynamics of coevolutionary systems, refer to: J. Cartlidge & S. Bullock, (2003), “Caring versus sharing: How to maintain engagement and diversity in coevolving populations,” in Proc. 7th Eur. Conf. Artif. Life (ECAL’03), W. Banzhaf et al., Eds. Dortmund, Germany: Springer Verlag, Sep. 2003, pp. 299–308. [Available Online] [Bibtex] [Abstract] doi:10.1007/978-3-540-39432-7_32 (10 pages, approx. 5,000 words).

  6. Inspired by virulence in natural coevolutionary systems, the “Reduced Virulence” technique was first introduced by John Cartlidge in 2002 to combat disengagement. Refer to: J. Cartlidge & S. Bullock, (2002), “Learning lessons from the common cold: How reducing parasite virulence improves coevolutionary optimization,” in Proc. Congr. Evol. Comput. (CEC’02), D. Fogel et al., Eds. Honolulu, HI: IEEE Press, Jun. 2002, pp. 1420–1425. [Available Online] [Bibtex] [Abstract] [Conference Link] doi:10.1109/CEC.2002.1004451 (7 pages, approx. 4,500 words).

  7. Reduced virulence has been shown to improve coevolutionary optimisation by reducing the likelihood of disengagement. Refer to: J. Cartlidge & S. Bullock, (2004), “Combating coevolutionary disengagement by reducing parasite virulence,” Evol. Comput., vol. 12, no. 2, pp. 193–222, Summer 2004. [Available Online] [Bibtex] [Abstract] [Journal Link] doi:10.1162/106365604773955148 (30 pages, approx. 15,000 words).

  8. First developed in 2008 by John Cartlidge, AVA is a technique for dynamically adapting population virulence during runtime. It has been shown to improve coevolutionary optimisation in a number of domains. For further reading, refer to the following publications:

 

©John Cartlidge.  Page last modified on: