Exploring Genetic Algorithms: A Deep Dive into the N-Queen Problem
Author(s): Hossein Chegini
Originally published on Towards AI.
“A 100-Queen solution”… photo from ‘repo/images/solutions’
Code Investigation
In a previous introduction, the fundamental steps for training a Genetic Algorithm (GA) were detailed, covering key concepts such as mutation, genes, chromosomes, and genetic populations. A case study was presented on solving the N-Queen problem using a GA. Following this, I created a repository, converting my Matlab code into Python. This article focuses on the repository’s components and how the main file is structured to configure the GA scenario and find the optimal solution. You can find the repository here.
The main file, n_queen_solver.py, is the entry point to configure the GA model and initiate the training process. It prompts the user to provide essential parameters crucial for configuring the GA model. These settings include:
- Chromosome Size or Board Size: The size of the board, representing the number of queens and the board’s dimensions.
- Population Size: The number of chromosomes in the population, representing the number of candidate solutions.
- Epochs: The number of iterations or generations for which the GA model will be trained.
The following code snippet illustrates how these parameters are gathered:
parser = argparse.ArgumentParser(description="Calculating the GA model to find the n-queen problem.")
parser.add_argument('chromosome_size', type=int, help="The size of a chromosome")
parser.add_argument('population_size', type=int, help="The size of the chromosome population")
parser.add_argument('epochs', type=int, help="The number of iterations to train the GA model")
args = parser.parse_args()
Once parameters are obtained, the population is initialized using the init_population() method, generating a population based on the specified number of individuals. The fitness function, a pivotal element, selects the best parents and guides their breeding to ensure optimal progression. The fitness function is shown below:
def fitness(chrom, chromosome_size):
q = 0
for i1 in range(chromosome_size):
tmp = i1 - chrom[i1]
for i2 in range(i1+1, chromosome_size):
q += (tmp == (i2 - chrom[i2]))
for i1 in range(chromosome_size):
tmp = i1 + chrom[i1]
for i2 in range(i1+1, chromosome_size):
q += (tmp == (i2 + chrom[i2]))
return 1/(q+0.001)
The fitness() function determines the fitness score by checking for collisions between queens. A lower collision count results in a higher fitness score, facilitating the selection of superior chromosomes.
The GA process selects parents with higher fitness scores for breeding, while those with lower scores are excluded from the next cycle. The line if ft[-1] == 1000 checks if the last fitness score indicates convergence towards a solution. If true, the loop is interrupted, ensuring no further operations are performed.
TIP: After reaching the solution, it’s crucial to terminate the program to avoid unnecessary operations. A break statement effectively handles this, exiting the loop post-solution discovery.
The above figure illustrates the learning curve, where the fitness score remains at 0 for the initial epochs, dramatically increasing to 100 and beyond. The solution is typically reached after 70 epochs. For additional learning curves, run the program or check the “repo/images/learning_curve” directory. Post-training, the “fitness_curve_plot” and “n_queen_plot” methods visualize the learning curve and queen positions, respectively.
Conclusion and Questions
This article explored Python code blocks to solve the N-Queen problem. The code is adaptable for efficiency improvements or additional functionality. For questions or suggestions, please share them in the comments.
Consider the following questions:
- Can you suggest another problem that could be solved using a genetic algorithm?
- What are your thoughts on the coding process, an essential aspect of genetic algorithms?
In the next article, I will explore a more complex case beyond the N-Queen problem, requiring more iterations to find a solution. Stay tuned for more exciting developments.
Published via Towards AI
“`
