A review of landmark articles in the field of co-evolutionary computing
---
paper_title: Co-evolving parasites improve simulated evolution as an optimization procedure

paper_content:

This paper shows an example of how simulated evolution can be applied to a practical optimization problem, and more specifically, how the addition of co-evolving parasites can improve the procedure by preventing the system from sticking at local maxima. Firstly an optimization procedure based on simulated evolution and its implementation on a parallel computer are described. Then an application of this system to the problem of generating minimal sorting networks is described. Finally it is shown how the introduction of a species of co-evolving parasites improves the efficiency and effectiveness of the procedure.
---
paper_title: Co-evolving parasites improve simulated evolution as an optimization procedure

paper_content:

This paper shows an example of how simulated evolution can be applied to a practical optimization problem, and more specifically, how the addition of co-evolving parasites can improve the procedure by preventing the system from sticking at local maxima. Firstly an optimization procedure based on simulated evolution and its implementation on a parallel computer are described. Then an application of this system to the problem of generating minimal sorting networks is described. Finally it is shown how the introduction of a species of co-evolving parasites improves the efficiency and effectiveness of the procedure.
---
paper_title: Applying Adaptive Algorithms to Epistatic Domains

paper_content:

John Holland has shown that when adaptive algorithms are used to search certain kinds of extremely large problem spaces, they will converge on a "good" solution fairly quickly. Such problem spaces are characterized by a low degree of epistasis. A host of classical search problems, however, are epistatic in nature. The present paper describes some new techniques for applying adaptive algorithms to epistatic domains, while retaining some of the strength of Holland's convergence proof. These techniques are described for two-dimensional bin-packing problems, and summarized for graph coloring problems. What makes these problems amenable to an adaptive approach is a two-stage evaluation procedure. Encodings of solutions are mutated and reproduced as they are in non-epistatic domains, but their evaluation is carried out after a decoding process. Using the techniques described, convergence is promoted in two ways: one of the natural mutation operators is a weaker version of Holland's crossover, and domain knowledge may be built into decoding processes so that the size of the search space is radically cut down.
---
paper_title: A Coevolutionary Approach to Learning Sequential Decision Rules

paper_content:

We present a coevolutionary approach to learning sequential decision rules which appears to have a number of advantages over non-coevolutionary approaches. The coevolutionary approach encourages the formation of stable niches representing simpler subbehaviors. The evolutionary direction of each subbehavior can be controlled independently, providing an alternative to evolving complex behavior using intermediate training steps. Results are presented showing a significant learning rate speedup over a noncoevolutionary approach in a simulated robot domain. In addition, the results suggest the coevolutionary approach may lead to emergent problem decompositions.
---
paper_title: Cooperative Coevolution: An Architecture for Evolving Coadapted Subcomponents

paper_content:

To successfully apply evolutionary algorithms to the solution of increasingly complex problems, we must develop effective techniques for evolving solutions in the form of interacting coadapted subcomponents. One of the major difficulties is finding computational extensions to our current evolutionary paradigms that will enable such subcomponents to "emerge" rather than being hand designed. In this paper, we describe an architecture for evolving such subcomponents as a collection of cooperating species. Given a simple string-matching task, we show that evolutionary pressure to increase the overall fitness of the ecosystem can provide the needed stimulus for the emergence of an appropriate number of interdependent subcomponents that cover multiple niches, evolve to an appropriate level of generality, and adapt as the number and roles of their fellow subcomponents change over time. We then explore these issues within the context of a more complicated domain through a case study involving the evolution of artificial neural networks.
---
paper_title: Evolving Complex Structures Via Cooperative Coevolution

paper_content:

A cooperative coevolutionary approach to learning complex structures is presented which, although preliminary in nature, appears to have a number of advantages over non-coevolutionary approaches. The cooperative coevolutionary approach encourages the parallel evolution of substructures which interact in useful ways to form more complex higher level structures. The architecture is designed to be general enough to permit the inclusion, if appropriate, of a priori knowledge in the form of initial biases towards particular kinds of decompositions. A brief summary of initial results obtained from testing this architecture in several problem domains is presented which shows a significant speedup over more traditional non-coevolutionary approaches.
---
paper_title: New Methods for Competitive Coevolution

paper_content:

We consider "competitive coevolution," in which fitness is based on direct competition among individuals selected from two independently evolving populations of "hosts" and "parasites." Competitive coevolution can lead to an "arms race," in which the two populations reciprocally drive one another to increasing levels of performance and complexity. We use the games of Nim and 3-D Tic-Tac-Toe as test problems to explore three new techniques in competitive coevolution. "Competitive fitness sharing" changes the way fitness is measured; "shared sampling" provides a method for selecting a strong, diverse set of parasites; and the "hall of fame" encourages arms races by saving good individuals from prior generations. We provide several different motivations for these methods and mathematical insights into their use. Experimental comparisons are done, and a detailed analysis of these experiments is presented in terms of testing issues, diversity, extinction, arms race progress measurements, and drift.
---
paper_title: Tracking the Red Queen: Measurements of Adaptive Progress in Co-Evolutionary Simulations

paper_content:

Co-evolution can give rise to the “Red Queen effect”, where interacting populations alter each other's fitness landscapes. The Red Queen effect significantly complicates any measurement of co-evolutionary progress, introducing fitness ambiguities where improvements in performance of co-evolved individuals can appear as a decline or stasis in the usual measures of evolutionary progress. Unfortunately, no appropriate measures of fitness given the Red Queen effect have been developed in artificial life, theoretical biology, population dynamics, or evolutionary genetics. We propose a set of appropriate performance measures based on both genetic and behavioral data, and illustrate their use in a simulation of co-evolution between genetically specified continuous-time noisy recurrent neural networks which generate pursuit and evasion behaviors in autonomous agents.
---
paper_title: Coevolving Predator and Prey Robots: Do Arms Races Arise in Artificial Evolution?

paper_content:

Coevolution (i.e., the evolution of two or more competing populations with coupled fitness) has several features that may potentially enhance the power of adaptation of artificial evolution. In particular, as discussed by Dawkins and Krebs, competing populations may reciprocally drive one another to increasing levels of complexity by producing an evolutionary "arms race." In this article we will investigate the role of coevolution in the context of evolutionary robotics. In particular, we will try to understand in what conditions coevolution can lead to "arms races." Moreover, we will show that in some cases artificial coevolution has a higher adaptive power than simple evolution. Finally, by analyzing the dynamics of coevolved populations, we will show that in some circumstances well-adapted individuals would be better advised to adopt simple but easily modifiable strategies suited for the current competitor strategies rather than incorporate complex and general strategies that may be effective against a wide range of opposing counter-strategies.
---
paper_title: New Methods for Competitive Coevolution

paper_content:

We consider "competitive coevolution," in which fitness is based on direct competition among individuals selected from two independently evolving populations of "hosts" and "parasites." Competitive coevolution can lead to an "arms race," in which the two populations reciprocally drive one another to increasing levels of performance and complexity. We use the games of Nim and 3-D Tic-Tac-Toe as test problems to explore three new techniques in competitive coevolution. "Competitive fitness sharing" changes the way fitness is measured; "shared sampling" provides a method for selecting a strong, diverse set of parasites; and the "hall of fame" encourages arms races by saving good individuals from prior generations. We provide several different motivations for these methods and mathematical insights into their use. Experimental comparisons are done, and a detailed analysis of these experiments is presented in terms of testing issues, diversity, extinction, arms race progress measurements, and drift.
---
paper_title: Pareto coevolution: using performance against coevolved opponents in a game as dimensions for Pareto selection

paper_content:

When using an automatic discovery method to find a good strategy in a game, we hope to find one that performs well against a wide variety of opponents. An appealing notion in the use of evolutionary algorithms to coevolve strategies is that the population represents a set of different strategies against which a player must do well. Implicit here is the idea that different players represent different "dimensions" of the domain, and being a robust player means being good in many (preferably all) dimensions of the game. Pareto coevolution makes this idea of "players as dimensions" explicit. By explicitly treating each player as a dimension, or objective, we may then use established multi-objective optimization techniques to find robust strategies. In this paper, we apply Pareto coevolution to Texas Hold'em poker, a complex real-world game of imperfect information. The performance of our Pareto coevolution algorithm is compared with that of a conventional genetic algorithm and shown to be promising.
---
paper_title: Co-evolving parasites improve simulated evolution as an optimization procedure

paper_content:

This paper shows an example of how simulated evolution can be applied to a practical optimization problem, and more specifically, how the addition of co-evolving parasites can improve the procedure by preventing the system from sticking at local maxima. Firstly an optimization procedure based on simulated evolution and its implementation on a parallel computer are described. Then an application of this system to the problem of generating minimal sorting networks is described. Finally it is shown how the introduction of a species of co-evolving parasites improves the efficiency and effectiveness of the procedure.
---
paper_title: Coevolving Predator and Prey Robots: Do Arms Races Arise in Artificial Evolution?

paper_content:

Coevolution (i.e., the evolution of two or more competing populations with coupled fitness) has several features that may potentially enhance the power of adaptation of artificial evolution. In particular, as discussed by Dawkins and Krebs, competing populations may reciprocally drive one another to increasing levels of complexity by producing an evolutionary "arms race." In this article we will investigate the role of coevolution in the context of evolutionary robotics. In particular, we will try to understand in what conditions coevolution can lead to "arms races." Moreover, we will show that in some cases artificial coevolution has a higher adaptive power than simple evolution. Finally, by analyzing the dynamics of coevolved populations, we will show that in some circumstances well-adapted individuals would be better advised to adopt simple but easily modifiable strategies suited for the current competitor strategies rather than incorporate complex and general strategies that may be effective against a wide range of opposing counter-strategies.
---
paper_title: New Methods for Competitive Coevolution

paper_content:

We consider "competitive coevolution," in which fitness is based on direct competition among individuals selected from two independently evolving populations of "hosts" and "parasites." Competitive coevolution can lead to an "arms race," in which the two populations reciprocally drive one another to increasing levels of performance and complexity. We use the games of Nim and 3-D Tic-Tac-Toe as test problems to explore three new techniques in competitive coevolution. "Competitive fitness sharing" changes the way fitness is measured; "shared sampling" provides a method for selecting a strong, diverse set of parasites; and the "hall of fame" encourages arms races by saving good individuals from prior generations. We provide several different motivations for these methods and mathematical insights into their use. Experimental comparisons are done, and a detailed analysis of these experiments is presented in terms of testing issues, diversity, extinction, arms race progress measurements, and drift.
---

Title: A Review of Landmark Articles in the Field of Co-evolutionary Computing

Section 1: INTRODUCTION
Description 1: Introduce evolutionary algorithms and focus on co-evolution, the scope of the paper, criteria used for article selection, and the paper's structure.

Section 2: REVIEW OF THE SELECTED ARTICLES
Description 2: Provide a thorough review of each of the selected articles in chronological order, summarizing their approaches, results, and any criticisms.

Section A: Co-evolving Parasites Improve Simulated Evolution As an Optimization Procedure
Description A: Discuss Hillis's work on applying co-evolution to evolutionary computation using a competitive evolution scenario for improving sorting networks.

Section B: Co-evolutionary Constraint Satisfaction
Description B: Explain Jan Paredis's work on applying co-evolution to Constraint Satisfaction Problems, detailing the predator-prey model used.

Section C: Evolving Complex Structures via Cooperative Coevolution
Description C: Describe De Jong and Potter's approach to using coevolution to evolve modular solutions for function optimization and robot task learning.

Section D: New Methods for Competitive Coevolution
Description D: Summarize Rosin and Belew's introduction of new competitive coevolutionary techniques using game theory, focusing on Nim and 3D tic-tac-toe.

Section E: Coevolving Predator and Prey Robots: Do "Arms Races" Arise in Artificial Evolution?
Description E: Discuss Nolfi and Floreano's research on the "arms race" phenomenon in competitive coevolution using predator-prey robot scenarios.

Section 3: DISCUSSION
Description 3: Compare and contrast the competitive and cooperative approaches in coevolutionary algorithms, discussing their strengths, weaknesses, and typical problems.

Section 4: CONCLUSIONS
Description 4: Summarize the insights gained from the reviewed articles, the effectiveness of coevolutionary algorithms, and the need for problem-dependent considerations in their application.