Solving N-Queens with Order-One Crossover

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

👈 Introducing N-Queens | TOC | Exploring Crossover 👉

To solve N-queens, you need to implement a crossover strategy that preserves the integrity of your permutation. While there are numerous approaches to doing this, one common strategy is known as order-one crossover.

Before you start, create a new file crossover.ex within the toolbox folder. Next, create a new module that looks like this:

​ ​defmodule​ Toolbox.Crossover ​do​
​   alias Types.Chromosome
​   ​# ...​
​ ​end​

Just like selection.ex in toolbox contains useful selection strategies, you’ll implement useful crossover strategies in Toolbox.Crossover.

Implementing Order-One Crossover

Order-one crossover, sometimes called “Davis order” crossover, is a crossover strategy on ordered lists or permutations. Order-one crossover is part of a unique set of crossover strategies that will preserve the integrity of a permutation solution.

Order-one crossover will maintain the integrity of the permutation without the need for chromosome repair. This is useful and eliminates some complexity in your algorithms.

Order-one crossover works like this:

1. Select a random slice of genes from Parent 1.
2. Remove the values from the slice of Parent 1 from Parent 2.
3. Insert the slice from Parent 1 into the same position in Parent 2.
4. Repeat with a random slice from Parent 2.

Order-one crossover will produce two new, valid children. The following image demonstrates the algorithm used to produce one child:

Because of its complexity, order-one crossover is difficult to implement in Elixir. It requires the use of MapSet and is generally harder to understand than other crossover strategies. Add the following function to your Toolbox.Crossover module:

​ ​def​ order_one_crossover(p1, p2) ​do​
​   lim = Enum.count(p1.genes) - 1
​   ​# Get random range​
​   {i1, i2} =
​     [​:rand​.uniform(lim), ​:rand​.uniform(lim)]
​     |> Enum.sort()
​     |> List.to_tuple()
​ 
​   ​# p2 contribution​
​   slice1 = Enum.slice(p1.genes, i1..i2)
​   slice1_set = MapSet.new(slice1)
​   p2_contrib = Enum.reject(p2.genes, &MapSet.member?(slice1_set, &1))
​   {head1, tail1} = Enum.split(p2_contrib, i1)
​ 
​   ​# p1 contribution​
​   slice2 = Enum.slice(p2.genes, i1..i2)
​   slice2_set = MapSet.new(slice2)
​   p1_contrib = Enum.reject(p1.genes, &MapSet.member?(slice2_set, &1))
​   {head2, tail2} = Enum.split(p1_contrib, i1)
​ 
​   ​# Make and return​
​   {c1, c2} = {head1 ++ slice1 ++ tail1, head2 ++ slice2 ++ tail2}
​ 
​   {%Chromosome{
​      ​genes:​ c1,
​      ​size:​ p1.size
​    },
​    %Chromosome{
​      ​genes:​ c2,
​      ​size:​ p2.size
​    }}
​ ​end​

Start by examining the first code block under the first comment. The code creates a tuple that is a random range in ascending order within the length of your chromosome.

The next block creates a slice from p1 using the range you just created. It then determines which elements from p1 are present in p2 and eliminates them from p2’s contribution to the child. Finally, it splits this contribution at the first index in the range, so the elements of p2’s contribution are added in the correct place in the new chromosome.

The process is repeated with p2, and the chromosomes are combined to return two new child chromosomes.

Order-one crossover is one strategy for solving problems with permutation genotypes. One drawback of order-one crossover is that it’s slow. With large solutions, order-one crossover will significantly slow down your algorithm. Fortunately, most problems that use permutation genotypes are small.

Adding Crossover Customization

Before you can finish solving N-queens, you need to tweak the crossover function in genetic.ex to support custom crossover functions. Recall from the previous chapter how you used opts to extract and apply a custom crossover function. You’ll do the same thing here.

First, open genetic.ex and navigate to the crossover function. Right now, it should look like this:

​ ​def​ crossover(population, opts \\ []) ​do​
​   population
​   |> Enum.reduce([],
​       ​fn​ {p1, p2}, acc ->
​         cx_point = ​:rand​.uniform(length(p1))
​         {{h1, t1}, {h2, t2}} =
​           {Enum.split(p1, cx_point),
​             Enum.split(p2, cx_point)}
​         {c1, c2} = {h1 ++ t2, h2 ++ t1}
​         [c1, c2 | acc]
​       ​end​
​     )
​ ​end​

Remember, this function takes a list of tuples representing pairs of parents. If you notice, the actual process of crossover takes place within the body of the anonymous function passed to Enum.reduce/3. That means you can replace this code with whatever crossover function you want.

First, extract a :crossover_type parameter from opts:

​ ​def​ crossover(population opts \\ []) ​do​
​   crossover_fn = Keyword.get(opts,
​                              ​:crossover_type​,
​                              &Toolbox.Crossover.order_one/2)
​ ​end​

For now, the default can remain Toolbox.Crossover.order_one/2 because that’s the only one you’ve implemented thus far. Next, in the body of the anonymous function in reduce, replace the code with the following:

​ ​# ...​
​ |> Enum.reduce([],
​     ​fn​ {p1, p2}, acc ->
​       {c1, c2} = apply(crossover_fn, [p1, p2])
​       [c1, c2 | acc]
​     ​end​
​   )

Remember from the last chapter that apply/2 simply applies the given function with the given arguments.

Now, you should be set to run N-queens. Add the following to nqueens.exs below your module:

​ soln = Genetic.run(NQueens)
​ 
​ IO.write(​"​​\n"​)
​ IO.inspect(soln)

A quick note: you don’t need to specify any specific crossover type because order_one/2 is the current default. You can adjust the population size, selection type, or crossover rate if you’d like.

Next, open your terminal and run the script:

​ ​$ ​​mix​​ ​​run​​ ​​scripts/nqueens.exs​
​ Current best: 8
​ %Types.Chromosome{
​   age: 1,
​   fitness: 8,
​   genes: [4, 6, 1, 5, 2, 0, 3, 7],
​   size: 8
​ }

👈 Introducing N-Queens | TOC | Exploring Crossover 👉

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.