Skip to content
Tutorials Center
My learning

Topics

Lesson 4 of 36 ยท Getting Started

The GA Loop, Parameters and Fitness Landscapes

Learn how a genetic algorithm is structured, how to choose population size, mutation and crossover rates, when to stop, and why fitness landscapes trap searches.

You have seen a working GA. Now we take it apart and ask the questions every practitioner faces: how big should the population be, how often should we mutate, when do we stop, and why does the search sometimes get stuck on a mediocre answer? The answers rest on one mental image, the fitness landscape, so we start there.

Fitness landscapes

Imagine every possible solution laid out on a map, where neighbors are solutions that differ by a small change (one flipped bit, two swapped cities). Now raise each point to a height equal to its fitness. You get a terrain: peaks are good solutions, valleys are poor ones. Searching means looking for the highest peak.

  • A global optimum is the highest peak.
  • A local optimum is a peak that is higher than all its neighbors but lower than the global one.
  • A plateau is a flat area where small changes make no difference.
  • A rugged landscape has many peaks; a smooth one has few.

A simple climber that always steps uphill ends on the nearest peak, which may be a poor local one. A population explores many regions at once, and mutation and crossover let it jump across valleys. The next example makes this concrete with a function that has many local peaks.

Python Hill climbing gets trapped, a population does better

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

A single hill climb often stalls on a small ripple, so only some of the 30 runs reach the main peak. The GA keeps a spread of candidates and recombines them, so it reaches the main peak more often. This is the benefit of a population, but notice it is not magic: a badly tuned GA can also converge to a local peak.

The anatomy of a GA

All GAs share the same skeleton. What varies is the generation model (how old and new individuals are mixed) and the settings.

flowchart TD
    S["Start: initialize<br/>population"] --> E["Evaluate fitness"]
    E --> T{"Stop?<br/>(good enough or<br/>budget used)"}
    T -- yes --> R["Return the<br/>best individual"]
    T -- no --> P["Select parents"]
    P --> C["Crossover<br/>(with probability p_c)"]
    C --> M["Mutation<br/>(per gene, p_m)"]
    M --> U["Form next<br/>generation"]
    U --> E

The generic genetic algorithm. The only fitness evaluations are in the box labelled "Evaluate".

Generation models

  • Generational: build an entire new population of N children, then replace the old one (with a few elites kept). This is what you wrote in the previous lesson.
  • Steady-state: in each step create only one or two children and insert them by replacing the worst (or a random) individual. Good solutions spread more slowly, and the population changes gradually.
  • (mu + lambda) and (mu, lambda): terms from evolution strategies. mu parents make lambda children; "plus" keeps the best of parents and children together, "comma" keeps only children.

Choosing the parameters

There is no universal setting, but sound starting points exist.

Parameter Typical start Too small Too large
Population size 50 to 200 (more for hard problems) Not enough variety, early convergence Slow: wastes evaluations
Crossover rate p_c 0.6 to 0.95 Little recombination, relies on mutation Rarely a problem; good parents get disrupted
Mutation rate p_m (per gene) 1 / chromosome_length Loss of variety, stuck Becomes random search
Tournament size 2 to 5 Weak selection pressure Premature convergence
Elitism 1 to 5 % of the population Best solution can be lost Population loses diversity

The mutation rate 1 / L means that on average one gene changes per child, a rule that works surprisingly well for bit strings.

Python How mutation rate changes the outcome

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

With no mutation the search stalls below the maximum because gene values missing from the initial population can never be created. A rate near 1/L does best. At 0.5 every child is essentially random, so the result drops back towards random search. The "right" rate lies in a broad middle range, so do not agonize over exact values.

When to stop

A GA never "knows" it has found the optimum, so you pick a termination criterion:

  1. Target reached: fitness is at least a threshold you accept.
  2. Maximum generations or maximum evaluations: a fixed budget. Use evaluations when comparing methods fairly.
  3. Stagnation: the best fitness has not improved for k generations.
  4. Convergence: the population has lost almost all diversity.
  5. Time limit: wall-clock seconds.

Most real systems combine a budget with a stagnation check.

Exploration versus exploitation

Every parameter trades two forces:

  • Exploration: search new regions (high mutation, big populations, weak selection).
  • Exploitation: refine good regions (strong selection, elitism, small steps).

Too much exploration is random search. Too much exploitation is premature convergence: the population collapses onto one mediocre peak. The skill of tuning a GA is balancing the two, often by shifting from exploration early to exploitation late.

Two forces to balance

Exploration Mutation, big population
Exploitation Selection pressure, elites

Too much of either one breaks the search.

1 / 2

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. What is a local optimum?

    A local optimum is a peak in the fitness landscape that is higher than nearby points but lower than the global optimum.
  2. 2. A common starting mutation rate for a bit-string chromosome of length L is

    A rate of 1/L changes about one gene per child, which explores gently without destroying good structure.
  3. 3. What distinguishes a steady-state GA from a generational GA?

    In a steady-state GA the population changes a little at a time, while a generational GA replaces (almost) everyone each generation.
  4. 4. Which symptom most suggests premature convergence?

    When all individuals are alike and fitness has stopped improving, diversity is gone and the population is stuck on a single peak.
  5. 5. Why compare methods by number of fitness evaluations rather than generations?

    Fitness evaluations are usually the expensive part, and equal generations can hide very different amounts of work.

Summary

  • A fitness landscape shows solutions as terrain; GAs look for the highest peak and must avoid local optima.
  • The GA skeleton is the same everywhere; generational and steady-state schemes differ in replacement.
  • Good starting parameters: population 50 to 200, crossover 0.6 to 0.95, mutation 1/L, small tournaments, a little elitism.
  • Stop on a target, a budget, stagnation or lost diversity.
  • Balance exploration and exploitation; too much exploitation causes premature convergence.

Next: Binary and Gray Encoding