When Evolving Populations is Better than Coevolving Individuals: The Blind Mice Problem

TL;DR

This paper argues that for certain complex multi-agent problems, a standard genetic algorithm applied to entire populations of agents can outperform cooperative coevolution. The authors demonstrate this on the "blind mice" problem, showing that the fragility of cooperative coevolution's evaluation process in the face of stochasticity leads to oscillations and slower convergence compared to a population-based GA with an "inner crossover" mechanism.

What Problem Does This Paper Address?

The paper tackles the challenge of evolving collaborating populations of agents, a growing area in artificial intelligence and evolutionary computation. While many evolutionary algorithms focus on optimizing individual agents, real-world systems often require multiple agents to work together. Cooperative coevolution (CC) is a popular approach where different types of agents (or roles) evolve in separate subpopulations, and individuals are evaluated based on their contribution to a team. However, CC can be computationally expensive and, as this paper suggests, potentially fragile. The authors question whether simpler, population-level evolutionary approaches might be more efficient and robust for certain problems, particularly those with inherent stochasticity and strong interdependencies between agents.

Methods

The paper compares two main approaches:

  • Population-Oriented Genetic Algorithm (POGA): This is a modified canonical Genetic Algorithm (GA). Instead of evolving individual agents, entire populations of agents are treated as individuals. The key innovation is an "inner crossover" operator, which allows for the creation of new agents by combining genetic material from two parent agents within a population. This is analogous to standard GA crossover but operates at the agent level within a population.
  • Cooperative Coevolution (CC): The paper describes a standard CC approach, specifically referencing methods like CCGA-1 (Enforced Subpopulations - ESP), where each agent is evaluated with a fixed set of collaborators (e.g., the best from other subpopulations). The evaluation of an individual agent is based on the performance of the entire team it's part of.

The "blind mice" problem is used as a benchmark. Mice, controlled by neural networks, must escape cats. Mice only know the center of their flock and cannot see cats or each other. Cats always chase the nearest mouse.

Datasets

Not discussed in the paper. The "blind mice" problem is presented as a novel benchmark task designed to highlight the differences between the evolutionary approaches.

Key Insights and Ideas

  • Fragility of Cooperative Coevolution: The core insight is that CC's evaluation process, which relies on assessing individual agent contributions within a team, can be inherently fragile. When the evaluation involves stochastic elements (common in simulations), small errors in assessing an agent's performance can have cascading negative effects across the entire system, leading to oscillations and instability.
  • Inner Crossover for Agent Evolution: The paper highlights the effectiveness of "inner crossover" in a population-based GA. This mechanism allows for the creation of novel agent behaviors by combining existing ones, which is crucial for exploring the search space and adapting to complex interdependencies.
  • Population-Level Adaptation vs. Subpopulation Optimization: The study suggests that for problems requiring highly interdependent agent behaviors, optimizing individual agents in isolation (as CC does) might be less effective than evolving entire populations where interdependencies emerge naturally through population-level selection and crossover.
  • The "Blind Mice" Problem as a Revealing Benchmark: The problem's design, with its information asymmetry and strong agent interdependencies, effectively exposes the limitations of CC and the strengths of the POGA.

Key Results

  • POGA Outperforms CC: On the "blind mice" problem, the population-oriented GA with inner crossover significantly outperformed cooperative coevolution.
  • Faster Convergence: The POGA converged to a successful strategy more efficiently, requiring fewer evaluations.
  • Stable Performance: The POGA achieved stable, effective strategies, whereas CC exhibited significant oscillations in performance, often converging and then diverging.
  • Successful Strategy: Both methods, when successful, evolved a similar "dancer" strategy where one mouse attracts cats away from the main flock, which then moves together.

Limitations and Future Work

  • Limited Scope of CC: The paper focuses on a specific type of CC (ESP/CCGA-1) and acknowledges that other CC variants exist. However, the core argument about evaluation fragility is presented as a general pitfall.
  • Stochasticity as the Key Factor: The authors emphasize that the fragility of CC is particularly pronounced in problems with stochastic evaluation. The paper doesn't extensively explore how CC might perform in purely deterministic environments.
  • Future Work: The paper suggests exploring more elaborate schemes for CC to mitigate fragility, but also implies that for certain problems, the population-based approach is fundamentally more robust. Further investigation into the types of problems where CC excels versus where POGA is superior is a natural next step.

Summary updated

Abstract

This paper is about the evolutionary design of multi-agent systems. An important part of recent research in this domain has been focusing on collaborative revolutionary methods. We expose possible drawbacks of these methods, and show that for a non-trivial problem called the "blind mice" problem, a classical GA approach in which whole populations are evaluated, selected and crossed together (with a few tweaks) finds an elegant and non-intuitive solution more efficiently than cooperative coevolution. The difference in efficiency grows with the number of agents within the simulation. We propose an explanation for this poorer performance of cooperative coevolution, based on the intrinsic fragility of the evaluation process. This explanation is supported by theoretical and experimental arguments.
BibTeX
@inproceedings{2003when,
  title = {{When Evolving Populations is Better than Coevolving Individuals: The Blind Mice Problem}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2003},
}
Figure