Solving the n-queen puzzle with Genetic Algorithm in R

In this article, a genetic algorithm implementation to solve the 8-queen problem and its generalized version the n-queen problem will be described. This solution technique was presented in one of the lectures in the edX course ColumbiaX: CSMM.101x Artificial Intelligence (AI). The following description of the problem, the genetic algorithm and how it can be applied to solve the problem are taken from the course slides.

1. Genetic algorithms (GA) is a variant of stochastic beam search.
2. Successor states are generated by combining two parents rather by modifying a single state.
3. The process is inspired by natural selection.
4. Starts with k randomly generated states, called population. Each state is an individual.
5. An individual is usually represented by a string of 0’s and 1’s, or digits, or a finite set.
6. The objective function is called fitness function: better states have high values of tness function.
7. Pairs of individuals are selected at random for reproduction w.r.t. some probabilities.
8. A crossover point is chosen randomly in the string.
9. Offspring are created by crossing the parents at the crossover point.

10. Each element in the string is also subject to some mutation with a small probability.

11. In the 8-queen problem, an individual can be represented by a string digits 1 to 8, that represents the position of the 8 queens in the 8 columns.

12. Possible fitness function is the number of non-attacking pairs of queens that we are interested to maximize (which has the maximum value \(8 \choose 2\) = 28 for the 8-queen’s problem. In other words we want the number of attacking pairs of queens to be zero in the solution assignment of the queens.

13. The following figure shows how the crossover and mutation are applied on the candidate genes at different generation.

    

    Data File Format

14. The following figure shows the pseudocode for the genetic algorithm in its general settings.

    

    Data File Format

15. The following two figures show the solutions of the 8-queens problem obtained using genetic algorithm. Note that two different solutions are obtained starting with 2 different sets of populations generated using different random seeds.

    
    

16. The following animations show the best-fit chromosome obtained at each generation of the algorithm, starting with different mutation rates. Here the min.cost variable denote the number of attacking pairs left at any generation. As soon as a solution with 0 cost is obtained, it’s reported and the algorithm execution is stopped.

17. Also, note that with all other parameters are kept identical, the higher the mutation rate, the longer time the algorithm takes to converge in general.

    Convergence of the genetic algorithm With mutation rate 0.1

    

    Convergence of the genetic algorithm With mutation rate 0.2

    

    Convergence of the genetic algorithm With mutation rate 0.3

    

    Convergence of the genetic algorithm With mutation rate 0.3

    Convergence of the genetic algorithm With mutation rate 0.4

    

    Convergence of the genetic algorithm With mutation rate 0.5

    

    Convergence of the genetic algorithm With mutation rate 0.6

    

18. The algorithm is then generalized to solve the n-queens problem and the following animations show the solutions obtained with two different rates of mutation, for \(n=20\).