Skip to content
Back to search results

Genetic Algorithm — Evolutionary Optimization

Introduced by
John Henry Holland
Year
1975
Type
Population-based metaheuristic
Font size

What does it do?

A genetic algorithm (GA) is a population-based metaheuristic optimization method introduced by John Henry Holland (1975) that mimics the principles of natural selection.

It maintains a population of candidate solutions and iteratively improves them through selection, crossover, and mutation operators, making it especially powerful on discontinuous, non-convex, and multi-modal search spaces where classical gradient-based methods fail.

The intuition behind the method

Imagine you have thousands of possible answers to a hard problem and no formula for finding the best one. A genetic algorithm treats each candidate answer as an individual in a population. In every generation it keeps the fittest individuals, breeds them together to mix their good traits, and occasionally mutates offspring to inject novelty. Over many generations the population drifts toward better and better solutions — not by following a gradient, but by mimicking the way evolution shapes organisms over time.

History

The genetic algorithm was introduced by John Henry Holland in his 1975 book Adaptation in Natural and Artificial Systems, which formalised the notion of a schema (building block) and provided the foundational theoretical analysis of why crossover and selection drive search toward fitter regions. Holland's students — notably David Goldberg — popularised GAs through engineering applications in the 1980s. Kalyanmoy Deb later extended the framework to multi-objective settings, culminating in the widely adopted NSGA-II algorithm (2002). Today GAs remain a standard tool in evolutionary computation, with active research in hybrid methods that combine evolutionary search with local refinement.

When to use it

Genetic algorithms are appropriate when the search space is large, discontinuous, non-differentiable, or highly multimodal — conditions where gradient-based solvers cannot operate or get trapped in local optima. They apply to continuous, categorical, binary, and ordinal variable types and impose no normality or distributional assumptions. The only requirement is a computable fitness function. For problems where an analytic or convex formulation exists, classical methods (linear programming, gradient descent) are faster and should be preferred. Sufficient iterations (typically well above 1,000 generations) are required for meaningful convergence; running too few generations is the most common failure mode.

Limitations and considerations

  • No guarantee of convergence to the global optimum; results may vary across runs.
  • Computationally expensive: each generation requires evaluating the entire population, which is prohibitive when the fitness function is slow.
  • Performance is sensitive to hyperparameter choices — population size, crossover probability, and mutation rate — which often require problem-specific tuning.
  • For smooth, convex, or well-structured problems, classical gradient-based or linear methods will be faster and more reliable.

Source conditions do not replace independent scientific review or validation by an analysis engine.

Strengths

  • Works on discontinuous, non-differentiable, and multi-modal objective landscapes where gradient-based methods break down.
  • Imposes no distributional assumptions — the only input required is a computable fitness function.
  • Naturally handles a wide range of variable types: continuous, binary, categorical, and ordinal.
  • Population diversity allows simultaneous exploration of multiple regions of the search space, reducing the risk of premature local-optimum trapping.
  • Highly extensible: domain-specific crossover and mutation operators, constraint-handling, and multi-objective variants (e.g., NSGA-II) are well established in the literature.

Applications

  • Engineering design optimisation: finding optimal parameter configurations for structures, circuits, or mechanical systems.
  • Scheduling and routing problems: job-shop scheduling, vehicle routing, and timetabling where the combinatorial search space is too large for exhaustive search.
  • Machine learning: hyperparameter tuning, neural architecture search, and feature selection.
  • Operations research: supply chain optimisation, portfolio allocation, and resource assignment under complex constraints.
  • Bioinformatics: sequence alignment, protein structure prediction, and gene regulatory network inference.

How it works

How it works

1

A population of candidate solutions (individuals) is created, typically at random within the search space. Each individual encodes a potential solution — for example as a binary string, a real-valued vector, or a permutation — and the population size is a key parameter that determines how broadly the search space is sampled from the outset.

2

Every individual in the population is scored by a fitness function that quantifies how good that solution is relative to the problem objective. The fitness function is the only domain-specific component the user must supply; it can be any computable measure — a simulation output, a cost formula, or a model error metric.

3

Individuals with higher fitness are chosen preferentially to become parents for the next generation. Common selection mechanisms include tournament selection, roulette-wheel (fitness-proportionate) selection, and rank-based selection. Selection pressure controls the trade-off between exploiting high-quality solutions and maintaining population diversity.

4

Selected parents produce offspring through crossover (recombination), where segments of two parent encodings are combined to form a new individual, and through mutation, where small random changes are applied to individual genes. The crossover probability and mutation rate are critical tuning parameters: too little mutation causes premature convergence, too much turns the search into random walk.

5

The loop of evaluate → select → reproduce continues for a set number of generations or until a convergence criterion is met (e.g., no improvement over a window of generations). The best individual found across all generations is returned as the solution. Because convergence to the global optimum is not guaranteed, multiple independent runs are recommended for high-stakes problems.

Common pitfalls

  • Running too few generations is the most common error: with insufficient generations the algorithm does not converge, so analytic or gradient-based methods should be preferred when only a small iteration budget is available.
  • Premature convergence — the population losing diversity too early — produces a locally optimal but globally suboptimal result; maintain adequate population size and mutation rate to counteract this.
  • Using an ill-defined or misspecified fitness function produces misleading results regardless of algorithmic correctness; validate the fitness function independently before running the GA.
  • Applying a GA to a smooth, convex problem where gradient descent or linear programming would suffice wastes computational resources and introduces unnecessary stochasticity.
  • Reporting a single run as the solution without checking reproducibility; for high-stakes applications run the algorithm multiple times and report the distribution of outcomes.

Frequently asked questions

How is a genetic algorithm different from gradient descent?

Gradient descent requires a differentiable objective and follows the local gradient downhill. A genetic algorithm requires only that the fitness can be computed for any candidate solution; it searches by evolving a population rather than following a gradient, so it can handle discontinuous, non-differentiable, and multi-modal landscapes where gradient descent fails or gets stuck.

How many generations and how large a population do I need?

There are no universal rules; both depend on the complexity of the search space. A population that is too small or a run that is too short risks premature convergence. As a practical starting point, population sizes of 50–200 and generation counts of 100–1,000 are common in the literature, but challenging problems routinely require more. Always inspect convergence curves rather than fixing arbitrary stopping criteria.

Is a genetic algorithm guaranteed to find the global optimum?

No. GAs are heuristics and provide no convergence guarantee to the global optimum in finite time. For deterministic guarantees you need exact methods such as integer programming solvers. For high-stakes decisions, run the GA multiple times, report the distribution of results, and compare the best solution to any known bounds.

When should I choose a GA over simulated annealing or particle swarm optimisation?

GAs tend to be preferred when the solution is naturally encoded as a combinatorial structure (permutations, binary strings) or when multi-objective extensions are needed. Particle swarm optimisation is often faster on continuous unimodal problems. Simulated annealing is simpler to implement for combinatorial problems with a well-defined neighbourhood. In practice, benchmarking two or three methods on a small problem instance before committing to one is advisable.

Related methods

Sources

  1. Holland, J.H. (1975). Adaptation in Natural and Artificial Systems. University of Michigan Press.

    Open publication reference
    Copied.
  2. Deb, K. (2001). Multi-Objective Optimization using Evolutionary Algorithms. Wiley.

    ISBN: 9780471873396
    Copied.