8 Queens Solution with Genetic Algorithm

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.