Skip to content
Tutorials Center
My learning

Topics

Lesson 14 of 36 ยท Crossover and Mutation

Crossover for Binary Strings

Learn one-point, two-point, k-point and uniform crossover for bit-string genetic algorithms, with Python code, positional bias, and when to prefer each operator.

Crossover is the operator that makes a genetic algorithm more than a clever random search. Two parents, each carrying some good genes, are combined into children that may carry the good genes of both. This is recombination: the same idea as shuffling two partly sorted decks together hoping to get a better one.

This lesson covers the classic crossover operators for bit strings (they also work on any fixed-length list). They are easy to code, and understanding how each one splits parents explains most of what you need for the real-valued and permutation operators later.

One-point crossover

Choose a random cut point between genes. Child 1 takes everything before the cut from parent 1 and everything after from parent 2; child 2 does the opposite.

TEXT
parent 1:  1 1 1 1 | 1 1 1 1
parent 2:  0 0 0 0 | 0 0 0 0
                 ^ cut after position 4
child 1:   1 1 1 1 | 0 0 0 0
child 2:   0 0 0 0 | 1 1 1 1
Python One-point and two-point crossover

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.

One-point crossover preserves long stretches of each parent, which is good when neighboring genes work together (a block of related bits). Its weakness is positional bias: genes at opposite ends of the chromosome are always separated by the cut, but genes next to each other are rarely separated. If your encoding puts two interacting genes at positions 1 and 40, one-point crossover almost never keeps them together.

Two-point and k-point crossover

Two-point crossover chooses two cut points and swaps the middle segment. It treats the chromosome as a ring, so the first and last genes are as likely to stay together as any neighbors, and it can swap a segment without being forced to take the end. k-point crossover generalizes this to k cuts. More cuts disrupt more building blocks but mix more thoroughly.

Uniform crossover

Uniform crossover decides gene by gene: for each position, flip a coin (usually 50 % but adjustable) to decide whether child 1 inherits from parent 1 or parent 2; child 2 gets the other.

Python Uniform crossover with a mask

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.

Uniform crossover has no positional bias: any set of genes can be inherited together, and the mixing is as thorough as it gets. The price is that it breaks up long building blocks (adjacent genes that work together) much more than one-point crossover. Where gene order is arbitrary, this does not matter and uniform crossover often works best.

Positional and distributional bias

Two kinds of bias distinguish the operators.

  • Positional bias: how the chance that two genes stay together depends on their distance. One-point has a strong bias, uniform has none.
  • Distributional bias: how many genes are exchanged. One-point produces very uneven splits (a tiny tail or half the chromosome), whereas uniform with p = 0.5 always exchanges about half.
Python How often do two genes stay together?

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.

For adjacent genes one-point almost always keeps them together (about 95 %), but genes at opposite ends are separated every single time (0.00). Two-point treats the chromosome as a ring, so the two end genes are always kept together (1.00) while middle genes are separated more often. Uniform crossover keeps any pair together half the time, no matter how far apart.

Which one to use?

Situation Suggested operator
Gene order has meaning (related genes adjacent) One-point or two-point
Gene order is arbitrary; many weak interactions Uniform
Unsure Two-point as a safe default; compare with uniform
Late in a run, population converged Any operator does little: parents are identical, so mutation matters

Also keep the crossover rate in mind: with probability 1 - p_c the two parents are copied unchanged. Rates of 0.6 to 0.95 are typical.

Three ways to cut

One-point Swap the tails
Two-point Swap a middle segment
Uniform Coin flip per gene

More mixing means more disruption of building blocks.

1 / 2

Why crossover can help

The building block hypothesis says GAs work by finding short, high-fitness patterns (building blocks) in different individuals and combining them. Crossover is the combining step. The hypothesis is debated for real problems, but the intuition is useful: crossover pays off when the problem can be broken into parts that can be solved independently and then assembled. If every gene interacts strongly with every other gene, crossover behaves like a big random mutation.

Test your own problem: run the GA with crossover rate 0 and see whether it does worse.

Python Does crossover help? A two-block problem

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.

Each block is solved independently by a different part of the population. Crossover can join two parents that each solved different blocks, while mutation alone must solve every block inside one lineage. With a budget of only 40 generations, the crossover runs reach the maximum while the mutation-only runs fall short.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. What does one-point crossover do?

    Child 1 gets parent 1's head and parent 2's tail, and child 2 the reverse.
  2. 2. What is positional bias?

    One-point crossover almost always keeps adjacent genes together and often separates distant ones. Uniform crossover has no such bias.
  3. 3. When is uniform crossover a better choice than one-point?

    Uniform crossover ignores gene positions, so it suits encodings where order carries no meaning.
  4. 4. A permutation is crossed with uniform crossover. What is the likely problem?

    Bit-string operators do not preserve the each-item-once rule of permutations. Specialized operators are covered in the permutation crossover lesson.

Summary

  • One-point, two-point and uniform crossover recombine parents at the gene level.
  • One-point keeps neighboring genes together but has strong positional bias; uniform has none but splits building blocks.
  • Two-point is a solid default; test uniform when gene order is arbitrary.
  • Use a crossover rate of about 0.6 to 0.95; otherwise copy the parents.
  • Crossover helps when a problem decomposes into parts that can be assembled.

Next: Crossover for Real Values