N Queens Genetic Algorithm

N queens problem solver via genetic algorithm

    Made by David Guido

    Built with Pygame, an open source game engine
    For CPSC 481 (Artificial Intelligence) at California State University Fullerton

    Spring 21'

---

Table of contents

• N Queens Genetic Algorithm
  • Introduction
  • Approach
  • Analysis
  • Graphical User Interface
  • Evaluation
  • Conclusion
  • Demos

---

Introduction

• A Genetic Algorithm (GA) is known to apply the genetic concepts of selection, crossover, and mutation process into solving Computer Science problems. This report aims to focus on how to use GA to solve the NQueens problem. The NQueens problem is a question of how to put N queens into a board which has size of NxN that no queen attacks any others (highest fitness value)

• Each new layout of queens represents a state (N elements), biologically called a chromosome with N genes. To reach the solution, we must find the best state (chromosome) that has the highest fitness value.
  
  

---

Approach

1. Obtaining and inheriting base class NQueen (search.py, utils.py)
   • Defining fitness value of a state inside NQueen
   • Customize genetic search and GA itself for better result
   • Other customization if needed
     
     
2. Visualization result (background.py, n_queens_game.py, images folder)
   • Preparing graphic user interface background
   • Allowing user to select mutation rate, generation numbers, and N size
   • Loading background interface of options and buttons
   • Viewing real time searching process into interface
     
     
3. Advance options (future studies)
   • Showing selection, crossing over, and mutation process each iteration
   • Considering adding music and animation into search process
   • Other advance features: multiple problem solver application
     
     

---

Analysis

1. Theoretically, how many pairs of queens can be placed onto an NxN board, without any attacks taking place? This can be calulated by (N)(N-1)/2
   
   
2. The real fitness of the state is the maximum number of non attack queen pairs. However, how many queen pairs attacked each other at a specific state? Note the heuristic function that is built in the NQueen problem class:

def h(self, node):
"""Return number of conflicting queens for a given node"""
    num_conflicts = 0
    for (r1, c1) in enumerate(node.state):
        for (r2, c2) in enumerate(node.state):
            if (r1, c1) != (r2, c2):
                num_conflicts += self.conflict(r1, c1, r2, c2)

3. Therefore, the fitness value at a specific state would be (1)-(2) or:

def value(self, state):
    myNode = Node(state)
    return int((self.N) * ((self.N) - 1) / 2 - self.h(myNode))

As students, we reuse code of the **NQueen class**, and build up one more function called **value(self, state)**.

Calling a combination of N queens on a board represents a state. The purpose of this function is to evaluate the fitness value of that state. The higher this value is, the better we look for the resulting solution.

4. Note that the self.h(mode) is the total conflict of a state. By looking through all chromosomes that are randomly processed by GA’s population, we look for the smallest so that the fitness value (above) is the highest.
   
   

5. Together with the based class of NQueen and our fitness value implemented, lets initialize the NQueen problem in main function:

n = int(input("Enter Queen number: "))   #i.e. 5
ngen = 31
pmut = 0.1
#initialize problem
myNQueen = NQueensProblem(n)
print("Beginning!")
genetic_search(myNQueen, ngen, pmut, n)

Basically, the value n is the input value of how many queens you want to place in the board. It is input by the user.

6. Now, let’s go through the genetic_search(function) with parameter of problem(myNQueen). How will generations loop through(ngen)? What is the rate of mutation (pmut) and the default value of gene numbers inside a state (n)?

def genetic_search(problem, ngen, pmut, n):
    s = problem.initial
    states = [problem.result(s, a) for a in problem.actions(s)]
    random.shuffle(states)
    gene_pool = range(0,n)
    genetic_algorithm(states[:n], problem.value, 
                      gene_pool, n * (n - 1) / 2, ngen, pmut)

7. By defining all states before shuffling, and declaring gene_pool(all valid value of a gene), we can start to look through the core algorithm genetic_algorithm

   1. The first step is to define the population (init_population function):

   population = init_population(ngen, gene_pool, len(gene_pool))

   
   
   2. Next loop through each population(loop), select (select function), then crossover (recombine function), and then mutate them (mutate). These processes will be looped for each population:

   for i in range(ngen):
       population = [mutate(recombine(*select(2, population, fitness_fn)),
                     gene_pool, pmut) for j in range(len(population))]

   
   
   3. For easier-to-track fitness values and chromosomes in each loop, lets display the information to the screen (Commented out at the moment)

   for j in range(len(population)):
       print("---Element",j,":",population[j],'f=',fitness_fn(population[j]))

   • And show the maximum fitness value and the best fit individual of that loop

   fittest_individual = max(population, key=fitness_fn)
   fitness_value = fitness_fn(fittest_individual)
   print("Max fitness at loop ", i, " is ", fittest_individual, 
         " with f= ", fitness_value)

   
   
   4. If we see the fittest individual (its fitness value >= f_thres) then we output that individual to screen and stop looping. For the fittest individual, f_thres = N*(N-1)/2:

   if fitness_value >= f_thres:
      print("Best fittest found!", fittest_individual, "with f=", fitness_value)
   return None

   
   
   5. Otherwise, keeping looping without the fitness individual found yet. We end up showing the best fit individual from last loop (Commented out at the moment)

   print("Not the best but I found :")
   temp = max(population, key=fitness_fn)
   print(temp, "f = ", fitness_fn(temp))

---

Graphical User Interface

• This project uses PyGame, an open source game engine to render both a menu scene and a puzzle scene to the screen as well as properly respond to user input. We developed a dynamic interface that responds to user-inputted changes in N’s value in real time by increasing/decreasing the board size.

UI Demo Images

• Main Menu Scene
  

  • Note: Pressing start takes the user to the puzzle scene
    
    

• Puzzle Scene #1
  

  • Note: These are the default values for N, NGen & Mutation
    
    

• Puzzle Scene #2
  

  • Note: 4 is the minimum value for N
    
    

• Puzzle Scene #3
  

  • Note: 10 is the maximum value for N
    
    

• Puzzle Scene #4
  

  • Note: After the find solution button is pressed, the following message is printed to the screen prior to a solution being found:
    Please wait
    Current Iteration: x
    
    

• Puzzle Scene #5
  

  • Note: After a solution is found the following message is printed to the screen:
    Solution: [ v1, v2, v3, .., vn ]
    Total Iterations: k

---

Evaluation

• Recall that it is impossible to seek a solution at N from 1 to 3. Hence, the conductors measure application performance with N starting at 4:
• Within 10 runtimes per N value, the average time, iterations, time per iteration result are:

N	Average overall time(s)	Iterations (#)	Average time/iteration(s)
4	1 - 3	3 - 10	0.2 - 0.4
5	5 - 10	10 - 30	0.3 - 1
6	20 - 40	1000 - 2500	0.2 - 0.3
7	120 - 480	2000 - 4500	0.2 - 0.4
8, 9	600 - 1200	4000 - 6000	0.5 - 0.9

---

Conclusion

• There are some remaining issues that could undoubtably be improved on:

1. Since the selection, crossover, and mutation are random, there is no guarantee that GA will precisely find the fittest individual (with the highest value) with no conflict at all.

   • Suggestion: Customize the loop so that it doesnt end by a generation number but until it actually seeks out for the highest fitness of N chromosome’s size. The downside of this is the long time committed when running code with big values of N, starting at 6.

2. Attempting to implement the while loop with stop looping condition of seeking for the fittest individual seems ambiguous in many cases, especially if N is big and it strongly depends on every runtime compile.

   • Suggestion: Use a better computational engine instead

3. Duplicate during GA process and showing the best fit individuals per generation

   • Suggestion: Customize the crossover step of the GA program in two main ways: either by crossing-over in the middle of the chromosome or by crossing-over at 2 differently random points of the chromosome.

4. In conclusion, the GA is a good algorithm for discovering solutions for tough and required resource problems, like N queen attackers in this case. This project approaches the problem biologically by implementing a solver via genetic concepts.

---

Demos

Click to watch demo on YouTube (Readme file doesn't allow video playback)

N queens solution with N = 6 found in only 2 iterations!

N queens solution with N = 4 found in 4 iterations!

N queens solution with N = 8 found in 138 iterations!

---

Thanks for reading!

If you like what you see give this repo
a star and share it with your friends.

Your support is greatly appreciated!