i recently started cs6601 (artificial intelligence) in my master's program and one of the early topics the course briefly covers is a class of algorithms called genetic algorithms as a way of solving search problems. i found this very fascinating as it borrows elements from biology to be used in solving complex search problems!
before i get into what the class of algorithm is, i want to give some context on solving problems via searching. the material states that any class of problem wherein the environment if fully known, discrete, static, actions are deterministic, and a solution is known to exist - can be solved via a search algorithm
the n-queens problem is one such problem that can be solved through search. here we introduce the concept of genetic algorithms. essentially we're treating the queens on a chess board like a species. we'll simulate evolution by eliminating any "weak" boards (boards that aren't any closer to solving the problem) through multiple generations and reproducing "strong" boards, until we end up with a solution board (survival of the fittest). fascinating! how do we do this?
first encode the 2d chess board in a way that's easier to manipulate. we can represent a chess board with n-queens on it as an array of length 8. the values at each index will represent the row number the queen is on and the index number itself will represent the column. so for the board [1, 2, 3, 4, 5, 6, 7, 8], we have queens starting from row 1, column 1 and following a diagonal down to the last queen in row 8, column 8.
we'll start with 4 "parent" boards, which are randomly selected/generated. we want to choose the "strongest" parents to produce offspring boards - but how do we determine that? we do that through something called a fitness function. the maximum number of attacking queens an 8x8 board can have is 28. our fitness function will be f(x)=28-num_attacking_queens. a higher fitness function score means a board has less attacking queens and thus is theoretically closer to the solution. (we'll know we've reached our solution when the fitness function score equals 28) we're going to want to get the fitness score for each parent and use that to determine the probability with which it will be chosen to "reproduce".
we choose 4 parents based on these probabilities (A, B, C, D). a pair of parents will create 2 child boards. to create the child boards we'll randomly choose a crossover point for each pair of parents, think of this as an index where for the first child, we'll take the values from parent 1 from the left of the crossover point and values from parent 2 from the right of the crossover point. for the 2nd child we'll start with parent 2 instead. we do this over and over, for N generations and we should eventually get to the solution. but what if the parents we start with don't have a critical piece of the solution (e.g a queen required on row 2 in column 2)? or if a critical piece of the solution is "evolved" out because it doesn't immediately lead to a less amount of attacking queens?
we can handle this through mutations! once a child is generated, each digit in the string/array has some small random probability of mutating to another digit. in our example, this would translate into a queen randomly moving to a different row. with this, we should be able to work around the issue of missing a critical piece of the solution.
and that's it, (at a very, very high level), on how genetic algorithms can be used to solve the n-queens problem! what's really interesting is encoding the problem in a way that makes it suitable for such an algorithm to solve it. and of course, computer science borrowing terms/concepts from biology to solve computation problems.