Abstract
This paper explores the evolutionary design of multi-agent systems, specifically focusing on collaborative evolutionary methods. We expose potential drawbacks of these methods and demonstrate that for a non-trivial problem called the "blind mice" problem, a classical Genetic Algorithm (GA) approach—in which whole populations are evaluated, selected, and crossed together—finds an elegant and non-intuitive solution more efficiently than cooperative coevolution. The performance gap widens as the number of agents increases. We propose that the poorer performance of cooperative coevolution stems from the intrinsic fragility of the evaluation process in highly interdependent environments, supported by both theoretical and experimental evidence.
Introduction
In the evolutionary design of multi-agent systems, researchers often aim to evolve teams of heterogeneous agents that can collaborate. A popular method for this is cooperative coevolution, where agents are evolved in separate sub-populations (pools) and evaluated by teaming them up with agents from other pools.
However, cooperative coevolution has a significant vulnerability: as the number of agents grows, the influence of a single agent on the team's overall performance shrinks, making accurate evaluation difficult. Furthermore, in environments with random elements (stochasticity), a high-performing agent might receive a poor fitness score by pure chance. This paper investigates whether for problems requiring highly interdependent teamwork, it is more effective to evolve the entire team as a single genetic individual.
The Blind Mice Problem
To test these approaches, we introduced the Blind Mice Problem. In this simulation, a flock of mice (controlled by neural networks) must escape cats in a toroidal (wrap-around) world. While the mice are faster than the cats, they are "blind"—they cannot see the cats or each other. Their only sensory input is the X/Y coordinates of the flock's center of gravity.
Because the mice only know the center of gravity, survival requires incredible coordination. The GA reliably evolved a brilliant, non-intuitive strategy: most mice clump together in a tight ball, while one specific mouse (the "Dancer") runs in a fast, sinuous path far away from the flock. Because the cats always chase the closest mouse, they endlessly pursue the Dancer, leaving the flock safe.
Methodology
We compared two primary evolutionary approaches:
- Cooperative Coevolution (Baseline): Agents are kept in separate pools. To evaluate an agent, it is grouped with the current "best" agents from all the other pools.
- Population-Oriented Genetic Algorithm: The algorithm treats an entire multi-agent system (the whole team) as a single individual. To manage the massive search space, we introduced an inner crossover operator. When two parent teams are crossed, the algorithm occasionally crosses the neural network weights of individual agents from the parents to create entirely new, hybrid agents for the offspring.
Results and Discussion
The population-oriented GA successfully found the optimal strategy in 100% of runs, regardless of team size. In contrast, cooperative coevolution struggled significantly. With 7 mice, it was less efficient than the GA; with 15 mice, it mostly failed to converge even after 10,000 evaluations.
Cooperative coevolution failed due to the highly interdependent nature of the Dancer strategy. If a stochastic variation causes a great Dancer to get caught during evaluation, it is assigned a poor fitness score and replaced. This replacement ruins the evaluation context for all other pools—the flock gets eaten because there is no Dancer to protect them, causing the algorithm to discard the good flock agents as well. This cascading ecosystem collapse is avoided by evaluating whole populations, as a bad run only affects that specific team rather than corrupting a shared pool of "best" agents.
Conclusion
For multi-agent problems characterized by high interdependence and stochasticity, evaluating whole populations can be more effective than coevolving individuals. The success of this approach relies on specialized operators like inner crossover to navigate the expanded search space. Future work will explore further genetic operators to enhance search efficiency in these complex landscapes.
Summary updated