15,169,085 members
Articles / Artificial Intelligence
Article
Posted 19 Oct 2005

316.7K views
85 bookmarked

# 8 Queens Solution with Genetic Algorithm

Rate me:
Using Genetic Algorithm to solve the 8 Queens problem.

## Genetic Algorithm, Theory

There are so many books and so many resources on the Web about Genetic Algorithms. The best that I can do is quote some nice descriptions from my preferred sites.

"Genetic algorithms are a part of evolutionary computing, which is a rapidly growing area of artificial intelligence. As you can guess, genetic algorithms are inspired by Darwin's theory about evolution. Simply said, solution to a problem solved by genetic algorithms is evolved."

The GA begins, like any other optimization algorithm, by defining the optimization variables. It ends like other optimization algorithms too, by testing for convergence. A path through the components of the GA is shown as a flowchart in Figure 1.

Fig. 1 - A path through the components of the GA

#### Define cost function and cost

For each problem there is a cost function. For example, maximum of a 3D surface with peaks and valleys when displayed in variable space. Cost, a value for fitness, is assigned to each solution.

#### Chromosomes and genes

A gene is a number between 0 to n-1. A chromosome is an array of these genes. It could be an answer. Population in each generation has determined the number of chromosomes.

#### Create a random initial population

An initial population is created from a random selection of chromosomes. The number of generations needed for convergence depends on the random initial population.

#### Decode the chromosome and find the cost

To find the assigned cost for each chromosome a cost function is defined. The result of the cost function called is called cost value. Finally, the average of cost values of each generation converges to the desired answer.

#### Mating and next generation

Those chromosomes with a higher fitness (lesser cost) value are used to produce the next generation. The offsprings are a product of the father and the mother, whose composition consists of a combination of genes from them (this process is known as "crossing over"). If the new generation 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.

## About the 8 queens problem

In chess, a queen can move as far as she pleases, horizontally, vertically, or diagonally. A chess board has 8 rows and 8 columns. The standard 8 by 8 queen's problem asks how to place 8 queens on an ordinary chess board so that none of them can hit any other in one move. Here we solve this problem with a genetic algorithm for a n (n is between 8 and 30) queen problem.

## Using the code

We first describe the variables and the functions:

### Variables:

• `int ChromosomeMatrix[30][1000]`: This variable is a matrix of numbers between 0 to `ChessBoardLenght`-1. For example, if `ChessBoardLength`=8, `ChromosomeMatrix` could be {4,6,0,2,7,5,3,1} so that the first number defines the place of the queen in the first row, the second number defines the place of the queen in the second row and so on.
• `int CostMatrix[1000]`: For each chromosome matrix, a cost value is defined. The best value is 0 and when no queen can take the other one.
• `int CrossOverMatrix[30][1000]`: For generating children from parents, a crossover matrix is needed that decides which gene must be selected from the two parents.
• `int Population`, `int Iteration`, `float Mutationrate`: These variables are genetic algorithm parameters.
• `int ChessBoardLength`: This determines how many rows and columns a chessboard has.
• `int area[30][30]`: This variable is a chess board matrix.

### Functions:

```void CGAQueen::Clear()
{
// to Reset All cells
area[i][j]=0;
}```

This function is used to clear the chess board (`area[][]`) with 0s.

```void CGAQueen::InitialPopulation()
{
int random;
bool bCheck;
for (int index=0;index<=Population-1;index++)
{
random=rand();
bCheck=1;
for (int b=0;b<a;b++)
bCheck=0;
if (bCheck)
else
a--;
}
}```

This function is used to generate the initial population. This generation is a purely random generation. With this function, `ChromosomeMatrix[][]` is valued with random numbers between 0 and `ChessBoardLength`-1. The number of `ChromosomeMatrix` is equal to `Population`.

```void CGAQueen::FillArea(int index)
{
Clear();
area[i][ChromosomeMatrix[i][index]]=1;
}```

This function is used to fill the chess board with a chromosome. For example, if `ChromosomeMatrix` = {3,6,8,5,1,4,0,7,9,2}, the first number defines the column of the queen in the first row, the second number defines the column of the queen in the second row and so on. The area is shown in fig. 2 – here `ChessBoardLength` =10.

Fig. 2 - The chess board with `ChromosomeMatrix`={ 3,6,8,5,1,4,0,7,9,2}

```int CGAQueen::CostFunc(int index)
{
int costValue=0;
int m,n;
int i,j;
{
j=ChromosomeMatrix[i][index];
m=i+1;
n=j-1;
{
if(area[m][n]==1)
costValue++;
m++;
n--;
}

m=i+1;
n=j+1;
{
if(area[m][n]==1)
costValue++;
m++;
n++;
}
m=i-1;
n=j-1;
while(m>=0 && n>=0)
{
if(area[m][n]==1)
costValue++;
m--;
n--;
}
m=i-1;
n=j+1;
{
if(area[m][n]==1)
costValue++;
m--;
n++;
}
}
return costValue;
}```

This function is used to determines the cost value for each `ChromosomeMatrix[][]` and keeps it in `CostMatrix[]`. For example, for chromosome = { 2,6,9,3,5,0,4,1,7,8 }, the cost value will be 2. (See fig. 3.)

Fig. 3 - Because of these two queens that hit each other, the cost value is 2.

```void CGAQueen::PopulationSort()
{
bool k=1;
int Temp;
while (k)
{
k=0;
for (int i=0;i<=Population-2;i++)
{
if (CostMatrix[i]>CostMatrix[i+1])
{
Temp=CostMatrix[i];
CostMatrix[i]=CostMatrix[i+1];
CostMatrix[i+1]=Temp;

{
Temp=ChromosomeMatrix[j][i];
ChromosomeMatrix[j][i]=ChromosomeMatrix[j][i+1];
ChromosomeMatrix[j][i+1]=Temp;
}
k=1;
}
}
}
}```

This function is used to 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.

```void CGAQueen::GenerateCrossOverMatrix()
{
int randomCrossOver;
for (int index=0;index<=Population-1;index++)
{
randomCrossOver=rand();
CrossOverMatrix[a][index]=randomCrossOver%2;
}
}```

This function is used to generate the cross over matrix. This matrix contains 0s and 1s.

```void CGAQueen::Mating()
{
int TempMatrix[30][2];
int TempMatrix0[30],TempMatrix1[30];
int Temp,j,k;

…
}```

This function is used to generate children from parents using `CrossOverMatrix`. It is a way to do this job. 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 (see figure 4). This step is repeated until both parent chromosomes are empty and the offspring contains all genes involved.

Fig. 4 The Cross Over method

```void CGAQueen::ApplyMutation()
{
int randomChromosome;
int randomGen0,randomGen1;
int Temp;
for(int k=0;k<=NumberOfMutation;k++)
{
randomChromosome=0;
while((randomChromosome=rand()%Population)==00;
Temp=ChromosomeMatrix[randomGen0][randomChromosome];
ChromosomeMatrix[randomGen0][randomChromosome]=
ChromosomeMatrix[randomGen1][randomChromosome];
ChromosomeMatrix[randomGen0][randomChromosome]=Temp;
}
}```

This function is used to 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.

There is a demo for you to enjoy the genetic algorithm.

Have fun.

A list of licenses authors might use can be found here

## Share

 Web Developer Iran (Islamic Republic of)
I live in Iran . I started hardware programming when I was young. I designed and built some ISA cards for attaching to PC.like ocsiloscope and signal generator. Now I am working for a engineering company and Manager of some project.

 FirstPrev Next
 random float number nhquang26-Oct-06 21:02 nhquang 26-Oct-06 21:02
 Re: random float number asef30-Oct-06 3:28 asef 30-Oct-06 3:28
 Nice work Hatem Mostafa24-Mar-06 2:12 Hatem Mostafa 24-Mar-06 2:12
 Poor, Misleading, Invalid Medus20-Nov-05 15:56 Medus 20-Nov-05 15:56
 Re: Poor, Misleading, Invalid Medus20-Nov-05 16:11 Medus 20-Nov-05 16:11
 Re: Poor, Misleading, Invalid YDLU10-Apr-06 13:02 YDLU 10-Apr-06 13:02
 Re: Poor, Misleading, Invalid Medus12-Apr-06 9:56 Medus 12-Apr-06 9:56
 Re: Poor, Misleading, Invalid David Roh20-Aug-06 5:03 David Roh 20-Aug-06 5:03
 Hi Medus, I have read a number of your comments on CP and would like to discuss an interesting problem that I am working on - davidjjon@hotmail.com
 Re: Poor, Misleading, Invalid cristitomi7-Mar-07 5:33 cristitomi 7-Mar-07 5:33
 Re: Poor, Misleading, Invalid garychapman15-Aug-07 11:12 garychapman 15-Aug-07 11:12
 cross over rate mbedward1-Nov-05 16:48 mbedward 1-Nov-05 16:48
 Re: cross over rate asef1-Nov-05 19:22 asef 1-Nov-05 19:22
 Re: cross over rate mbedward2-Nov-05 16:06 mbedward 2-Nov-05 16:06
 contact with u amin chegeni28-Oct-05 10:00 amin chegeni 28-Oct-05 10:00
 Re: contact with u asef29-Oct-05 2:06 asef 29-Oct-05 2:06
 good one zxaar28-Oct-05 0:20 zxaar 28-Oct-05 0:20
 Cool Article Serge R24-Oct-05 7:18 Serge R 24-Oct-05 7:18
 Nice one hairy_hats24-Oct-05 2:28 hairy_hats 24-Oct-05 2:28
 Re: Nice one asef26-Oct-05 22:10 asef 26-Oct-05 22:10
 Re: Nice one hairy_hats27-Oct-05 3:44 hairy_hats 27-Oct-05 3:44
 Hi Asef great article! Pete in Australia Petey Boy24-Oct-05 0:05 Petey Boy 24-Oct-05 0:05
 Got my 5 Mehdi Bonvari22-Oct-05 3:07 Mehdi Bonvari 22-Oct-05 3:07
 Re: Got my 5 asef22-Oct-05 3:16 asef 22-Oct-05 3:16
 Excellent! A. Riazi20-Oct-05 0:50 A. Riazi 20-Oct-05 0:50
 Last Visit: 31-Dec-99 19:00     Last Update: 18-Jan-22 11:38 Refresh ᐊ Prev123