8 Queens Problem
The N-queens problem is an effort to find a placement of N queens on an N by N chess board so that no two queens attack each other
At an initial state some queens may be attacking each other (i.e no 2 queens are on the same row, column, and diagonal).
GOAL: To evolve such a state using GA to find a state in which no 2 queens are attacking each other.
Genetic Algorithm
GA is one of the most popular meta-heuristic algorithms, its represent the space solution by population of chromosome and each chromosome work as a solution for the problem.
GA give the optimal solution depending on fitness function and also depending on the structure of algorithm. The algorithm repeats the crossover of chromosome and the mutation operations until reaching the optimal solution (stop condition).
Algorithm
Input: Initial random solutions.
Output: All possible solutions for eight queens problem.
Step1: Generate 100 random solutions. This was done by initializing 100 vectors (with length of 64), the values in each vector are either one for the queen or zero for the empty square. Thus each vector will have eight queens distributed randomly. This is the initial population for GA with size equal 100 chromosomes.
Step2: Evaluate the fitness of each chromosome (solution).
Step3: Rank the chromosomes depending on their fitness’s values (small fitness values first).
Step4: The 50 solutions that have the best fitness values are selected as parents and retained for the next generation. Those parents are then used to create another 50 offspring using single point crossover.
Step5: The new solutions are mutated.
Step6: Repeat steps 2-5 until a new solution to the 8-queens problem is found.
No comments:
Post a Comment