Evolutionary Algorithms — From Biology to Code

1. The Evolutionary Computation Landscape

All EAs maintain a population of candidate solutions and iteratively improve it using nature-inspired operators. The main families are:

The generic loop shared by all EAs:

2. Genetic Algorithms — Representation & Operators

Representation

A chromosome encodes a candidate solution. Common encodings include:

• Binary string: each gene is 0 or 1. Classic for subset selection or discrete parameters.
• Real-valued vector: each gene is a floating-point number. Common for neural network weights.
• Permutation: genes are a permutation of integers 1…n. Used for routing, scheduling, TSP.

Crossover

Crossover combines genes from two parents. For permutation representations, standard crossover breaks the ordering constraint; specialised operators are needed:

• Order Crossover (OX): copy a sub-segment from parent A; fill remaining positions in the order they appear in parent B.
• Partially Mapped Crossover (PMX): swaps a segment between parents and repairs conflicts with a positional mapping.

Mutation

Mutation introduces diversity to escape local optima. For permutations:

• Swap mutation: pick two random positions and swap their genes.
• 2-opt inversion: reverse a random sub-segment. Particularly effective for TSP.
• Insertion mutation: remove a gene from one position and insert it elsewhere.

3. Selection Pressure and Fitness Scaling

Tournament selection: pick k individuals at random and keep the best. k = 2 is common — easy to implement, controllable pressure (larger k = more pressure).

Roulette wheel (fitness-proportionate) selection: each individual is selected with probability proportional to its fitness. Susceptible to domination by a single super-fit individual early in the run (premature convergence).

Rank-based selection: sort by fitness; assign selection probability by rank position rather than raw fitness. More robust than roulette; controllable linear or exponential rank scaling.

4. Evolution Strategies and Self-Adaptation

Evolution Strategies (ES) work directly in ℝⁿ with Gaussian mutation. Each individual carries both the parameter vector x and a step-size vector σ that evolves alongside it:

The common notation (μ + λ)-ES maintains μ parents and generates λ offspring; all μ + λ individuals compete for the next generation. (μ, λ)-ES discards all parents, enforcing more aggressive exploration.

Rechenberg's 1/5 success rule is a simpler alternative: if more than 20% of mutations improve fitness, increase σ by a factor of 1.22; below 20%, decrease by the same factor. When no self-adaptation is available, this rule maintains a good step size automatically.

5. CMA-ES — Covariance Matrix Adaptation

CMA-ES (covariance matrix adaptation evolution strategy, Hansen & Ostermeier 2001) is the current gold standard for derivative-free continuous optimisation up to a few hundred dimensions. It learns the full covariance matrix of the search distribution:

The mathematical details are involved, but the high-level intuition is elegant: C captures the shape of the fitness landscape locally. After many iterations, the eigenvectors of C align with the "easy directions" of the landscape, allowing CMA-ES to make much more effective steps than a fixed spherical distribution.

CMA-ES has O(n²) cost per generation and is recommended for n ≤ 200–300. For higher dimensions, separable CMA-ES (diagonal C only) extends it to thousands of variables.

6. JavaScript: GA for the Travelling Salesman Problem

// TSP: find the shortest tour through N cities
// Chromosome: permutation of city indices [0 .. N-1]

function tourDistance(cities, tour) {
  let d = 0;
  for (let i = 0; i < tour.length; i++) {
    const a = cities[tour[i]];
    const b = cities[tour[(i + 1) % tour.length]];
    d += Math.hypot(b.x - a.x, b.y - a.y);
  }
  return d;
}

// Order Crossover (OX)
function oxCrossover(p1, p2) {
  const n  = p1.length;
  const i1 = Math.floor(Math.random() * n);
  const i2 = Math.floor(Math.random() * n);
  const [lo, hi] = [Math.min(i1, i2), Math.max(i1, i2)];
  const segment = new Set(p1.slice(lo, hi));
  const child = p1.slice(lo, hi);
  for (const gene of p2) if (!segment.has(gene)) child.push(gene);
  return [...child.slice(n - lo), ...child.slice(0, n - lo)];
}

// 2-opt inversion mutation
function mutate(tour, rate) {
  if (Math.random() > rate) return tour;
  const i = Math.floor(Math.random() * tour.length);
  const j = Math.floor(Math.random() * tour.length);
  const [lo, hi] = [Math.min(i, j), Math.max(i, j)];
  return [
    ...tour.slice(0, lo),
    ...tour.slice(lo, hi + 1).reverse(),
    ...tour.slice(hi + 1),
  ];
}

function runGA(cities, { popSize = 100, generations = 500, mutRate = 0.1, eliteN = 5 } = {}) {
  const n = cities.length;

  // Initialise with random permutations
  let pop = Array.from({ length: popSize }, () =>
    [...Array(n).keys()].sort(() => Math.random() - 0.5));

  for (let gen = 0; gen < generations; gen++) {
    // Evaluate (lower distance = higher fitness)
    pop.sort((a, b) => tourDistance(cities, a) - tourDistance(cities, b));

    // Elitism: keep top eliteN unchanged
    const nextPop = pop.slice(0, eliteN);

    while (nextPop.length < popSize) {
      // Tournament selection (k=3)
      const tournament = () => {
        let best = pop[Math.floor(Math.random() * pop.length)];
        for (let k = 1; k < 3; k++) {
          const c = pop[Math.floor(Math.random() * pop.length)];
          if (tourDistance(cities, c) < tourDistance(cities, best)) best = c;
        }
        return best;
      };
      const child = mutate(oxCrossover(tournament(), tournament()), mutRate);
      nextPop.push(child);
    }
    pop = nextPop;
  }
  return pop[0];   // best tour
}

// Example: 10 random cities
const cities = Array.from({ length: 10 }, () =>
  ({ x: Math.random() * 100, y: Math.random() * 100 }));
const best = runGA(cities);
console.log('Best tour:', best);
console.log('Distance:', tourDistance(cities, best).toFixed(2));

7. Common Pitfalls and Tuning

Premature Convergence

The population loses diversity and gets stuck in a local optimum before finding the global one. Remedies: reduce selection pressure (smaller tournament size); increase mutation rate; use geographic niching (island model with migration); restart. Population diversity can be monitored cheaply by computing average pairwise Hamming distance.

Bloat (Genetic Programming)

In grammatical or tree-based representations, programs grow without bound ("bloat") while fitness stagnates. Parsimony pressure (penalising longer programs) or strict size limits prevent this.

Choosing Hyperparameters

• Population size: typically 50–200 for GA; 4 + ⌊3 ln n⌋ for CMA-ES.
• Mutation rate: ~1/n for binary GA (flip one bit per chromosome); 0.1–0.3 for permutation GA.
• Crossover rate: 0.6–0.9 for binary; 1.0 for permutation (always cross).
• Budget: run until stagnation (no improvement for 50 generations), then restart.

8. Applications

Neural Architecture Search (NAS)

Evolutionary methods (NEAT, regularised evolution) discover neural network topologies and weights simultaneously — encoding network graph structure as a chromosome. Google's AmoebaNet found state-of-the-art image classifiers with evolutionary search.

Drug Discovery

Molecular structures are represented as SMILES strings or molecular graphs. EAs explore chemical space by mutating functional groups and crossing molecular scaffolds, guided by predicted binding affinity from a surrogate model (often a graph neural network).

Scheduling and Logistics

Job-shop scheduling, vehicle routing, satellite observation scheduling, and airline crew pairing are all complex combinatorial problems where GAs with domain-specific operators are competitive with (or superior to) specialised exact solvers.