Overview
Genetic Algorithm (GA) is a metahuristic algorithm inspired by the process of natural selection, which is an evolutionary algorithm (EA). It is mostly used for optimization and search problems. During the course of Bio-Inspired Computing, I could solve a search problem by GA. The algorithm consists of different steps based on what is happening in Gens of biological creatures. Firstly we have to model the problem, chose a genetic representation, then design a fitness function, after that, build a population, next choose a selection, recombination, and mutation sequentially. Finally, devise a termination condition and analysis procedure. According to the stochastic nature of GA, if we select the fitness function more suitable, it will lead to a better answer more quickly.
Problem Definition
Suppose there are some sports competitions held in the university for students. Each student can participate in one or more competitions. If it is decided to hold m matches simultaneously on the first day of the competition, we want to write a program using the genetic algorithm that receives a graph in which each vertex represents a match, and the edge between both vertices indicates the presence of at least one interested student. To participate in both competitions, let’s specify these m competitions.
Solution
In the following, I will provide you the general concepts based on my source code on GitHub, refer to the last header. Everything is clear, just follow the source code beside what I explain in here. :)
- The adjacancy graph represents the model of the problem, discrete binary representation. The first row of
input.txt file is m and the rest of the lines define whether there is a vertex between i and j edges or not. The input.txt would be passed into load_input function to extract adjacancy graph and m.
- After that, the
generation function generates chromosomes ramdomly, our goal is to find the most suitable chromosome (solution).
- Next we have to assign an objective value via
obj_func function.
- Then we deploy roulette wheel for the selection step, chose chromosomes and do generation. It is executed by the
roulette_wheel function.
- After that, we need crossover to produce one of the most important pillars of evolution, diversity. It is done by the
crossover function.
- Later, mutation must be done. Mutation also leads to more diversity by taking the chromosomes away from the local minima points for having broader range of chromosomes.
- Finally, the main routine,
solution function, calculates the best chromosome as answer.
In the following I will demonstrate how fast the algorithm finds the solution, it is done by 200 chromosomes, 25% crossover rate, 10% mutation rate, and 700 iteration.
There may be some errors in the above parameters’ values, but nothing important.
Source Code
The source code is uploaded to genetic_algorithm_case_study repository on GitHub. Email me if you have question.