·

Follow

Published in

·

5 min read

·

Mar 20, 2022

--

Genetic algorithms (GA) try to approach problem solving the way nature and evolution does. The fittest individuals are selected for reproduction in order to produce the offspring of the next generation. In this article we will attempt to solve an 8 queens puzzle using one for educational purposes. An 8 queens is a classic puzzle problem of placing eight chess queens on an 8x8 chessboard so that no two queens threaten each other. Thus no two queens should share the same row, column, or diagonal.

The approach we will use when tackling the 8 queens problem Firstly, we ‘ll seek for a list combination that gives zero cost on the cost function, which means that no queen is attacking the other queen.

We assume that each queen belongs in a separate row, otherwise they would already attack each other. For example the chess board on the right would be decoded as [3,1,6,2,5,7,4,0] . Our goal is to find one such permutation.

Analytically the process entails the following steps:

**Initialization**: A population of suitable size of suitable length is created.The population size should not be kept very large as it can cause a GA to slow down, while a smaller population might not be enough for a good mating pool. Therefore, an optimal population size needs to be decided by trial and error.

**Selection**: it involves the selection of a subset of the best results from the current population, that is the 8-queens outcomes which have the minimum cost function. In our case we’ll keep 20% of the population.

**Crossover**: Picking this subset we’ll randomly pick 2 of those words each time and crossover them. Picking a random length from 0,8 that is the length of the Queens states we ll take the first bit of the first word and concatenate it with the second word of the second bit

A visual below shows what happens:

- Mutation: The mutation is manifested with a small random change in the combination of the individuals. This mutation happens once in a small probability. In our case it’s 30% of the time.

The below does nothing more but the above described in one routine:

Lastly an EightQueensState class representation is needed for everything to work:

A double for loop for every chess position like below would visualize our solution:

So now our algorithm is working. But let’s turn it up a notch, taking a few extra steps and extend our application:

- First let’s make queens accept any number of queens.

- Since we have a permutation, it makes sense to take advantage of that and not treat it like an integer representation. Changing to a permutation instead of an integer should bring a bettwer outcome faster.

- Lastly implement Davis’ Order Crossover and change mutation function.

We tried to use OX1 to gain faster results. What we did in our new crossover function involves the following steps.

- Create two random crossover points in the first parent copy the segment between them from the first parent to the offspring.
- Starting from the second crossover point in the second parent, copy the remaining unused numbers from the second parent to the first child wrapping around the list.
- Do the same for the second child with the first parent now being the second and vise versa.
- Since keeping them same mutation function or erasing it either breaks the application cause we would have more than one occurrences of the same number and this would break OX1 implementation or converges really fast getting stack in trying to find a combination where it doesn’t exist. We implemented a mutation function that every 30% of the time just inputs a random permutation of a new individual.

Example of David’s Crossover [2]

Now let’s make a consistent way of judging whether our enhancements indeed increase the efficiency of our algorithm timewise. So, we create a loop for the first 100 seeds and calculate the time it took the algorithm to find an optimal solution.

Adding a plot and statitics for the mean, average, variance, max, min will give us a feel for how good we did.

This plots shows our initial times:

The enhanced version clearly shows a significant increase in the efficiency of the algorithm.

The complete project is on GitHub https://github.com/nikkaramessinis/Genetic-Algorithm

If you liked the content please consider following Nick Karamessinis or https://www.buymeacoffee.com/nikaramesinis. For any corrections or additions you are more than welcome to comment for more discussion.

References

*[1] Artificial Intelligence A Modern Approach Third Edition*. (n.d.).

[2]*Genetic Algorithm: 8 Queens Problem | by Cheng Xi Tsou | Nerd For Tech | Medium*. (n.d.). Retrieved January 18, 2022, from

https://medium.com/nerd-for-tech/genetic-algorithm-8-queens-problem-b01730e673fd

*[3] Genetic Algorithms — Quick Guide*. (n.d.). Retrieved January 18, 2022, from https://www.tutorialspoint.com/genetic_algorithms/genetic_algorithms_quick_guide.htm