Transcript In n-queens…

N- Queens Solution with
Genetic Algorithm
By
Mohammad A. Ismael
N-Queens problem Definition
Here N=8
 Place N queens on an N*N
board so that no queen is
attacking another queen.
 A queen can move
horizontally, vertically, or
diagonally.
 The problem can be solved
with genetic algorithm for a
n queens problem. (n is
between 8 and 30)
8-Queens problem
Simple solutions may lead to very high search
costs
64 fields, 8 queens ==> 64^8 possible sequences
Genetic algorithm solution trim the search
space.
Problem formulation
Initial State: n queens placed randomly on the
board, one per column.
Successor function: moving one queen to a
new location.
Cost: The number of queens that hit each
others.
Genetic consists of
Genes
Chromosomes
Populations
In n-queens…
A gene is a number between 0 to n-1.
Is a position of any queen in the board
 A chromosome is an array of these genes. It
could be the solution.
 Population is a generated set of chromosomes.
Chromosomes and genes
A chromosome (array of genes. It could be an answer)
Gene
{3,6,8,5,1,4,0,7,9,2}
{7,6,9,5,1,4,0,3,8,2}
{9,6,1,5,8,4,0,7,3,2}
{6,3,8,5,2,4,0,7,9,1}
{3,6,8,5,1,4,0,7,9,2}
.
.
.
Population
Here N=10
Create a random initial population
An initial population is created from a random
selection of chromosomes.
 The number of generations needed depends on
the random initial population.
Finding the cost
To find the assigned cost for each chromosome
a cost function is defined.
The result of the cost function is called cost
value.
This value is used for chromosomes ranking
• The best (minimum value) is placed on top and the worst
(maximum) is placed in the bottom.
Producing next generation
 Those chromosomes with a higher fitness (lesser cost) value
are used to produce the next generation.
 The offspring (or Child) is a product of the two parents,
whose composition consists of a combination of genes from
them (this process is known as "crossing over").
 If the new generation (Child) contains a chromosome that
produces an output that is close enough or equal to the
desired answer then the problem has been solved.
 If this is not the case, then the new generation will go through
the same process as their parents did. This will continue until a
solution is reached.
Steps to solving the problem with GA
Clear the board.
Generate the initial population.
• This generation is a purely random generation.
Fill the chess board with a chromosome.
For example,
Let Chromosome Matrix= {3,6,8,5,1,4,0,
7,9,2},
Here Chess Board Length =10 (n=10).
Steps to solving the problem with GA
Determines the cost value for each chromosome
matrix.
 For example,
For chromosome ={ 2,6,9,3,5,
0,4,1,7,8 }, the cost value will be 2
Because of there are two queens
that hit each other
Steps to solving the problem with GA
Sort the new generation according to their cost
value.
 The best (minimum) is placed on top and the worst
(maximum) is placed in the bottom.
 Generate the cross over matrix. This matrix
contains 0s and 1s.
Steps to solving the problem with GA
 Generate children from
parents using cross over
matrix.
Genes are drawn from P0 and
P1.
 A gene is drawn from one
parent and it is appended to the
offspring (child) chromosome.
 The corresponding gene is
deleted in the other parent
This step is repeated until both
parent chromosomes are empty
and the offspring contains all
genes involved .
Steps to solving the problem with GA
Apply mutation to the current generation.
 First of all, a random chromosome is selected but
the first (best) one in the list.
 Then, two random genes of this chromosome are
selected and replaced with each other.
 Increasing the number of mutations increases the
algorithm’s freedom to search outside the current
region of chromosome space .
Example of such software
Questions?