Genetic Algorithm#

A genetic algorithm (GA) is a population-based search method inspired by natural selection. It evolves a set of candidate solutions over generations using selection, crossover and mutation, and needs only the ability to evaluate a solution, not gradients. This makes GAs useful for non-convex, discontinuous or combinatorial problems where calculus-based optimisers struggle.

Problem formulation#

A GA solves

\[x^{*} = \arg\max_{x \in \mathcal{S}} f(x)\]

where \(\mathcal{S}\) is the search space and \(f\) is the fitness function. Minimisation problems are handled by maximising \(-f(x)\) (or \(1 / (1 + f(x))\) when \(f \ge 0\)).

At generation \(t\) the algorithm holds a population of \(N\) individuals

\[P_t = \{x_1^{(t)}, x_2^{(t)}, \dots, x_N^{(t)}\}, \qquad f_i = f\big(x_i^{(t)}\big).\]

The algorithm#

initialise P_0 at random
for t = 0, 1, 2, ... until stopping criterion:
    evaluate f(x) for every x in P_t
    select parents from P_t according to fitness
    create children by crossover with probability p_c
    mutate each gene with probability p_m
    form P_{t+1} from the children (keeping the best e individuals)
return the best individual found

Typical stopping criteria are a maximum number of generations, a fitness target, or no improvement in the best fitness for \(G\) generations.

Encoding#

Each individual is a chromosome made up of genes:

Binary: \(x \in \{0, 1\}^L\). A real variable on \([a, b]\) encoded with \(L\) bits is decoded as

\[x = a + \frac{b - a}{2^L - 1} \sum_{j=0}^{L-1} b_j \, 2^{j},\]

giving a resolution of \((b - a) / (2^L - 1)\).
Real-valued: \(x \in \mathbb{R}^n\), usually with bounds \(l_j \le x_j \le u_j\). This is the natural choice for continuous problems such as model calibration.
Permutation: \(x\) is an ordering of \(\{1, \dots, n\}\), used for scheduling and routing problems.

Selection#

Selection chooses parents, favouring fitter individuals while keeping enough diversity to avoid premature convergence. The strength of this bias is the selection pressure.

Roulette wheel (fitness proportionate). For \(f_i \ge 0\):

\[p_i = \frac{f_i}{\sum_{j=1}^{N} f_j}\]

It is sensitive to the scale of \(f\), so fitness is often linearly scaled first, \(f_i' = a f_i + b\).

Rank selection. Sort the population so that rank \(r_i = 1\) is the worst and \(r_i = N\) the best. With linear ranking:

\[p_i = \frac{1}{N}\left(\eta^{-} + \left(\eta^{+} - \eta^{-}\right)\frac{r_i - 1}{N - 1}\right), \qquad \eta^{+} + \eta^{-} = 2, \quad 1 \le \eta^{+} \le 2\]

where \(\eta^{+}\) controls the selection pressure. Ranking removes the dependence on the scale of \(f\).

Tournament selection. Draw \(k\) individuals at random (with replacement) and keep the best. For the individual of rank \(i\) (worst = 1), the probability of being selected is

\[p_i = \frac{i^{k} - (i - 1)^{k}}{N^{k}}\]

Larger \(k\) means higher pressure; \(k = 2\) or \(3\) is common. Tournament selection is cheap, scale-invariant and easy to parallelise.

Boltzmann selection. With temperature \(T\):

\[p_i = \frac{e^{f_i / T}}{\sum_{j=1}^{N} e^{f_j / T}}\]

Lowering \(T\) over the run moves from exploration to exploitation.

Crossover#

Crossover combines two parents \(x\) and \(y\) into children, applied with probability \(p_c\) (typically 0.6 to 0.9).

One-point crossover at a random cut \(c \in \{1, \dots, n-1\}\):

\[\begin{split}\begin{aligned} c^{(1)} &= (x_1, \dots, x_c, \; y_{c+1}, \dots, y_n) \\ c^{(2)} &= (y_1, \dots, y_c, \; x_{c+1}, \dots, x_n) \end{aligned}\end{split}\]

Uniform crossover. With \(u_j \sim U(0, 1)\):

\[\begin{split}c_j = \begin{cases} x_j & u_j < 0.5 \\ y_j & \text{otherwise} \end{cases}\end{split}\]

Arithmetic crossover (real-valued). With \(\lambda \in [0, 1]\):

\[c^{(1)} = \lambda x + (1 - \lambda) y, \qquad c^{(2)} = (1 - \lambda) x + \lambda y\]

Blend crossover, BLX- \(\alpha\) (real-valued). For each gene let \(d_j = |x_j - y_j|\), then

\[c_j \sim U\big(\min(x_j, y_j) - \alpha d_j, \; \max(x_j, y_j) + \alpha d_j\big)\]

With \(\alpha = 0.5\) children can fall outside the parents’ interval, which helps exploration.

Permutation encodings need operators that keep a valid ordering, such as order crossover (OX) or partially mapped crossover (PMX).

Mutation#

Mutation makes small random changes so the search can reach new regions and the population does not lose diversity.

Bit-flip (binary). Each bit flips with probability \(p_m\), so the expected number of flips per chromosome is \(L \, p_m\). A common default is \(p_m = 1 / L\).

Gaussian (real-valued). Each gene is perturbed with probability \(p_m\):

\[x_j' = \operatorname{clip}\big(x_j + \sigma \, z_j, \; l_j, \; u_j\big), \qquad z_j \sim \mathcal{N}(0, 1)\]

The step size \(\sigma\) can be reduced over time, for example \(\sigma_t = \sigma_0 \, \gamma^{t}\) with \(0 < \gamma < 1\).

Swap (permutation). Exchange two randomly chosen positions.

Replacement and elitism#

In generational replacement the children replace the whole population. With elitism, the best \(e\) individuals are copied unchanged into \(P_{t+1}\), so the best fitness never decreases:

\[\max_i f\big(x_i^{(t+1)}\big) \ge \max_i f\big(x_i^{(t)}\big)\]

Steady-state GAs replace only a few individuals (often the worst) each generation.

Constraints#

Constraints \(g_k(x) \le 0\) are commonly handled with a penalty on the fitness:

\[f'(x) = f(x) - \sum_{k} \mu_k \max\big(0, g_k(x)\big)^2\]

where \(\mu_k > 0\) sets how strongly violations are punished. Alternatives are repair operators that map an infeasible individual back into the feasible region, or encodings that can only represent feasible solutions.

Why GAs work: the schema theorem#

For binary encodings, a schema \(H\) is a template such as 1**0*1 where * matches either bit. Let

\(m(H, t)\) be the number of individuals matching \(H\) at generation \(t\),
\(f(H)\) be their average fitness and \(\bar{f}\) the population average fitness,
\(o(H)\) be the order (number of fixed positions) and \(\delta(H)\) the defining length (distance between the first and last fixed positions).

With fitness proportionate selection, one-point crossover and bit-flip mutation, Holland’s schema theorem gives

\[\mathbb{E}\big[m(H, t+1)\big] \ge m(H, t) \, \frac{f(H)}{\bar{f}} \left[1 - p_c \frac{\delta(H)}{L - 1} - o(H) \, p_m\right]\]

Short, low-order, above-average schemas (building blocks) therefore receive exponentially increasing numbers of trials. The bound is a lower bound only: it ignores schemas created by crossover and mutation.

Parameter guide#

Parameter	Typical value	Effect
Population size \(N\)	50 to 500	Larger keeps more diversity but costs more evaluations per generation.
Crossover rate \(p_c\)	0.6 to 0.9	Higher mixes building blocks faster.
Mutation rate \(p_m\)	\(1/L\) or \(1/n\)	Too low stalls the search; too high turns it into random search.
Tournament size \(k\)	2 to 5	Higher increases selection pressure.
Elites \(e\)	1 to 5% of \(N\)	Protects the best solutions; too many reduces diversity.

Example: minimising the Rastrigin function#

The Rastrigin function is a standard test problem with many local minima and a global minimum of 0 at \(x = 0\):

\[f(x) = 10n + \sum_{i=1}^{n} \left(x_i^2 - 10 \cos(2 \pi x_i)\right), \qquad x_i \in [-5.12, 5.12]\]

The implementation below uses a real-valued encoding, tournament selection, BLX-\(\alpha\) crossover, Gaussian mutation and elitism. Because this is minimisation, the tournament keeps the individual with the lowest \(f\).

import numpy as np


def rastrigin(x):
    return 10 * x.shape[-1] + np.sum(x**2 - 10 * np.cos(2 * np.pi * x), axis=-1)


def tournament(pop, fit, k, rng):
    idx = rng.integers(len(pop), size=(len(pop), k))
    winners = idx[np.arange(len(pop)), np.argmin(fit[idx], axis=1)]
    return pop[winners]


def blx_alpha(p1, p2, alpha, rng):
    lo, hi = np.minimum(p1, p2), np.maximum(p1, p2)
    d = hi - lo
    return rng.uniform(lo - alpha * d, hi + alpha * d)


def ga(f, n_dim=5, bounds=(-5.12, 5.12), pop_size=100, generations=300,
       p_c=0.9, p_m=0.1, sigma=0.3, alpha=0.5, k=3, elite=2, seed=0):
    rng = np.random.default_rng(seed)
    lo, hi = bounds
    pop = rng.uniform(lo, hi, size=(pop_size, n_dim))

    for _ in range(generations):
        fit = f(pop)
        elites = pop[np.argsort(fit)[:elite]]

        parents = tournament(pop, fit, k, rng)
        rng.shuffle(parents)
        p1, p2 = parents[0::2], parents[1::2]

        do_cx = rng.random((len(p1), 1)) < p_c
        c1 = np.where(do_cx, blx_alpha(p1, p2, alpha, rng), p1)
        c2 = np.where(do_cx, blx_alpha(p1, p2, alpha, rng), p2)
        children = np.vstack([c1, c2])

        mutate = rng.random(children.shape) < p_m
        children = children + mutate * rng.normal(0, sigma, children.shape)
        children = np.clip(children, lo, hi)

        pop = np.vstack([elites, children[: pop_size - elite]])

    fit = f(pop)
    best = np.argmin(fit)
    return pop[best], fit[best]


x, fx = ga(rastrigin)
print(x.round(3), round(fx, 4))

Running it in 5 dimensions finds the global minimum, \(x \approx 0\) with \(f(x) \approx 0\).

Application: portfolio optimisation#

GAs suit portfolio problems with constraints that break standard quadratic solvers, such as cardinality limits or minimum lot sizes. To maximise the Sharpe ratio of weights \(w\) given expected returns \(\mu\), covariance \(\Sigma\) and risk-free rate \(r_f\):

\[\max_{w} \; \frac{w^{\top} \mu - r_f}{\sqrt{w^{\top} \Sigma w}} \quad \text{s.t.} \quad \sum_{i} w_i = 1, \; w_i \ge 0, \; \#\{i : w_i > 0\} \le K\]

A convenient encoding is an unconstrained vector \(z \in \mathbb{R}^n\) mapped to valid weights by keeping its \(K\) largest entries and normalising:

\[w_i = \frac{|z_i| \, \mathbb{1}[i \in \text{top}_K(|z|)]}{\sum_{j \in \text{top}_K(|z|)} |z_j|}\]

so every chromosome decodes to a feasible portfolio and no penalty term is needed.

Strengths and limitations#

Strengths

No gradients needed; works with noisy, discontinuous or black-box objectives.
Searches many regions at once, so it is less likely to get stuck in one local optimum.
Evaluations within a generation are independent and easy to parallelise.

Limitations

No guarantee of finding the global optimum, and convergence can be slow near the optimum.
Results depend on parameters such as \(N\), \(p_c\) and \(p_m\).
Needs many fitness evaluations, which is costly when each one is expensive (e.g. a full pricing run).

A common remedy for slow final convergence is a hybrid approach: use the GA to find a good region, then refine the best individual with a local optimiser such as Nelder-Mead or BFGS.

References#

1. 1. Holland, Adaptation in Natural and Artificial Systems, University of Michigan Press, 1975.
1. 1. Goldberg, Genetic Algorithms in Search, Optimization and Machine Learning, Addison-Wesley, 1989.
L. J. Eshelman and J. D. Schaffer, “Real-coded genetic algorithms and interval-schemata”, Foundations of Genetic Algorithms 2, 1993.

Math is Everywhere 32 vs 64 bit

Recent Posts

Categories

Archives