EC lab Activities

Workshop Topic

  Understanding Coevolution
  Theory and Analysis of Coevolutionary Algorithms

Coevolutionary algorithms promise several advantages over traditional evolutionary algorithms in terms of their adaptability and potential open-endedness. However, they also challenge us with new and difficult issues. For example, their very adaptability means that fitness assessments in the algorithm are in some sense subjective, and thus the existence of Red Queen dynamics can make it difficult to know whether real progress is being made in any objective sense and pathologies like mediocre stable states can cast doubt on whether optimization is being done at all. More generally, dynamics in these systems can be complicated and surprising. Theory and analysis of coevolutionary algorithms is far less advanced than that of traditional evolutionary algorithms, but the time has come to focus our collective attention on analysis issues more formally. The goal of this workshop is to foster and encourage open discussion about the issues surrounding the direction that analysis of coevolutionary algorithms might take in the future, as well as introducing existing theory and empirically analytical work to those who are looking for a place to start understanding coevolution.

The publications in this year's workshop focused primarily on attempting to understand how to characterize and analyze coevolution. The first paper introduces an interesting new framework for analyzing coevolutionary problems from an order-theoretic perspective. The second paper overlaps this paper slightly, using similar notions of order and ranking in order to help better understand when coevolutionary algorithms behave dynamically like a traditional evolutionary algorithm. The third paper is also quite complementary, using dominance tournament methods to allow for on-line measurement of progress during evolutionary runs. The final paper offers an empirical perspective by applying coevolution to the problem of feature construction in machine learning.

Workshop Details

The workshop was held as a half day event, focusing on theoretical and empirical analysis of coevolutionary algorithms. The first 45 minutes was set aside for an introductory discussion, the next two hours was reserved for paper discussions, and the remaining time was dedicated to a very fruitful panel discussion.

Workshop Papers
The following is a list of the papers appearing in the workshop proceedings, in the order of their appearance. Those wishing to discuss details of the articles, such as how and if copies can be obtained, are encouraged to do so directly with the authors themselves, rather than through the workshop organizers.

• Order-Theoretic Analysis of Coevolution Problems: Coevolutionary Statics.
  Anthony Bucci and Jordan B. Pollack
• When Coevolutionary Algorithms Exhibit Evolutionary Dynamics.
  Sean Luke and R. Paul Wiegand
• The Dominance Tournament Method of Monitoring Progress in Coevolution.
  Kenneth O. Stanley and Risto Miikkulainen
• Coevolutionary Construction of Features for Transformation of Representation in Machine Learning.
  Bir Bhanu and Krzysztof Krawiec

Workshop Presentations
The workshop presentations are provided below. You can also download the workshop bib file here.

• Introduction to the Coevolution Workshop
• Order-Theoretic Analysis of Coevolution Problems: Coevolutionary Statics
• When Coevolutionary Algorithms Exhibit Evolutionary Dynamics
• The Dominance Tournament Method of Monitoring Progress in Coevolution
• Coevolutionary Construction of Features for Transformation of Representation in Machine Learning

Workshop Results Summary
This year's workshop went very well. There seemed to be good attendance, and the discussion that followed the presentations seemed to suggest that there is a strong interest in coevolutionary computation. The panel discussion was divided into three components: Challenges for the Coevolutionary Computation Community, Challenges of Coevolutionary Computation Research, and Action Items for the Future. A short description of the salient points from these three topics will follow.

• Challenges for the Coevolutionary Computation Community

  We discussed the problems coevolutionary computation seems to face as a community: lack of presence in the wider EC community and a lack of cohesion and interaction among coevolutionary researchers. The group at large identified several factors that may be contributing to this:

  • A lot of time spent on faults of coevolution, but not a lot of focus on its advantages.
  • Need to articulate usefulness of CEAs more clearly to the EC community: when and how does coevolution excel over a more traditional EA?
  • Hard to know where to submit papers at GECCO (and some other conferences).
  • No widely known common resources for discussion. Very few people were aware of Rik Belew's BBS.



• Challenges of Coevolutionary Computation Research

  We touched on some of the research issues which pose particular challenges to those of us who study coevolution.

  • There may be a bias towards inherently non-coevolutionary problems as focus of study. We need to articulate clearly what (if anything) do CEAs optimize?
  • Our choices for representation may be limiting potential open-ended coevolution.
  • Perhaps we should search for interesting problem domains that are well suited for the dynamic/adaptive advantages of coevolutionary methods. An example was provided: Cognitive Science/Neural Science models, etc.
  • Need to understand what kinds of problems where one could see unbounded emergence occur. What are the criteria for open-endedness? What exactly is open-endedness?



• Action Items for the Future

  We discussed some items that we can take in the near future to help promote coevolutionary computation in th EC field at large, as well as gather some cohesion among coevolutionary researchers.

  • Discuss putting together a mail list and/or web site for discussions.
  • Determine whether or not we should pursue a "Coevolution" track for GECCO next year (or for 2004). Perhaps we might combine tracks with some other group (Multi-Agent, etc.).
  • A suggestion was made that we consider trying to get one of the journals to have a special issue on coevolution. To do this, we will need to determine if there is enough critical mass of research to support it, and if there is interest from any of our journals.
  • It was the overwhelming feeling of those present that we should have a coevolution workshop next year. It was suggested that future workshops should be more focussed and more specific in topic.