The "Multicultural" Edge: Boosting Distributed EAs via Diversity-Driven Migration

TL;DR

In the world of parallel Evolutionary Algorithms (EAs), "sending your best" might actually be a recipe for failure. This paper reveals that selecting migrants based on their genotypic difference from the receiving population—rather than just their fitness—prevents premature convergence and significantly reduces the computational effort required to solve deceptive, multimodal problems.

The Diversity Trap in Island Models

Parallel EAs typically use the Island Model, where subpopulations evolve in isolation and occasionally exchange individuals. The conventional wisdom is to migrate the "best" individuals to spread high-quality genes.

However, the authors point out a critical flaw: if a highly fit immigrant is too similar to the target population, it adds nothing new. Conversely, if it is too superior and dominates the genetic pool too quickly, it causes a diversity collapse. This is akin to inbreeding in biology; without "new blood," the system stagnates in local optima.

Methodology: The "Multikulti" Approach

Inspired by biological Mate Choice (specifically the MHC complex in vertebrates where individuals prefer genotypically different mates), the authors propose the Multikulti policy.

1. Representing the "The Other"

An emitting island needs to know what the target island looks like without transferring the whole population (which would kill bandwidth). The authors test two proxies:

• Best Representation: Using the target island's best individual.
• Consensus Sequence: A "synthetic" individual representing the most frequent alleles in the target population—a condensed genetic snapshot.

2. Selective Difference

Instead of just picking the most different individual (which might have terrible fitness), the method creates an elite pool of the best individuals and then selects the one from that pool that is most distant (using Hamming distance) from the target population's proxy.

Experimental Showdown

The authors tested these policies on demanding benchmarks, including the P-Peaks problem and the Massively Multimodal Deceptive Problem (MMDP).

Key Findings:

• The Elite Size Sweet Spot: Simply picking the most different individual in the whole population fails. Success requires a balance—picking a diverse individual from a high-quality elite (size 4 or 8).
• Entropy Matters: The Multikulti policies maintained significantly higher Shannon entropy (diversity) throughout the run, whereas "Best" migration caused entropy to plummet.
• Scalability: As the number of nodes increases from 2 to 8, the advantage of Multikulti policies becomes even more pronounced, as shown in the table below:

Critical Insight: Why Does It Work?

The success of this method validates the Intermediate Disturbance Hypothesis. Migration acts as a disturbance. If you migrate the best individual, the disturbance is too high (conquest effect). If you migrate a random one, it might be too low. The Multikulti approach provides an optimal disturbance—strong enough to introduce useful new material, but distinct enough to prevent the "conquest" of the receiving island.

Conclusion & Future Outlook

This paper shifts the focus of Island Models from "Fitness Diffusion" to "Diversity Maintenance." While the study focused on discrete strings, the logic of consensus-sequence representation could easily be extended to continuous domains or even neural architecture search (NAS).

Limitations: The current model assumes a ring topology. It remains to be seen how these policies perform in more complex, dynamic network topologies (like small-world networks) where the risk of rapid "gene flow" is even higher.