#genetic algorithms #genetic programming #alps #evolution #algorithms

TL;DR The Age Layered Population Structure (ALPS) is a technique for evolutionary algorithms designed to avoid premature convergence and maintain long term diversity during the search. Introduced by Gregory S. Hornby in 2006, it prevents high-fitness "super-individuals" from dominating the population too early.

The central idea is to organise individuals into layers based on their age. Younger individuals compete only with their peers, while older, more refined solutions migrate to progressively higher layers.

Basic idea

In a traditional genetic algorithm, the population often becomes genetically stagnant. Early dominant individuals may take over the population, reducing exploration.

ALPS addresses this by continuously injecting young individuals into the bottom layer and preventing them from competing directly with highly optimised individuals in the upper layers.

Population structure

ALPS divides the population into L layers. Each layer has a specific age limit, often following a non-linear scale to allow more time for refinement in later stages.

Example age scheme 

Layer   Maximum age
0                10
1                30
2                90
3               160
4                 ∞

Defining age

In ALPS, age does not refer to the number of generations an individual has survived, but rather the age of its oldest genetic material.

age(child) = max(age(parent1), age(parent2)) + 1  // crossover
age(child) = age(parent) + 1                      // mutation
age        = 0  // individual inserted in the lowest layer

Parents connect to offspring with edges, and node labels show age

Evolution process

The algorithm evolves each layer almost independently.

For each generation:

  1. selection, crossover and mutation occur within the layer;
  2. if an individual's age exceeds the current layer's limit, it attempts to move to the next layer (promotion). Once there, it participates in the normal replacement process of that layer;
  3. an individual moving up competes with the individuals already in that higher layer. If it's fitter than the weakest member, it replaces it (inter-layer competition).
flowchart TD Start([Generate Offspring]) --> Type{Source?} Type -->|Random| Age0[Age = 0] Type -->|Mutation| AgeM[Age = Parent Age + 1] Type -->|Crossover| AgeC["Age = max(P1, P2) + 1"] Age0 & AgeM & AgeC --> CheckLimit{Age > Layer Limit?} CheckLimit -->|No| Stay[Stay in current layer] CheckLimit -->|Yes| Move[Attempt promotion to next layer] Move --> Fitness{Accepted by next layer?} Fitness -->|Yes| Replace[Replace weakest individual] Fitness -->|No| Discard[Discard offspring] Stay --> Evolve[Participate in next Generation] Replace --> Evolve

Constant injection

The most critical feature of ALPS is that Layer 0 is periodically cleared and re-initialised with brand-new, random individuals (age=0).

This ensures that the search never "finishes" exploring. New genetic material is constantly filtered through the layers; if a new random individual has a promising genetic trajectory, it will eventually age into the higher layers.

Individuals move upward between layers, and new individuals appear in layer 0

Why ALPS works

ALPS effectively balances exploration and exploitation:

  • prevents premature convergence. Because Layer 0 is always fresh, the algorithm cannot get stuck forever;
  • protects innovation. In a standard GA, a new random individual (high potential but low current fitness) would be instantly killed off by an older, "refined" individual. In ALPS, that new individual has a "safe space" in the lower layers to evolve before facing the "elites".