Island Models: What Splitting the Population Actually Buys

A single population genetic algorithm has a fundamental tension: selection pressure pushes toward exploitation of current best solutions, while diversity is needed for exploration of new regions. Push too hard on selection and the population converges prematurely. Maintain too much diversity and progress stalls.

Island models resolve this by running multiple populations in parallel with occasional migration between them. Each island can converge on its own local optimum while migration periodically injects fresh genetic material.

The Original Design

The MATLAB code that became ParGA had a simple approach: evolve four populations independently, then merge the best individuals into one final population:

function obj=evolveCommunities(obj)
    for m=1:obj.numPops
        for j=1:obj.numGenerations
            [obj.nations{1,m},temp]=obj.nations{1,m}.breed;
        end
    end
end

function obj=mergeCommunities(obj)
    newpop=cell(1,obj.pop_size);
    counter=1;
    for m=1:1:obj.numPops
        fitnesses=obj.nations{1,m}.converganceCheck;
        [~,ix]=sort(fitnesses);
        for j=1:1:obj.pop_size/obj.numPops
            if counter<=obj.pop_size
                newpop{1,counter}=obj.nations{1,m}.getPop{1,ix(j)};
                counter=counter+1;
            end
        end
    end
end

This worked, but it was all-or-nothing. Populations evolved in complete isolation, then merged at the end. The modern approach keeps islands connected throughout evolution.

Continuous Migration

Instead of one final merge, ParGA performs periodic migration during evolution. Every N generations, a subset of individuals moves between islands:

for gen in 0..self.config.generations {
    // Evolve each island
    self.evolve_islands();

    // Evaluate fitness
    self.evaluate_all_islands();

    // Migrate if interval reached
    if (gen + 1) % self.config.migration_interval == 0 {
        self.migrate();
    }
}

The key parameters:

• Migration interval: How often migration occurs (default: every 10 generations)
• Migration count: How many individuals migrate per event (default: 5)
• Selection for migration: Best individuals are chosen as migrants

Migrants get their fitness invalidated when they arrive at the destination island. This forces re-evaluation, which matters when islands might have slightly different selective pressures or when fitness evaluation has stochastic elements.

Migration Topologies

The topology determines which islands can exchange individuals. This seemingly small detail has significant effects on algorithm behavior.

Ring Topology

Each island sends migrants to the next island in sequence. Island 0 sends to island 1, island 1 to island 2, and so on, wrapping around at the end.

MigrationTopology::Ring => {
    let dest = (from + 1) % num_islands;
}

Ring is simple and provides moderate connectivity. Information flows slowly around the ring, giving each island time to adapt to incoming migrants before passing them along.

Star Topology

One central hub island exchanges with all satellite islands. The hub sends migrants to every satellite, and every satellite sends migrants back to the hub.

MigrationTopology::Star => {
    if from == 0 {
        (1..num_islands).collect()  // Hub sends to all satellites
    } else {
        vec![0]  // Satellites send to hub
    }
}

Star creates a natural hierarchy. Good solutions found on any satellite quickly reach the hub and can spread to other satellites. This accelerates convergence but can reduce diversity if the hub dominates too quickly.

Ladder Topology

Bidirectional exchange between adjacent islands. Island 0 exchanges with island 1, island 1 exchanges with islands 0 and 2, and so on.

MigrationTopology::Ladder => {
    let mut dests = Vec::new();
    if from > 0 {
        dests.push(from - 1);
    }
    if from < num_islands - 1 {
        dests.push(from + 1);
    }
    dests
}

Ladder preserves more diversity than ring or star because information has to diffuse through the chain. End islands only have one neighbor, making them natural refuges for diverse genetic material.

Fully Connected

Every island can send to every other island.

MigrationTopology::FullyConnected => {
    (0..num_islands).filter(|&i| i != from).collect()
}

Maximum connectivity means fastest information spread, but also fastest convergence. Use this when you want aggressive exploration early and don’t mind rapid convergence.

Random

Migrants go to randomly selected islands each migration event.

MigrationTopology::Random => {
    let mut dest = rng.gen_range(0..num_islands);
    while dest == from {
        dest = rng.gen_range(0..num_islands);
    }
}

Random adds unpredictability that can help escape local optima. It’s the least structured option.

What islands cost at a fixed budget

The case for islands is usually made as diversity: separate subpopulations explore separate regions, so the search is less likely to collapse onto one peak. That is a claim about solution quality, so it should show up when you hold the budget fixed and vary only the structure.

In ParGA, population_size is the total across islands, so splitting it costs nothing extra. 400 individuals for 100 generations is 40,000 evaluations whether that is one population of 400 or sixteen of 25. Ten dimensions, 24 seeds, median best value found:

Splitting the population makes things worse, monotonically, on every function including the multimodal ones islands are supposed to be for. Two islands is a wash. By sixteen, Rastrigin is fifteen times worse than a single population given exactly the same number of evaluations.

The reason is not mysterious once you look at the sizes. Sixteen islands of 25 individuals each is sixteen populations too small to hold much diversity at all. Each one converges fast on whatever its 25 starting points happened to bracket, and migration every ten generations is not enough to rescue that. The diversity you gain between islands costs you more diversity within them.

So why use them

Because that is the wrong comparison, and it is the one the framing invites.

Islands are a parallelism strategy. Each island evolves independently between migrations, which means eight islands run on eight cores in roughly the wall-clock time of one. The real question is not “is 8 x 50 better than 1 x 400”, it is “now that I have eight cores, what do I do with them”.

Same benchmark, but each island keeps a full 100 individuals, so eight islands genuinely costs eight times the evaluations:

Islands are transformative against the small population, thirty times better on Rastrigin. But that is mostly just the eight times more evaluations talking, and the last column proves it: a single population of 800, spending exactly what the eight islands spent, beats them on all three.

So the honest summary is that the island structure is not buying solution quality here. It is buying the ability to spend more evaluations in the same wall-clock, and it gives back a little quality in exchange for that. Which is a good trade when the alternative is not spending them.

Topology, measured

If islands cost a little quality, the topology is where you get some back. All five of ParGA’s topologies, eight islands of 100, 16 seeds:

Ring is the worst on all three functions. Fully connected is the best or within noise of the best on all three. Ladder, which the diagrams above suggest should be the strongest diversity preserver, is mid-table.

That ordering is the opposite of the usual reasoning, which says to restrict migration so islands stay different from each other for longer. On these benchmarks the restriction is simply a delay: a good solution found on island 3 has to walk around the ring to reach island 7, and while it walks, island 7 is spending its generations on something worse.

It also lines up with the first experiment. One big population is the maximum-mixing limit, and it won. Fully connected islands are the closest thing to one big population that still runs in parallel, and they came second. Ring is the most isolated arrangement, and it lost. Every result here points the same direction: on this class of problem, mixing beats isolation.

I would not generalize that to every landscape. A problem with genuinely separated basins of attraction, where premature global convergence is the actual failure mode, is exactly where isolation should pay, and none of these four benchmarks is really that problem. But it does mean ring-by-default deserves more scrutiny than it usually gets.

Using islands in ParGA

from parga import minimize, MigrationTopology

result = minimize(
    fitness,
    genome_length=10,
    bounds=(-5.12, 5.12),
    population_size=800,          # total across islands
    generations=100,
    islands=8,                    # 100 individuals each
    migration_interval=10,
    migration_count=5,
    migration_topology=MigrationTopology.fully_connected(),
)
print(-result.best_fitness)

migration_topology reaches the facade as of this change; before it, GA(islands=N) always used the engine default, which is ring.

When islands are worth it

Use them when you have cores and an expensive fitness function. That is the case they were designed for and the case where the arithmetic works: parallel evaluation buys you more generations per hour than the structure costs you in quality.

Prefer more connectivity than feels right. Fully connected was the best or joint-best choice on all three multimodal benchmarks, and ring the worst.

Don’t split a small population. Below roughly 50 individuals per island the subpopulations stop being able to hold diversity, which is the thing you split them up to preserve.

And check the single-population baseline. It is one line to run, it is the maximum-mixing limit of everything above, and on these functions it is still the best answer per evaluation.