A solution to the 8 queen problem using the evolutionary algorithm approach.
Evolutionary algorithms are based on the Darwinian concept of evolution. It usually follows the following steps:
-
Initialize the population randomly
-
Calculate the fitness of each individual
-
Select individuals to reproduce based on some rule influenced by the fitness
-
Recombine the selected parents to generate new sons.
-
Crossover
-
Mutation
-
The main difficulty in the evolution process is to find a good balance between exploration of the problem space and exploitation of local minima. Increases in crossover and mutation probability usually lead to an increase in exploration. On the other hand, a small recombination probability leads to sons being more similar to their parents, which causes an increase in exploitation. Other means of increasing exploitation involve:
-
Elitist parent selection
-
Crossover rules biased towards preservation of parent genotype
-
Mutation probability set to low
However, if the algorithm is too biased toward exploitation this may lead to early convergence, which may not offer the desired solution.
The 8 queens problem is to find a chessboard configuration where 8 queens so that no two queens threaten each other. This problem is NP-complete which makes large boards unfeasible to solve algorithmically. Many approaches have been proposed to offer a solution to the problem, they are usually based on a given heuristic.
We developed a standard evolutionary algorithm to solve the 8 queens problem.
-
Fitness function: The sum of all conflicts on a given board
-
Parent selection: Two parents were randomly picked out of the 5 best individuals in the population
-
Recombination
-
Crossover:
-
Standart crossover
-
Crossover at the edges of the array
-
-
Mutation:
- Standart mutation
-
Dynamic tuning of crossover and mutation probability
-
The following metrics were used to evaluate the performance of a given architecture:
-
Num of epochs to reach convergence
-
Average num of epochs
-
Mean num of epochs
-
-
Best individual fitness
-
Standard deviation fitness
-
Average fitness