⚗️ Multithreaded Genetic Algorithm
- 1 minGenetic Algorithm to Solve the N-Queens Problem
After briefly learning about genetic algorithms in CPSC 322, a course on artificial intelligence, I decided to take my own crack at making one of my own over the winter break.
The problem I decided to solve was one that had been intoduced in the course - the N-Queens problem. The problem involves trying to place N queens on an N x N chess board, such that there are the least number of attacks between queens possible. For small sizes, this seems easy. Of course, you could always brute-force a problem like this, but for large N this becomes incredibly computationally intensive.
The idea of a genetic algorithm is inspired by evolution! Instead of brute-forcing the problem, we will assign possible solutions a score (called a "fitness score"). Possible solutions are called "strands of DNA," and instead of exhausting all possible solutions, random mutation and crossover is performed between the most fit strands with the goal of reaching a close-to-optimal solution.
I find this type of algorithm fascinating as it employs knowledge from a different field (in this case, biology) in order to derive an interesting solution to a common problem in computer science.
I was able to first write a sequential version which worked well enough. You provide the dimensions of the board, along with how many iterations/generations you'd like, and in the end a strand with the best fitness in the gene pool is spit out. However, being the systems guy I am, I figured I could obtain a bit of a speed-up if I employed the use of threads to perform some of the work in parallel. Doing this, I was able to acquire an approximate 1.44x speedup from the sequential implementation, which was really neat!
William Walcher
Computer Science Student at UBC