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:
- Select a random slice of genes from Parent 1.
- Remove the values from the…