Introduction
There are several ways to solve NP-hard problems. Genetic algorithm is one easy approach to solve such kind of problems. This article is about solving 8 queens puzzle with genetic algorithm using C#.
The eight queens puzzle is the problem of placing eight chess queens on an 8×8 chessboard so that no two queens attack each other. Thus, a solution requires that no two queens share the same row, column, or diagonal.
In order to use genetic algorithm, it is a must to define the crossover operator, mutation operator, chromosome and genes.
Problem Representation
Gene: A gene is a number from 0 to 7 that means the row number that a queen is located. The position of the gene in a chromosome implies the column number of the queen. It is mandatory to locate one queen per column and row because there are same number of queens and columns/rows in the board.
Chromosome: A chromosome is a set of 8 genes. It is assumed to be that no duplicate genes in a chromosome.
Example:
0|1|4|2|3|6|7|5 8 queens are located in following cells.
(0,0), (1,1), (2,4), (3,2), (4,3), (5,6), (6,7), (7,5)
Mutation: Mutation is done with swapping the gene that is to be mutated with a randomly selected gene (except the gene that is currently subjected to the mutation) from the same chromosome.
Crossover: Genes are drawn from the two parent chromosomes with the probability of 0.5. A gene is drawn from one parent and it is appended to the offspring 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.
Fitness Function: A collision is two queens who are able to attack each other. This means they are in the same diagonal, the same row or the same column. Since the chromosome has no duplicate genes and it guarantees that 2 queens are not in a single column it is only needed to calculate the diagonal collisions. Therefore maximum number of collisions that can occur is 28. The fitness function is a higher-is-better function, so calculate it by subtracting the amount of collisions that occur in the current state from 28. A solution would have 0 collisions and thus a fitness of 28.
Using the Code
Classes and Structures
class GeneticAlgo: The class that is responsible for all the operations of genetic algorithm.class FitnessComparator: A comparator class to sort chromosomes with fitness value in order to show the final population in the table. struct Chromosome: The structure that represents a chromosome which include genes, fitness and its cumulative of average fitness.class MainFrame: The class that responsible for handling user interface and create initial population in order to pass to the genetic algorithm.class Board: The class that is responsible for graphical view and operations of the chess board.
Variables
private const int <code>MAX_FIT = 28; holds the maximum fitness.
Functions
private List<chromosome> GetInitialPopulation(int population)
{
List<chromosome> initPop = new List<chromosome>();
GeneticAlgo RandomGen = new GeneticAlgo();
for (int i = 0; i < population; i++)
{
List<int> genes = new List<int>(new int[] {0, 1, 2, 3, 4, 5, 6, 7});
Chromosome chromosome = new Chromosome();
chromosome.genes = new int[8];
for (int j = 0; j < 8; j++)
{
int geneIndex = (int)(RandomGen.GetRandomVal
(0,genes.Count-1)+0.5);
chromosome.genes[j] = genes[geneIndex];
genes.RemoveAt(geneIndex);
}
initPop.Add(chromosome);
}
return initPop;
}
This function takes the size of population as the parameter and returns a list of chromosomes that contain randomly generated genes. The values of genes are randomly selected from a list that contains 0 to 7. While selecting the values from the list, the selected values are removed to avoid the duplication of genes in a chromosome. The size of the list is equal to the size of population. After creating the initial population using this function, the returned list of chromosomes sends to the function DoMating.
public void DoMating(ref List<Chromosome> initPopulation,
int generations, double probCrossver, double probMutation)
{
int totalFitness = 0;
CalcFitness(ref initPopulation, ref totalFitness);
for (int generation = 0; generation < generations; generation++)
{
PrepareRuletteWheel(ref initPopulation,totalFitness);
Crossover(ref initPopulation, probCrossver);
Mutate(ref initPopulation, probMutation);
CalcFitness(ref initPopulation, ref totalFitness);
if (initPopulation[initPopulation.Count - 1].fitness == 28)
break;
if (progress != null)
{
progress(generation + 1);
}
}
initPopulation.Sort(new FitnessComparator());
}
This function takes a list of chromosomes as the initial population, number of generations that we are willing to propagate in the algorithm, the crossover probability and the mutation probability as its parameters. The responsible of this function is to handle the propagation to the required generation by invoking the functions CalcFitness, PrepareRuletteWheel, Crossover and Mutate.
public void CalcFitness(ref List<Chromosome> chromosome, ref int totalFitness)
{
int collisions = 0;
totalFitness = 0;
for (int k = 0; k < chromosome.Count; k++)
{
for (int i = 0; i < chromosome[k].genes.Length - 1; i++)
{
int x = i;
int y = chromosome[k].genes[i];
for (int j = i + 1; j < chromosome[k].genes.Length; j++)
{
if (Math.Abs(j - x) == Math.Abs
(chromosome[k].genes[j] - y))
collisions++;
}
}
Chromosome temp = chromosome[k];
temp.fitness = MAX_FIT - collisions;
chromosome[k] = temp;
totalFitness += chromosome[k].fitness;
collisions = 0;
}
}
This function calculates the fitness of each chromosome and assigns the fitness value to the property fitness of each chromosome. The fitness is calculated by counting the number of collisions and deduct it from the maximum number of collisions because in this code the fitness is a higher-is-better function. While calculating the fitness for each chromosome, this function also calculates the total fitness of the population because we need it in the next step to calculate the fitness ratio of each chromosome.
private void PrepareRuletteWheel(ref List<Chromosome> parents,int total)
{
int currentTotalFitness=0;
for (int i = 0; i < parents.Count; i++)
{
currentTotalFitness += parents[i].fitness;
Chromosome temp = parents[i];
temp.cumAvgFitness = currentTotalFitness / (double)total;
parents[i] = temp;
}
}
A rulette wheel that is based on the fitness of chromosome is used for selecting parents to mate in order to generate a new generation. This function is responsible for preparing the rullette wheel and it takes a list of chromosomes as the current population and the total fitness of the population. The function calculates the ratio of fitness of each chromosome to the total fitness and then calculates the cumulative of it to assign to the property cumAvgFitness of a chromosome.
public void Crossover(ref List<Chromosome> parents, double probability)
{
List<Chromosome> offspring = new List<Chromosome>();
for (int i = 0; i < parents.Count; i++)
{
if (Assay(probability))
{
Chromosome parentX = AssayRuletteWheel(parents);
Chromosome parentY = AssayRuletteWheel(parents);
List<int> child = new List<int>();
for (int j = 0; j < 8; j++)
{
if (Assay(0.5))
{
for (int k = 0; k < parentX.genes.Length; k++)
{
if (!child.Contains
(parentX.genes[k]))
{
child.Add(parentX.genes[k]);
break;
}
}
}
else
{
for (int k = 0; k < parentY.genes.Length; k++)
{
if (!child.Contains
(parentY.genes[k]))
{
child.Add(parentY.genes[k]);
break;
}
}
}
}
Chromosome offSpr = new Chromosome();
offSpr.genes = child.ToArray();
offspring.Add(offSpr);
}
else
{
Chromosome parentX = AssayRuletteWheel(parents);
offspring.Add(parentX);
}
}
while (offspring.Count > parents.Count)
{
offspring.RemoveAt((int)GetRandomVal(0, offspring.Count - 1));
}
parents = offspring;
}
This function is responsible for crossing over and cloning operations. The function takes a list of chromosomes as the current population and the crossover probability as its parameters. The function Assay(int probability) returns true with the given probability, therefore it is used with the crossover probability to determine whether the operation is a crossing over or a cloning.
if (Assay(probability))
{
Chromosome parentX = AssayRuletteWheel(parents);
Chromosome parentY = AssayRuletteWheel(parents);
List<int> child = new List<int>();
for (int j = 0; j < 8; j++)
{
if (Assay(0.5))
{
for (int k = 0; k < parentX.genes.Length; k++)
{
if (!child.Contains(parentX.genes[k]))
{
child.Add(parentX.genes[k]);
break;
}
}
}
else
{
for (int k = 0; k < parentY.genes.Length; k++)
{
if (!child.Contains(parentY.genes[k]))
{
child.Add(parentY.genes[k]);
break;
}
}
}
}
Chromosome offSpr = new Chromosome();
offSpr.genes = child.ToArray();
offspring.Add(offSpr);
}
This part of code is from the above function and is responsible for crossover the two parents parentX and parentY. In order to create the offspring, genes are selecting from two parents with a probability of 0.5 while avoiding the gene duplication in the chromosome.
In the cloning operation, one parent is directly brought to the next generation.
public void Mutate(ref List<Chromosome> parents, double probability)
{
List<Chromosome> offsprings = new List<Chromosome>();
for (int i = 0; i < parents.Count; i++)
{
Chromosome offspring = parents[i];
for (int mutatePosition = 0; mutatePosition < 8; mutatePosition++)
{
if (Assay(probability))
{
int newGeneIndex = (int)(GetRandomVal(0,6)+0.5);
if (newGeneIndex>=mutatePosition)
{
newGeneIndex += 1;
}
int swapTemp = offspring.genes[mutatePosition];
offspring.genes[mutatePosition] =
offspring.genes[newGeneIndex];
offspring.genes[newGeneIndex] = swapTemp;
}
}
offsprings.Add(offspring);
}
parents = offsprings;
}
This function applies the mutation operator with the given probability. It assays the chance of mutation while traversing the genes of chromosomes in the current population. If the mutation has to be applied to a gene, then it's value swaps with a randomly selected gene except the gene that is subjected to mutate from the same chromosome.
When a solution is achieved, the array of genes in the chromosome that contains the solution can be set to the property that are named as Genes in the class Board.
How to Use
The program allows you to specify the population size, number of generations, crossover probability and the mutation probability. The algorithm can be executed using the start button. If the population size and the number of generations are too large, please use the progress bar to indicate the current generation. But it can dramatically slow down the algorithm.
All the chromosomes of the final generation are shown in the table and the graphical chess board shows the best result.
The source code is available to download.
