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:

Average Generations2.0184.5195.4838.0396.2
Median Generations11938.5320.5295.5
Average* Generations1.695.275.2521.9349.4
Solution Density128116641.8E61.4E7

*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

No comments: