Author(s): Hossein Chegini
Originally published on Towards AI.
“A 100-queen solution”…image from ‘repo/images/solution’
code check
In the previous introduction, I provided a detailed description of the basic steps involved in training a genetic algorithm (GA). I discussed important concepts such as mutation, genes, chromosomes, and genetic populations, and presented a case study on solving the n-queen problem using GA.
After publication of the article, I proceeded to create a repository and convert my previously written Matlab code into Python code. In this article, my focus is on explaining the different components of the repository and how the main file is structured to set up a GA scenario and find the optimal solution. you can find the repo Here.
The main file (n_queen_solver.py) serves as the entry point to install the GA model and start the training process. It prompts the user to provide the required parameters that are important to configure the GA model. These parameters include:
- Chromium size or chessboard size: The size of a chessboard, indicating the number of queens and the dimensions of the board.
- Population size: The number of chromosomes in the population represents the number of candidate solutions.
- Epoch: The number of iterations or generations for which the GA model will be trained.
parser = argparse.ArgumentParser(description='Computation of the GA model for finding 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 population of the chromosomes')
parser.add_argument('epoches', type=int, help='The nmber of iterations to traing the GA model')
args = parser.parse_args()
After receiving the parameters, the next block of code is responsible for initializing the population. The ‘init_population()’ method generates a population based on the specified number of individuals, using the encoding described in the previous article. This returns the initial population to the main method of the file.
The calculation of the fitness function and fitness score plays an important role in selecting the best parents and guiding their reproduction to ensure that the program progresses on the optimal path. For simplicity and clarity of this implementation, I have chosen a straightforward fitness method. The following code block demonstrates the ‘fitness()’ method:
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 = q + (tmp == (i2 - chrom(i2)))
for i1 in range(chromosome_size):
tmp = i1 + chrom(i1)
for i2 in range(i1+1,chromosome_size):
q = q + (tmp == (i2 + chrom(i2)))
return 1/(q+0.001)
In this block ‘fitness()’ received an individual chromosome and its size as input parameters and returned its fitness score. In the given code block, the fitness function checks whether two queens in a chromosome are crossing each other or not. If two queens are found crossing, the variable ‘q’ is increased by one. The purpose of this test is to evaluate the fitness of the chromosome based on the number of queen collisions.
The line ‘1 / (q+0.001)’ represents the fitness score based on ‘q’. Using the inverse of the ‘q + 0.001’ value, the fitness score will be higher for chromosomes with fewer queen collisions (ie, lower values of ‘q’). The addition of ‘0.001’ is to avoid division by zero.
Fitness scores are used to assess the quality of each chromosome in a population. The higher the fitness score, the better the performance of the chromosome. In case a fitness score of 1000 is reached, it indicates that the solution has been found, and the program can terminate without further operations.
def train_population(population,epoches,chromosome_size):
num_best_parents = 2
ft = ()
success_booelan = False
population_size = len(population)
for i1 in tqdm(range(epoches)): # 1 should be epoches later
fitness_score = ()
for i2 in range(population_size):
fitness_score.append(fitness(population(i2),chromosome_size)) #fitness score initialisation
ft.append(sum(fitness_score)/population_size)
pop = np.concatenate((population, np.expand_dims(fitness_score, axis=1)), axis=1)
sorted_indices = np.argsort(pop(:, -1))
pop_sorted = pop(sorted_indices)
pop = pop_sorted(:, :-1)
best_parents_muted = ()
best_parents = pop(-num_best_parents:)
best_parents_muted = (mutation(best_parents(i), chromosome_size) for i in range(num_best_parents))
pop(0:num_best_parents) = best_parents_muted
population = pop
if ft(-1) == 1000: # this should be calculated accurately. In each case the model might pass the potimum solution, so whenever it is touching the solution's score we should stop the training
print('Woowww, the model could find the solution!!')
print('Here is an example of a solution : ',population(-1))
success_booelan = True
break
return population, ft, success_booelan
Genetic algorithm (GA) employs a selection process to choose parents with higher fitness scores for reproduction through mutation or crossover. The resulting offspring are added to the population, while chromosomes with low fitness scores are excluded from the next training round. The line ‘if ft(-1) == 1000’ checks if the latest fitness score indicates convergence to a solution. If the condition is true, the loop breaks, and the method terminates, making way for the execution of subsequent blocks.”
Tip: After reaching a solution or finding a global optimum of the solution space, it is possible for the program to continue executing operations. A break statement is used to ensure that the program terminates after finding the best fitness score. The break statement exits the loop and ensures that no further operations are performed.
In the above figure, we see the step-wise behavior of the learning curve. The program remains at a fitness score of 0 for the first 28 epochs and then suddenly reaches a fitness score of 100. During a normal run, the solution is reached after 70 epochs, but there is a brief period where the program gets stuck at a fitness score of 600. You can run the program to generate additional learning curves or check the “repo/images/learning_curves” directory for existing curves. After training the model, two additional methods, namely “fitness_curve_plot” and “n_queens_plot” are called to display the learning curve and visualize the positions of the queens on the chessboard.
Conclusions and Questions
Various blocks of Python code for solving the n-queens problem are presented in this article. The code can be modified and extended in various ways to add additional capabilities to improve efficiency or find solutions. If you have any questions or suggestions about the code repository, feel free to share them in the comments.
Additionally, I invite you to consider the following questions and provide your insights:
- Can you propose any other problems that can be solved using genetic algorithms?
- Please share your views on the encoding process, which is an important aspect of genetic algorithms.
In the next article, I plan to explore a more challenging case that goes beyond the n-queen problem and may require more iterations to find the solution. Stay tuned for more exciting developments.
Published via Towards AI
