Genetic Algorithm
GA is a heuristic search technique to find the most relevant solutions or optimal solution for any given problem. This is inspired by Charles Darwin’s theory of natural evolution. By using this natural selection process, we can determine the possible set of solutions that can be used to solve any given problem. The output of any GA would be the fittest solution for the problem. All the possible solutions we obtain are called chromosomes. The fittest solution is obtained in 5 phases namely: Initial population, Fitness function, Selection, Crossover/reproduction, Mutation. Elitism (Which is explained in later part of the article) is another technique in GA which helps to save the best solution till the end.
Flowchart for this solution:
Let us understand the Genetic Algorithm in a better way considering an example:
Travelling Salesman problem:
This problem is to find the minimum distance a salesperson can travel on a search space/graph which represents cities. The salesman starts from one point and eventually returns to the same point by visiting all other cities.
E.g.: A — B — D — C — A
the main aim is to choose the combination such that all the distances between each node (A-B or B-D and so on) should be calculated and is optimal. The distance between each city is calculated using the Pythagoras theorem (as we are taking the cities on a graph with x & y coordinates).
Phases:
- Initial population: The process begins with a set of individuals which is called a Population. Each individual is a solution to the problem you want to solve. An individual is characterized by a set of parameters (variables) known as Genes. Genes are joined into a string to form a Chromosome (solution). In a genetic algorithm, the set of genes of an individual is represented using a string, in terms of an alphabet. Usually, binary values are used (a string of 1s and 0s). We say that we encode the genes in a chromosome.
All the routes are then considered as a population which in turn known as chromosomes as per this problem. If there are n number of cities then the number of the possible population would be n!.
2. Fitness function: This is a way of specifying the criteria for the ‘goodness’ of a given solution compared to others and to the problem being solved. For certain phases (crossover and mutation), the Probability of an individual i being selected for mating depends on its absolute fitness value compared to the absolute fitness values of the whole population.
Note: Sum of probabilities must be 1
As far as this example is considered, the distance between 2 cities has been calculated and added to the total path distance which is then reciprocated and saved as total path fitness. The output of this fitness is then sorted so that the lowest distance paths can be picked up.
3. Selection: Roulette wheel or Tournament selection processes can be used to select the chromosome for crossover as parents, which is a fitness proportionate selection (this is used as there is high Probability of selections, which picks useful results from fitness for reproduction).
Roulette Wheel: Repeatedly spin a one-armed roulette wheel, where the sizes of the holes reflect the selection probabilities. The best fittest values occupy more space on the wheel (therefore, chances of them getting selected are more).
Tournament selection: Probability of individuals being selected depends on Rank in population, Tournament size.
In this example, cumulative sum and cumulative percentages are calculated and the data frame is created with all possible values. Using a qualification criterion (fitness function), the best fit chromosomes are selected from the data frame discarding the remaining chromosomes.
4. Crossover: Crossover is used in this GA to generate children. There are conditions to pick the parents from the mating pool (using selection). Once the children are generated the fitness of them is evaluated. The child chromosomes also have the chance that they might get picked for crossover from the selection process (if they are fittest). There are many types of crossovers, few are listed below:
a. One point crossover
b. Multi-point crossover
c. Uniform crossover
d. Whole arithmetic recombination
e. Davis’ order crossover
Crossover is chosen because we are taking the vector values and playing around with indexes of the cities. Also, this crossover avoids duplication as this problem is all about salesmen traveling to each location for one time only. If I choose 1 point crossover, there are many chances a salesperson travels to the same location for more than 1 time.
5. Mutation: Mutation is used to mutate a chromosome. The mutation is a process of changing the position of genes in a chromosome so that the fitness of the new chromosomes is evaluated and saved. The types of mutation are listed below:
a. Bit flip mutation
b. Random resetting
c. Swap mutation
d. Scramble mutation
e. Inversion mutation
Swap mutation is used to solve TSP because in other processes any location can be dropped which is against the rules of TSP. Therefore, this simple swap mutation process is used to simply swap the values in indexes
Elitism: This process is to carry out the best routes or population to next-generation ensuring that the top-ranked population still persists. A practical variant of the general process of constructing a new population is to allow the best organism(s) from the current generation to carry over to the next, unaltered. This strategy is known as elitist selection and guarantees that the solution quality obtained by the GA will not decrease from one generation to the next.
Application Areas of Genetic Algorithm
- Image Processing & Recognition
- Optimization Problem Solving
- DNA Analysis
- Neural Network
Citation:
http://www.eecg.toronto.edu/~jayar/courses/aps105S/quizzes/quiz2b/node4.html
https://en.wikipedia.org/wiki/Mating_pool
https://en.wikipedia.org/wiki/Genetic_algorithm#Elitism
