Genetic algorithm vs. Backtracking: N-Queen Problem
A comparison between Backtracking solver and Genetic algorithm performances.
A few months ago, I got familiar with genetic algorithms. I started to read about it and I was pretty amazed by it. One of the most famous problems solved by genetic algorithms is the n-queen problem. I implemented my genetic solver, plus the famous old backtracking solver using python 3. I implemented a Chess class (backtracking solver) and a GeneticChess class (genetic solver). These classes both have an attribute board which is a two dimension list. Each row of the list is filled with N zeros.
Backtracking solver
As you know, the backtracking solver is a simple function which starts solving the problem by putting a queen on the first row of the board and tries to put the second queen on the second row in a way it wouldn’t conflict the first one. It continues putting the queens on the board row by row until it puts the last one on the n-th row. If it couldn’t fill any tile on a row it would backtrack and change the position of the previous row’s queen.
The following tree describes how the backtracking algorithm solves the 4-queen problem.
The backtracking solver will find the solution for us. But as the N increases it becomes slower. If N=25, it would take 322.89 seconds to find the solution and when N=26, it would take forever! So an approach is needed which could find the solution pretty much quicker. Here’s the backtracking method:
def solveBackTracking(self,col):if col >= self.size:
self.solutions.append(self.board)
return Truefor i in range(self.size):
if self.isSafe(i,col):
self.board[i][col] = 1
if self.solveBackTracking(col+1) == True:
return True self.board[i][col] = 0return False
GA solver
One way is to solve the problem using genetic algorithms. So how does genetic algorithms work?
The base idea comes from what happens in the nature. In an environment, there exists some chromosomes(or gens). These chromosomes combine together and create some children in the environment. The new chromosome is a combination of its parents’ DNA and also it mutates itself. Of course, the environment has a population limit. Since each chromosome is unique from others, it is understood that some are stronger than the others. Based on the law of nature the stronger creatures will make it to the next generation and the weaker ones will die. So, we expect that each generation consists of stronger chromosomes. That’s how a genetic algorithm works.
The following steps should be taken to achieve a genetic algorithm:
- Create a chromosome representation
- Create an utility function
- Create a crossover function
- Create a mutation function
- Create the environment
Now let’s jump into these steps to create our genetic algorithm.
Step 1: Chromosomes
Basically, a chromosome (also called gen) is a representation of a solution whether it’s valid or not. How are we going to represent a n-queen solution? One way is to create a 2 dimension list filled with 0 and then, fill it with N ones representing the position of the queen. This maybe the first thing that comes to the mind but it’s not actually good. A better and simpler representation is that the chromosome is a list of length N. Each index specifies a column of the board. The value of each index is between 0 and N-1 representing the the row of a queen in a column.
Step 2: Utility Function
The Utility function is a function that determines how good is a solution. So the function takes a gen as its parameter and returns a number which is the utility. In this case our utility function will evaluate the number of conflicts based on queen positions. It is the summation of the number of conflicts on the left side of each queen. So if the utility function returns 0, we know that there are no conflicts on the board, therefore, we have our solution.
def utilityFunction(self,gen): hits = 0
board = self.createBoard(self.size)
self.setBoard(board,gen)
col = 0 for dna in gen:
try:
for i in range(col-1,-1,-1):
if board[dna][i] == 1:
hits+=1
for i,j in zip(range(dna-1,-1,-1),range(col-1,-1,-1)):
if board[i][j] == 1:
hits+=1
for i,j in zip(range(dna+1,self.size,1),range(col-1,-1,-1)):
if board[i][j] == 1:
hits+=1
col+=1
return hits
Step 3: Crossover function
As I said, the child chromosome is a combination of its parents’ DNA. This process is called Crossover. This function is the key function that makes the Genetic algorithm faster than the backtracking solver. There exists a lot of crossover functions and you can even implement your own. The function takes two chromosomes as the parameters. These are the parents and they are going to create new children chromosomes. I decided to swap the elements of the first list with the elements of the second list whenever the difference of two elements in one of the lists is less than 2.
def crossOverGens(self,firstGen,secondGen):
for i in range(1,len(firstGen)):
if abs(firstGen[i-1] — firstGen[i])<2:
firstGen[i],secondGen[i] = secondGen[i],firstGen[i]
if abs(secondGen[i-1] — secondGen[i])<2:
firstGen[i],secondGen[i] = secondGen[i],firstGen[i]Step 4: Mutation function
After the crossover process the child is created. Now the child tries to change itself somehow to decrease the utility value. After the crossover, some elements could be redundant in the gen (e.g. [1,1,2,3]). The mutation function will remove the redundant elements and fill them with the elements which weren’t used in the gen. Also a two random elements will be selected from the left side and right side of the chromosome and they will be swapped. This method may decrease the utility.
def MutantGen(self,gen): bound = self.size//2
from random import randint as rand
leftSideIndex = rand(0,bound)
RightSideIndex = rand(bound+1,self.size-1)
newGen = []
for dna in gen:
if dna not in newGen:
newGen.append(dna)
for i in range(self.size):
if i not in newGen:
newGen.append(i) gen = newGen
gen[leftSideIndex],gen[RightSideIndex] = gen[RightSideIndex],gen[leftSideIndex]
return gen
Step 5: The Environment
Now that we have our functions, let’s create our environment and its merciless rules. First we initialize the first generation of the chromosomes which are just some random chromosomes. After that all chromosomes are checked in order to find out whether the solution already exists or not. If it didn’t exist the chromosomes start to create children. Since the population exceeds its limit the utility of each chromosome is calculated. The ones with higher utility (higher conflicts) will be removed from the environment and the ones with a lower utility will be selected. Now the second generation is created. This loop continues creating next generations until it finds the solution.
def solveGA(self):
self.initializeFirstGenereation()
for gen in self.env:
if self.isGoalGen(gen):
return gen
while True:
self.crossOverAndMutant()
self.env = self.makeSelection()
if self.goalIndex >= 0 :
try:
return self.goal
except IndexError:
print(self.goalIndex)
else:
continueResults
As I mentioned, the Backtracking solver could only solve the problem at maximum N=25 which took about 322.89 seconds to find the answer. The GA solver found the solution for N=25 in just 1.83 seconds. The crossover and mutation function that I implemented aren’t the best algorithms and still I got a pretty much quick result. I tested the GA solver from N=4 up to N=66 and the maximum time took for the algorithm to solve the problem was 125.93 seconds for N=66. I have even tried N=80 and get the solution in 122.82 seconds! This is amazing! The algorithm is based on random numbers. It might seem that it would be worse than the backtracking solver but the results are quite fascinating.
I pretty much recommend implementing both B-Solver and GA-Solver yourself to see the magic of the Genetic Algorithms. You can find my code at my Github link.
Hope you find this article helpful!
