## Sunday, May 17, 2009

### Secret Research Project 4: N Queens Problem with GA

Over the last couple of days I had an idea and nothing to do, so I implemented a genetic algorithm search for the N Queens problem. The N Queens problem is a toy problem in chess, where you are given N queens and a N x N chessboard, and where you are supposed to place the queens such that they do not attack each other.

The idea behind the GA search is simple; each individual in the population represents one configuration of the board. Better solutions can breed, thus (hopefully) conserving better positions. The details of the GA I used are as in the standard literature, employing uniform crossover and mutation with no elitism. The fitness function employed is the number of non-mutually-attacking queen pairs.

I tested the performance of the GA search algorithm on the N queen problem for N=4,6,8,10,12. Each problem was run 20 times, resulting in the following results:

 N 4 6 8 10 12 Average Generations 2 184.5 195.4 838 396.2 Median Generations 1 19 38.5 320.5 295.5 Average* Generations 1.6 95.2 75.2 521.9 349.4 Solution Density 128 11664 1.8e+06 1.4e+07 6.3e+08 Efficiency 0.82 1.22 24.3 264 17968

*Average after discarding the 2 highest and lowest extremes.
Solution Density is the number of board configurations divided by number of distinct solutions; hence representing the number of random searches before a solution is found.
Efficiency is the solution density divided by average number of GA searches.

The results of the GA search are not too bad, though I was expecting better performance. However, the scaling seems a bit haphazard; I am unable to explain why N = 12 runs better than N = 10. Another point which is unreflected in this report is that for N = 15 and beyond, this GA search will require considerable time to run. More improvements are necessary.

Lastly, here are some of the solutions found by the GA search. A solution each for the N = 8 and N = 12 cases are shown.