8 Queens Solution with Genetic Algorithm

• Download demo - 18.3 Kb
• Download source - 2.32 Kb

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 
    for (int i=0;i<ChessBorad;i++)
        for (int j=0;j<ChessBorad;j++)
            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++)
        for (int a=0;a<ChessBorad;a++)
        {
            random=rand();
            bCheck=1;
            for (int b=0;b<a;b++)
            if (random%ChessBorad==ChromosomeMatrix[b][index])
                bCheck=0;
            if (bCheck)
                ChromosomeMatrix[a][index]=random%ChessBorad;
            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();
    for (int i=0;i<ChessBoradLenght;i++)
        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;
    for(i=0;i<ChessBoradLenght;i++)
    {    
        j=ChromosomeMatrix[i][index];
        m=i+1;
        n=j-1;
        while(m<ChessBoradLenght    && n>=0)
        {
            if(area[m][n]==1)
                costValue++; 
            m++;
            n--;
        }

        m=i+1;
        n=j+1;
        while(m<ChessBoradLenght && n<ChessBoradLenght )
        {        
            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;
        while(m>=0 && n<ChessBoradLenght)
        {        
            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;
                
            for (int j=0;j<ChessBoradLenght;j++)
            {
                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++)
        for (int a=0;a<ChessBoradLenght;a++)
        {
            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 p₀ and p₁. 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;
    int NumberOfMutation=int(MutationRate*(Population-1)*ChessBoradLenght);
    for(int k=0;k<=NumberOfMutation;k++)
    {
        randomChromosome=0;
        while((randomChromosome=rand()%Population)==00;
        randomGen0=rand()%ChessBoradLenght;
        while((randomGen1=rand()%ChessBoradLenght)==randomGen0);
        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.