Primer

Genetic Algorithms

A genetic algorithm (GA) is a search method that copies the logic of natural selection: keep a population of candidate solutions, let the better ones reproduce, mix and mutate them, and repeat. Over many generations the population drifts toward high-quality answers — without anyone having to know the "right" answer in advance.

The big idea

Most optimization methods need something specific from your problem — a smooth formula, a gradient to follow, a tidy mathematical structure. Many real problems have none of that. They have a huge number of possible answers and a messy, bumpy landscape of "better" and "worse."

Genetic algorithms ask for almost nothing. You only need two things: a way to represent a candidate solution, and a way to score how good a candidate is (the fitness function). Given those, the GA searches by evolving a whole population of candidates at once — exploring many regions in parallel and steadily concentrating on the promising ones.

Selection supplies the pressure toward "better." Crossover and mutation supply the variation that keeps new ideas coming. Balance the two and the population learns.

The vocabulary

Genome / chromosome

The encoded form of one candidate solution. Classically a fixed-length string — bits, integers, or real numbers. For a delivery-route problem it might be an ordering of cities; for a robot it might be a vector of navigation parameters.

Gene & allele

A gene is one position in the genome; an allele is the value it holds. Flipping or nudging alleles is how the algorithm explores nearby solutions.

Population

The set of candidate solutions alive in the current generation. A bigger, more diverse population explores more of the search space but costs more to evaluate.

Fitness function

The score that says how good a candidate is at the job. This is the one piece you must design carefully — the GA will optimize exactly what you measure, for better or worse.

The loop, step by step

Initialize. Create a random starting population of genomes.
Evaluate. Run the fitness function on every candidate.
Select. Choose parents, biased toward higher fitness — for example with tournament selection (pick a few at random, keep the best) or roulette-wheel selection (probability proportional to fitness).
Crossover. Combine two parents into offspring — for instance, take the first part of one genome and the rest of the other (single-point crossover), or mix gene by gene (uniform crossover).
Mutate. With small probability, randomly change some genes. This keeps diversity alive and lets the search escape dead ends.
Replace. Form the next generation, usually keeping a few of the very best unchanged (elitism), then loop back to evaluation until you hit a target fitness or a generation budget.

A minimal sketch

Stripped to its essence, the whole method fits on a napkin:

population = random_genomes(N)
for generation in range(max_gens):
    scores = [fitness(g) for g in population]
    if best(scores) is good_enough:
        break
    parents = select(population, scores)   # favor higher fitness
    children = []
    while len(children) < N:
        a, b = pick_two(parents)
        child = crossover(a, b)            # recombine
        child = mutate(child, rate)        # vary
        children.append(child)
    population = elitism(population, scores) + children
return best_solution(population)

What can go wrong (and how it's handled)

The classic failure mode is premature convergence: the population collapses onto one mediocre solution too early and stops exploring. Practitioners counter it by keeping selection pressure moderate, preserving diversity (tournament selection from a wide pool, injecting random "immigrants," boosting mutation when diversity drops), and retaining elites only for stability. The SEED-Nav robot project on this site uses exactly these tactics — see the project page.

The other practical issue is expensive fitness: when scoring a candidate means running a simulation or a physical robot episode, evaluations dominate the cost, so small populations and noisy scores are the norm and diversity maintenance matters even more.

Where genetic algorithms shine

Combinatorial optimization — scheduling, routing, packing, layout, timetabling.
Parameter and design search — tuning systems with many interacting knobs and no clean gradient.
Engineering design — antenna shapes, structures, circuits, and other "evolved" artifacts.
Machine learning support — feature selection, hyperparameter search, and evolving neural networks (neuroevolution).
Robotics & control — evolving controllers and navigation policies, as in the featured robot project.

Genetic algorithms vs. genetic programming

A GA typically evolves a fixed-shape genome — a vector of values. Genetic programming (GP) evolves programs of variable shape, usually trees of code, so the structure of the solution itself can grow and change. GP is best thought of as a close cousin of the GA. If you've got the GA loop in your head, the genetic programming primer will feel familiar.

Go deeper

For the foundational books (Holland; Goldberg; Mitchell), survey papers, and software you can install today, head to the Library. If you'd rather see evolution running on real hardware, the SEED-Nav robot evolves its own navigation behavior episode by episode.

← Home Genetic Programming →