Implementing Other Common Crossover Strategies

Genetic Algorithms in Elixir — by Sean Moriarity (52 / 101)

👈 Exploring Crossover | TOC | Crossing Over More Than Two Parents 👉

The goal of crossover is to produce child solutions that are better than their parents. A good crossover strategy will produce, on average, better child solutions in the long run. Additionally, a good crossover strategy will respect the genotype of your chromosome. For example, if you’re using a permutation genotype, a good crossover strategy will maintain the integrity of the permutation. You don’t want to use a crossover strategy that will produce invalid solutions because, eventually, all of your solutions will become invalid and your algorithm will never produce the best solution.

In this section, you’ll learn about several common crossover strategies that work on all of the genotypes you’ve learned about so far. With these crossover strategies in place, you’ll be able to effectively solve problems that use binary, permutation, and real-value genotypes. The crossover strategies you’ll implement are:

• Single-point crossover
• Uniform crossover
• Whole arithmetic recombination

Additionally, you’ll be introduced to a variety of more advanced crossover strategies that you can research and implement on your own.

Single-Point Crossover

Single-point crossover is the most basic crossover strategy and the one you’ve been using since Chapter 1, ​Writing Your First Genetic Algorithm​. John Holland proposed it as the crossover strategy in the original genetic algorithm. Single-point crossover is common in solving basic problems because it’s the easiest to implement.

The basic algorithm for single-point crossover is:

1. Choose a random number k between 0 and n-1 where n is the length of the parent chromosomes.
2. Split both parents at k to produce four slices of genes.
3. Swap the tails of each parent at k to produce two new children.

The following picture illustrates single-point crossover:

This is how you would implement single-point crossover in Elixir:

​ ​def​ single_point(p1, p2) ​do​
​   cx_point = ​:rand​.uniform(p1.size)
​   {p1_head, p1_tail} = Enum.split(p1.genes, cx_point)
​   {p2_head, p2_tail} = Enum.split(p2.genes, cx_point)
​   {c1, c2} = {p1_head ++ p2_tail, p2_head ++ p1_tail}
​   {%Chromosome{​genes:​ c1, ​size:​ length(c1)},
​     %Chromosome{​genes:​ c2, ​size:​ length(c2)}}
​ ​end​

First, you select a random number. Remember, :rand.uniform/1 returns a uniform random number between 0 and n-1. Next, you split both chromosomes at cx_point. Enum.split/2 returns a tuple of slices. Finally, you swap the tails of each parent to produce new children. You then wrap these children in a Chromosome struct and return them as a tuple.

The advantages of single-point crossover lie in its simplicity. It’s a simple algorithm that runs very fast on solutions of all sizes. Unfortunately, single-point crossover does a poor job producing stronger solutions. This fact is especially evident when you’re dealing with large solutions. Additionally, single-point crossover won’t maintain the integrity of a permutation, and it might not “blend” real-value solutions like you’d need. Single-point crossover works most effectively on binary genotypes where order matters.

Single-point crossover is only useful for basic problems; however, you can use it to prototype problems and as a benchmark against other crossover strategies.

Uniform Crossover

Uniform crossover is a slightly more advanced crossover strategy in which genes in the parent chromosome are treated separately. While single-point crossover only works on blocks of genes, uniform crossover works on individual genes.

Uniform crossover works by pairing corresponding genes in a chromosome and swapping them according to a rate. The rate is a number between 0 and 1 that represents the probability that two genes will be swapped. A rate of 0.5 indicates that genes have a 50% chance of swapping between parent chromosomes.

The image demonstrates uniform crossover.

This is how you would implement uniform crossover in Elixir:

​ ​def​ uniform(p1, p2, rate) ​do​
​   {c1, c2} =
​     p1.genes
​     |> Enum.zip(p2.genes)
​     |> Enum.map(​fn​ {x, y} ->
​       ​if​ ​:rand​.uniform() < rate ​do​
​         {x, y}
​       ​else​
​         {y, x}
​       ​end​
​     ​end​)
​     |> Enum.unzip()
​ 
​   {%Chromosome{​genes:​ c1, ​size:​ length(c1)},
​     %Chromosome{​genes:​ c2, ​size:​ length(c2)}}
​ ​end​

First, you use Enum.zip/2 to pair corresponding genes from both parents. Enum.zip/2 returns a single enumerable from two enumerables with corresponding elements “zipped” in a tuple. Next, you iterate over each tuple with Enum.map/2 and swap genes according to the rate provided. Finally, you use Enum.unzip/1 to unpack the tuples back into two lists of new chromosomes.

Uniform crossover is more versatile in its ability to isolate and swap single genes that could significantly improve the fitness of child chromosomes. For example, imagine you have two parent solutions that look like the image.

If you were to try and use single-point crossover on those parent chromosomes, it would be difficult to produce solutions that effectively maximize the potential of each parent. Notice what happens when using single-point crossover at the following crossover point:

If you used uniform crossover, you could effectively isolate individual genes and potentially swap the correct genes to produce the best solution, like the image.

One thing to consider with uniform crossover is the impact the rate will have on its effectiveness. A higher uniform crossover rate means more genes will be swapped. A lower uniform crossover rate means fewer genes will be swapped. Think of it like this: a uniform crossover rate of 0.8 means that each child will be made up of 80% of one parent and 20% of the other. Typically, it’s best to choose a rate of 0.5.

Uniform crossover doesn’t work on permutations, nor will it produce desired results for most real-valued genotypes. Additionally, because uniform crossover needs to iterate over the entirety of both parent chromosomes, it can be slow with extremely large chromosomes. Uniform crossover works best with binary genotypes. It’s effective and relatively fast with small chromosomes.

Whole Arithmetic Recombination

Whole arithmetic recombination is a crossover strategy for real-value chromosomes that mathematically mixes each gene of the parents to produce children. Whole arithmetic recombination takes a percentage of each parent gene and adds them to produce new solutions. The percentage of each parent gene present in the child gene is determined by a parameter alpha.

Whole arithmetic recombination combines genes according to the formula:

Where x and y are parent genes, and z is a resulting child gene.

That formula is applied on each corresponding gene in the parent chromosomes. One thing to note is that an alpha of 0.5 will produce identical child chromosomes.

The image demonstrates whole arithmetic recombination.

This is how you would implement whole arithmetic recombination in Elixir:

​ ​def​ whole_arithmetic_crossover(p1, p2, alpha) ​do​
​   {c1, c2} =
​     p1.genes
​     |> Enum.zip(p2.genes)
​     |> Enum.map(
​ 
​ 
​         ​fn​ {x, y} ->
​           {
​             x*alpha + y*(1-alpha),
​             x*(1-alpha) + y*alpha
​           }
​         ​end​
​       )
​     |> Enum.unzip()
​   {%Chromosome{​genes:​ c1, ​size:​ length(c1)},
​     %Chromosome{​genes:​ c2, ​size:​ length(c2)}}
​ ​end​

Because whole arithmetic recombination also works on corresponding genes in the parents, you use Enum.zip/2 to pair genes like in uniform crossover. Next, you use Enum.map/2 to iterate over each pair and combine them according to the formula mentioned earlier. Finally, you use Enum.unzip/2 to return two new sets of genes.

Whole arithmetic recombination is a basic strategy for combining real-value chromosomes. One issue it has is its tendency to converge quickly on poor solutions. Because there’s no randomness involved, all chromosomes will inevitably become the same without other strategies to prevent premature convergence. You can defeat this by only combining a percentage of genes in the chromosome.

Whole arithmetic recombination, like uniform crossover, iterates over entire chromosomes. This means it will be slower on larger solutions. It can be useful with floating-point solutions — like in portfolio optimization and determining what percentage of your portfolio to allocate to each asset.

Other Crossover Strategies

Numerous algorithms for implementing crossover on various genotypes are available, such as:

• Messy single-point: messy crossover strategy doesn’t preserve the length of chromosomes.
• Cycle: crossover on ordered list using cycles.
• Multi-point: crossover at multiple points.

You can find these algorithms online and attempt to implement them yourself.

👈 Exploring Crossover | TOC | Crossing Over More Than Two Parents 👉

Genetic Algorithms in Elixir by Sean Moriarity can be purchased in other book formats directly from the Pragmatic Programmers. If you notice a code error or formatting mistake, please let us know here so that we can fix it.