Skip to content
Tutorials Center
My learning

Topics

Lesson 3 of 36 ยท Getting Started

Your First Genetic Algorithm in Python

Build a complete genetic algorithm from scratch in Python: initialization, fitness, selection, crossover, mutation and elitism, tested on OneMax and a target string.

Time to write a real genetic algorithm. We will build it in small pieces so that every part is clear, then put the pieces together and watch a population improve generation by generation. The code uses only the Python standard library, and every example here runs in your browser.

Our first problem is OneMax: find a bit string of length 40 with as many 1s as possible. It is silly (the answer is obvious) and that is the point. Because you know the right answer, you can tell at a glance whether your GA works. Once it does, you can swap in a harder fitness function without changing the machinery.

The pieces

A minimal GA needs six steps.

  1. Initialize a population of random chromosomes.
  2. Evaluate each one with the fitness function.
  3. Select parents, favoring the fitter.
  4. Crossover two parents to make children.
  5. Mutate the children slightly.
  6. Replace the old population with the new one.

Here are the first four building blocks as separate, testable functions.

Python Building blocks: initialize, select, crossover, mutate

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.

tournament is a simple selection method: draw three at random and keep the best. Chapter 3 studies it closely. one_point_crossover cuts both parents at the same random point and swaps the tails. mutate flips each bit with a small probability.

The complete loop

Now we assemble the generation loop. Two details matter:

  • Elitism: copy the best individual unchanged into the next generation, so progress is never lost to bad luck.
  • Statistics: record the best and average fitness each generation. Watching these two numbers is how you debug a GA.
Python A complete genetic algorithm for OneMax

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.

You should see the average fitness start near 20 (half the bits are 1 by chance) and climb steadily, while the best fitness approaches 40 within a few dozen generations. The exact generation count depends on the random seed, so try other seeds.

Notice how the average trails the best. The gap is the diversity of the population. When average and best meet, everyone is nearly identical and the search has stalled (see population initialization and diversity).

Evolving a target string

OneMax is too easy to be convincing, so here is a variant with a richer alphabet: evolve a population of random text until it spells a target phrase. The chromosome is a string of characters, the allele set is letters and spaces, and fitness is the number of characters in the right position.

Python Evolving a phrase

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.

Random text starts at about one correct letter in 27. Within some tens of generations the phrase usually emerges. Each correct letter, once found, tends to be kept by selection, and crossover combines correct letters from different parents. This "building blocks come together" effect is the intuition behind why GAs work, and a good reason to use crossover instead of mutation alone.

This is a demonstration, not a good way to produce a known string: here the fitness function already contains the answer. Real GAs use a fitness function that measures quality without knowing the solution.

Why it works, in one picture

flowchart TD
    P["Generation t: mixed population<br/>some fit, many average"] --> S["Selection: fit individuals<br/>get more offspring"]
    S --> X["Crossover: combine good<br/>pieces from two parents"]
    X --> M["Mutation: introduce<br/>new genes"]
    M --> N["Generation t+1: higher<br/>average fitness"]

Selection concentrates the search on promising regions, crossover recombines their parts, and mutation explores around them.

Things to try

  • Set MUTATION_RATE to 0 in the phrase example and see how often the run gets stuck.
  • Set it to 0.3 and see why too much mutation destroys progress.
  • Replace tournament size 4 with 1 (random parents) and watch the run slow dramatically.
  • Remove the elite ([best] + ...) and observe the best fitness dipping.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. What does elitism do?

    Elitism guarantees the best solution found so far is never lost through unlucky selection, crossover or mutation.
  2. 2. In one-point crossover, what happens at the cut point?

    Each child takes the head of one parent and the tail of the other, so both parents' building blocks are recombined.
  3. 3. A run's average fitness is almost equal to its best fitness. What does it suggest?

    When nearly everyone is identical, crossover cannot create anything new, so the search stalls unless mutation adds fresh genes.
  4. 4. Why does the target-phrase example not teach how real problems work?

    Comparing to the target gives away the solution. Real fitness functions measure quality (cost, score, error) without knowing the best answer.

Summary

  • A GA is initialization plus a loop of evaluate, select, crossover, mutate, replace.
  • Elitism protects the best solution; a mutation rate near 1 / length is a common starting point.
  • Tracking best and average fitness per generation shows whether the search is progressing or has converged.
  • Selection concentrates the search, crossover recombines parts, mutation adds new genes.
  • The same loop handles bits, characters or any other encoding by swapping the operators.

Next: The GA Loop and Its Parameters