Solving N-Queens with Order-One Crossover
Explore how to implement order-one crossover, a permutation-preserving crossover strategy, to solve the N-Queens problem using genetic algorithms in Elixir. Understand the code structure and customization techniques, enabling you to run and optimize this crossover within your genetic algorithm framework.
We'll cover the following...
Implementing a crossover strategy
To solve N-queens, we need to implement a crossover strategy that preserves the integrity of our permutation. While there are numerous approaches to doing this, one common strategy is known as order-one crossover.
Before you start, we will first create a new file crossover.ex within the toolbox folder. Next, we will create a new module that looks like this:
Just like selection.ex in toolbox contains useful selection strategies, we’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 algorithms.
Order-one crossover works like this:
-
Select a random slice of genes ...