Genetic Algorithms & Evolutionary Computation

Key Topics

• 1. Fitness-Proportionate Selection & Tournament Selection
• 2. Schema Theorem & Building Blocks Hypothesis
• 3. Crossover Operators & Schema Disruption
• 4. Mutation & Exploration-Exploitation Balance
• 5. Convergence Theory & No Free Lunch Theorem
• 6. Multi-Objective Optimization & Pareto Fronts
• 7. Advanced Variants: GP, DE, CMA-ES, NEAT
• 8. Applications in Science

The Genetic Algorithm Framework

Every generation of a GA follows this cycle:

The algorithm terminates when a stopping criterion is met: maximum generations, fitness threshold, or convergence detection. The best individual found across all generations is returned as the solution.

Selection Intensity & Takeover Time

The selection intensity measures how strongly selection shifts the population mean. Under proportionate selection, the best individual with fitness $f_{\max}$ receives $f_{\max}/\bar{f}$ expected copies per generation. After $t$ generations of selection only (no crossover or mutation), the number of copies of the best individual grows as:

The takeover time $t^*$ is when the best individual fills the entire population ($n_{\text{best}} = N$):

Problem: Premature Convergence

Proportionate selection suffers from premature convergence: early in the search, a single super-individual can dominate, reducing diversity before the search space is adequately explored. Several alternatives address this.

Tournament Selection

Select $k$ individuals uniformly at random, then choose the best. For tournament size $k$, the probability that the $i$-th ranked individual (rank 1 = best) wins is:

Tournament selection is preferred in practice because: (a) selection pressure is controlled by $k$, independent of fitness scaling; (b) it requires only ordinal comparisons; (c) it parallelizes trivially.

Rank Selection

Assign selection probabilities based on rank rather than raw fitness. For linear ranking with selective pressure $s \in [1.0, 2.0]$:

Boltzmann Selection

Inspired by simulated annealing, use a temperature $T$ to control selection pressure:$P_i \propto e^{f_i/T}$. High $T$ gives near-uniform selection (exploration); low $T$ sharpens selection toward the best (exploitation). Annealing $T$ over generations provides adaptive control.

Schema Properties

For a schema $H$ over chromosomes of length $L$:

• Order $o(H)$: The number of fixed (non-$*$) positions. Example: $o(1**0*1) = 3$
• Defining length $\delta(H)$: The distance between the outermost fixed positions. Example: $\delta(1**0*1) = 5$ (positions 0 to 5)
• Fitness $f(H)$: The average fitness of all individuals matching schema $H$
• Count $m(H, t)$: The number of individuals matching$H$ at generation $t$

Deriving the Growth Equation

Step 1: Selection. Under proportionate selection, the expected number of representatives of $H$ after selection is:

Step 2: Crossover survival. A schema survives single-point crossover if the crossover point does not fall within the defining length. The crossover point is chosen uniformly from $L-1$ positions, so the disruption probability is:

With crossover probability $p_c$, the survival probability is at least$1 - p_c \cdot \delta(H)/(L-1)$ (a lower bound, since crossover with a matching partner preserves the schema).

Step 3: Mutation survival. Each fixed position must survive mutation (probability $1 - p_m$ per bit). With $o(H)$ fixed positions:

Combining all three effects yields the Schema Theorem:

Implications: Building Blocks

The Schema Theorem shows that schemata which are simultaneously:

• Short (small $\delta(H)$): survive crossover with high probability
• Low-order (small $o(H)$): survive mutation with high probability
• Above-average ($f(H) > \bar{f}$): receive more copies through selection

grow exponentially in the population. These are called building blocks. The building blocks hypothesis states that GAs work by identifying, preserving, and combining these short, fit schemata into complete high-fitness solutions.

Implicit parallelism: A population of $N$ binary strings of length $L$ contains instances of at least $2^k$ different schemata (where $k \approx L$ for reasonable populations), yet requires only $N$ fitness evaluations per generation. Holland estimated that $O(N^3)$ schemata are usefully processed — a massive parallel search with linear computational cost.

Single-Point Crossover

Choose a random crossover point $c \in \lbrace 1, 2, \ldots, L-1\rbrace$ uniformly. Swap the segments after position $c$ between two parents. A schema $H$ with defining length $\delta(H)$ is disrupted if $c$ falls between the outermost fixed positions:

Therefore, the survival probability is:$P_{\text{survive}}^{1\text{pt}}(H) = 1 - \frac{\delta(H)}{L-1}$. Short schemata ($\delta(H) \ll L$) are almost never disrupted.

Two-Point Crossover

Choose two crossover points and swap the segment between them. A schema survives if neither crossover point falls within the defining length, or both fall within it (the defining region is swapped out and back). The disruption probability is:

Two-point crossover is less positional-biased than single-point: it treats the chromosome more like a ring than a linear string, reducing the advantage of schemata located at the ends.

Uniform Crossover

At each position independently, exchange the bit between parents with probability$p_0$ (typically $p_0 = 0.5$). A schema $H$ with order$o(H)$ survives if none of its fixed positions are exchanged:

Note that this depends only on the order, not the defining length. This is a fundamental difference: uniform crossover is less disruptive for compact schemata (many fixed positions clustered together) but more explorative overallsince it can recombine any subset of positions.

For $p_0 = 0.5$ and $o(H) = 5$:$P_{\text{survive}} = 0.5^5 = 0.03125$, while single-point crossover on the same schema might yield $P_{\text{survive}} = 1 - 5/99 = 0.95$ for$L = 100$. Thus uniform crossover is far more disruptive for high-order schemata but provides superior mixing of alleles from different regions of the chromosome.

Optimal Mutation Rate

For a binary chromosome of length $L$, each bit is flipped independently with probability $p_m$. The expected number of mutations per chromosome is$L \cdot p_m$. The classic result for the optimal mutation rate is:

This gives exactly one expected bit flip per chromosome. The derivation follows from balancing exploration and exploitation:

Exploration requirement: The probability that a specific bit position is mutated in at least one individual across the population of size $N$ is:

For adequate exploration, we need $P_{\text{explore}}$ to be significant, requiring $p_m \gtrsim 1/N$.

Exploitation requirement: The probability that a good chromosome (a building block of order $o(H)$) survives mutation is $(1 - p_m)^{o(H)}$. For the entire chromosome ($o(H) = L$), the survival probability is:

At $p_m = 1/L$, this gives $P_{\text{survive}} \approx e^{-1} \approx 0.37$, meaning about 37% of individuals survive without any mutation — a reasonable balance. Higher rates destroy too much structure; lower rates explore too slowly.

Mutation & Deceptive Problems

A problem is deceptive if low-order building blocks mislead the search toward a suboptimal solution. Formally, a deceptive function of order $k$ has the property that:

Without mutation, a GA using only selection and crossover converges to a suboptimal solution with probability 1 on deceptive problems. Mutation provides the random jumps needed to escape deceptive basins. This can be proven by noting that without mutation, once an allele is lost from the population it can never be recovered — making the GA equivalent to a greedy search on schemata.

Consequences for Genetic Algorithms

The NFL theorem implies that GAs must exploit problem structureto outperform random search. The specific structure GAs exploit is the building block structure: fitness functions where short, low-order schemata provide reliable information about the global optimum.

GAs provably outperform hill climbing on problems with:

• Multimodal landscapes: Many local optima trap hill climbers, but GAs maintain population diversity to search multiple basins simultaneously
• Deceptive landscapes: Where local gradient information leads away from the global optimum, but building blocks at higher orders point correctly
• Rugged landscapes: Where small changes in the input cause large changes in fitness, making gradient estimation unreliable
• Non-differentiable or discrete spaces: Where gradient methods are inapplicable (e.g., combinatorial optimization, symbolic search)

Conversely, on smooth unimodal landscapes, gradient descent vastly outperforms GAs — and the NFL theorem tells us this advantage must be balanced by the GA's advantage elsewhere.

Pareto Dominance

For a minimization problem with $M$ objectives, solution $\mathbf{x}$ dominates solution $\mathbf{y}$ (written $\mathbf{x} \prec \mathbf{y}$) if and only if:

The Pareto front is the set of all non-dominated solutions: no solution in the Pareto set can improve on one objective without worsening another.

NSGA-II: Non-Dominated Sorting

The NSGA-II algorithm (Deb et al., 2002) is the most widely used multi-objective GA. It ranks solutions by non-dominated sorting:

• Front 1 (rank 1): All non-dominated solutions in the population
• Front 2 (rank 2): Non-dominated solutions after removing Front 1
• Front $k$: Non-dominated solutions after removing Fronts $1, \ldots, k-1$

The algorithm for each solution $p$: compute $n_p$ (number of solutions dominating $p$) and $S_p$ (set of solutions dominated by $p$). Front 1 consists of all $p$ with $n_p = 0$. For each $p$ in Front 1, decrement $n_q$ for all $q \in S_p$; those reaching $n_q = 0$ form Front 2, and so on. Complexity: $O(MN^2)$.

Crowding Distance

Within each front, NSGA-II uses crowding distance to maintain diversity. For solution $i$ in a front, the crowding distance is:

where $f_m^{(i+1)}$ and $f_m^{(i-1)}$ are the objective values of the neighboring solutions when sorted by objective $m$. Solutions with higher crowding distance are preferred, promoting a well-spread Pareto front.

Hypervolume Indicator

The hypervolume indicator (HV) measures the quality of a Pareto front approximation. Given a reference point $\mathbf{r}$ (dominated by all solutions), the hypervolume is the $M$-dimensional volume of the space dominated by the Pareto front and bounded by $\mathbf{r}$:

The hypervolume is the only unary quality indicator known to be strictly monotonic with respect to Pareto dominance: if set $A$ dominates set $B$, then$\text{HV}(A) > \text{HV}(B)$. For two objectives, computing HV is $O(n \log n)$; for $M$ objectives, the exact computation is $\#P$-hard.

Differential Evolution (DE)

DE (Storn & Price, 1997) operates on real-valued vectors. For each target vector $\mathbf{x}_i$, a donor vector is created by:

where $r_1, r_2, r_3$ are distinct random indices and $F \in [0, 2]$ is the scale factor. The mutation$F(\mathbf{x}_{r_2} - \mathbf{x}_{r_3})$ is a scaled difference vector, which automatically adapts to the local geometry of the search space: when the population is spread out, mutations are large; as it converges, they shrink.

A trial vector is formed by binomial crossover with rate $CR$, and replaces$\mathbf{x}_i$ only if it has better fitness (greedy selection). DE is remarkably effective for continuous optimization with few control parameters.

CMA-ES: Covariance Matrix Adaptation

CMA-ES (Hansen & Ostermeier, 2001) is arguably the most sophisticated evolutionary strategy. It maintains a multivariate normal distributionand adapts its covariance matrix to learn the local landscape geometry:

The covariance matrix adaptation updates $\mathbf{C}$using two complementary mechanisms:

• Rank-one update (evolution path): $\mathbf{C} \leftarrow (1-c_1)\mathbf{C} + c_1 \mathbf{p}_c \mathbf{p}_c^T$, where $\mathbf{p}_c$ tracks the cumulative mean shift
• Rank-$\mu$ update: $\mathbf{C} \leftarrow (1-c_\mu)\mathbf{C} + c_\mu \sum_{i=1}^\mu w_i \mathbf{y}_{i:\lambda}\mathbf{y}_{i:\lambda}^T$, using the $\mu$ best samples

CMA-ES is rotation-invariant, scale-free, and regarded as the gold standard for derivative-free optimization in continuous spaces up to a few hundred dimensions.

Neuroevolution: NEAT

NeuroEvolution of Augmenting Topologies (NEAT, Stanley & Miikkulainen, 2002) evolves both the weights and topology of neural networks. Key innovations:

• Historical markings: Each gene (connection) has a global innovation number enabling meaningful crossover between networks with different topologies
• Speciation: Networks are grouped into species based on structural similarity, protecting innovations through niche protection
• Complexification: Start minimal and grow topology, avoiding the search through unnecessarily large spaces

NASA ST5 Evolved Antenna

In 2006, NASA's ST5 mission flew the first evolved hardware in space: an X-band antenna designed entirely by a GA. The algorithm evolved 3D wire structures evaluated by EM simulation, producing an irregular, asymmetric design no human would create — yet it met all performance requirements with superior radiation patterns.

Materials Science, Astrophysics & Engineering

GAs optimize multi-component alloy compositions for mechanical properties, fit parametric galaxy models to photometry (handling multimodal likelihood surfaces from age-metallicity-dust degeneracies), evolve electronic circuits (analog filters, oscillators), and solve complex scheduling problems (telescope observations, accelerator beam time).