N-queen Solution Using Genetic Algorithm

With this program, we are going to find a solution for the classical N-Queen problem using Genetic Algorithm.

But, What is N-Queen Problem?

The N-Queens problem requires placing N chess queens on an NxN chessboard such that:

• No two queens are in the same row
• No two queens are in the same column
• No two queens are in the same diagonal line (both forward and backward diagonals)

The objective of the problem is to find all possible solutions to place N queens on an NxN chessboard, and it is considered an NP-complete problem, making it challenging to solve efficiently for large values of N.

Since it is an NP-Complete Problem, we can not use the brute force method to find the solutions. We can use AI techniques to find solutions faster. We can use Simulated Annealing, Constraint Satisfaction Problem (CSP), Genetic Algorithm, and so on.

What is Genetic Algorithm?

Genetic algorithms (GA) are a class of optimization algorithms inspired by the principles of natural selection and genetics. They are used to solve complex problems that may have many possible solutions.

At a high level, the GA works by creating a population of candidate solutions, also known as chromosomes, which are represented as strings of binary digits. Each chromosome represents a potential solution to the problem. The chromosomes are then evaluated using a fitness function that measures how well they solve the problem.

The GA uses several genetic operators to simulate the process of natural selection and reproduction. These operators include:

1. Selection : This process involves choosing the fittest chromosomes from the population to be the parents of the next generation.

2. Fitness : This step involves checking the fitness of the chromosomes.

3. Crossover : This process involves combining the genetic material of two parent chromosomes to create a new offspring chromosome.

4. Mutation : This process involves randomly changing the values of some of the genes in a chromosome to introduce new genetic diversity.

The GA then repeats this process of selection, crossover, and, mutation for a specified number of generations or until a satisfactory solution is found.

The key intuition behind genetic algorithms is that the fittest chromosomes have a higher probability of being selected as parents, and their genetic material is more likely to be passed on to the next generation. Over time, the population evolves towards better solutions to the problem.

Genetic algorithms have been applied to a wide range of optimization problems, including engineering design, scheduling, and data analysis. They are particularly effective when the search space is large and complex, and when there are many possible solutions that may be equally good.

Our Model of Representation of the Problem

Before solving any problem we need to model it in some mathematical way. Given below is the process of how we used Genetic Algo to solve the N-Queen problem.

1. Chromosome : Each chromosome is represented in a 1-D array where the index represents the Column and the value in it specifies the row.
2. Population A population of chromosomes is generated by placing one queen in each column at a random place. (Hence, we satisfy column constraint beforehand)
3. Fitness : Number of non-attacking pairs in a chromosome is calculated. Higher the number, the fitter the chromosome.
4. Select : We then convert the fitness index to percentage and use probability theory to randomly choose the next generation with more chances of choosing the fitter. This way less fit chromosomes die in long run and only fit chromosomes survive.
5. Cross-Over : Pairs of the selected chromosomes are made and crossed over at random points. It gives us a new chromosome with the properties of both its parents. It may or may not be fitter than their parents but again, only the fittest would survive in the long run.
6. Mutation : Finally analogous to evolution, there are random mutations in the chromosomes at random places.
7. Objective : The objective is to find the maximum possible fitness a chromosome can achieve. Since Max fitness would be the Max number of possible non-attacking pairs of the queens, we stop as soon as we find a solution. We aim to find one solution only rather than all possible ones.

We specify the size of the chessboard as input and it returns us the answer.