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.0	184.5	195.4	838.0	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.8E6	1.4E7	6.3E8
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.

N = 8 Solution

N = 12 Solution