Crossing Over More Than Two Parents

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

👈 Implementing Other Common Crossover Strategie s | TOC | Implementing Chromosome Repairment 👉

Some algorithms require you to select more than two parents for crossover. All of the algorithms presented above can be implemented on multiple parents.

Here’s an example of single-point crossover on multiple parents:

​ ​def​ single_point_crossover([]), ​do​:
​   ​raise​ ​"​​You must have at least one parent!"​
​ ​def​ single_point_crossover([p1 | []]), ​do​: p1
​ 
​ ​def​ single_point_crossover(parents) ​do​
​     crossover_point = ​:rand​.uniform(hd(parents).size)
​     parents
​     |> Enum.chunk_every(2, 1, [hd(parents)])
​     |> Enum.map(&(List.to_tuple(&1)))
​     |> Enum.reduce(
​         [],
​         ​fn​ {p1, p2}, chd ->
​             {front, _} = Enum.split(p1.genes, crossover_point)
​             {_, back} = Enum.split(p2.genes, crossover_point)
​             c = %Chromosome{​genes:​ front ++ back, ​size:​ length(p1)}
​             [c | chd]
​         ​end​
​     )
​ ​end​

Start by examining the first two function definitions. Thanks to Elixir’s rich set of pattern matching features, you can define functions on specific inputs. The first definition is to ensure that the function doesn’t accept empty lists. The next definition simply returns the same chromosome if only one parent is provided.

The next function will work on a list of an arbitrary number of parents. The function starts by selecting a crossover point between 0 and the length of the first parent.

Now, examine this code block:

​ parents
​ |> Enum.chunk_every(2, 1, [hd(parents)])
​ |> Enum.map(&(List.to_tuple(&1)))

Enum.chunk_every/3 will pair every parent into groupings of two starting at index 1. The last argument, [hd(parents)], tells the function to group the leftover elements with the first element of parents. Then, each element is transformed into a tuple to make pattern matching easier.

Now, examine the final block:

​ |> Enum.reduce(
​     [],
​     ​fn​ {p1, p2}, chd ->
​         {front, _} = Enum.split(p1.genes, crossover_point)
​         {_, back} = Enum.split(p2.genes, crossover_point)
​         c = %Chromosome{​genes:​ front ++ back, ​size:​ length(p1)}
​         [c | chd]
​     ​end​

Enum.reduce/3 takes an enumerable, an accumulator, and a function as input. The enumerable is the list of tuples that represent pairs of parents. The accumulator is an empty list. The function simply implements single-point crossover on each pairing of parents and returns the child at the front of the accumulator.

This same algorithm can be implemented for each crossover strategy, replacing the body of the anonymous function in Enum.reduce/3 with whatever strategy you want.

Crossing over more than two parents can add a lot of unnecessary complexity to your algorithms. It’s best not to use this approach unless you absolutely have to.

👈 Implementing Other Common Crossover Strategie s | TOC | Implementing Chromosome Repairment 👉

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.