Genetic Algorithm Explained :

Everything you need to know About Genetic Algorithm .

10 min readOct 16, 2021

In This Article i will try to give you an Introduction to The Genetic Algorithm , and we will see how can we use it to solve some very complicated Problems .

Article Summary :

1. Genetic Algorithm Definition .
2. Genetic Algorithm PseudoCode .
3. essential Terms :
3.1. Population .
3.2. Chromosome .
3.3. Gene .
3.4. Encoding Methods .
3.5. Fitness Function .
3.6. Termination Criteria .
4. Genetic operators :
4.1. Selection .
4.2. CrossOver .
4.3. Mutation .
5. Applications :
5.1. Using Genetic Algorithm to Optimize a Mathematical Function .
5.2. Using Genetic Algorithm to Optimize a Neural Network .
5.3. Using Genetic Algorithm to Solve The Travelling Salesman Problem .
6. References .

1. Genetic Algorithm Definition :

Genetic algorithm (GA) is a metaheuristic inspired by the process of natural selection that belongs to the larger class of evolutionary algorithms (EA). Genetic algorithms are commonly used to generate high-quality solutions to optimization and search problems by relying on biologically inspired operators such as mutation, crossover and selection .

2. Genetic Algorithm PseudoCode :

3. Essential Terms :

3.1 Population :

A population is a group of individuals or Chromosomes and each individual is a candidate solution to The problem.

3.2 Chromosome :

A Chromosome is An individual that contains a set of parameters known as Genes (take a look at the figure above).

3.3 Gene :

A Chromosome Contains a list of Parameters , this parameters we call them genes (take a look at the figure above) .

3.4 Encoding Methods :

Binary Encoding : This is The most common method of encoding , where we represents a Chromosome with a String of bits (0 and 1) , this method used to solve problems like knapsack problem and Optimizing a Mathematical Functions (we will se an Example later) .

Value Encoding : represents a Chromosome as a set of values , for Example we can use this encoding to optimize a neural network , to find the best weights and biases for our network (we will see an Example later ).

Order Encoding : Each Chromosome represents a sequence of Elements , Used in Problems such as Travelling Salesman problem (we will see an Example later ).

3.5 Fitness Function :

A fitness function is a particular type of objective function which takes as input a candidate solution and outputs the quality of this solution, therefore the fitness function makes it possible to evaluate the candidate solutions .

3.6 Termination Criteria :

The Reproduction process is repeated until a termination condition has been reached , common terminating conditions are .

A solution is found that satisfies minimum criteria .
Fixed number of generations reached .
Allocated budget (computation time/money) reached .
Manual inspection .
Combinations of the above .

4. Genetic operators :

4.1 Selection :

Selection is the process of selecting parents to generate the Child we call it also offspring that will be a part of the next generation , There are several selection methods among the most used we have :

Elitism Selection : Elitism Selection Consists of Selecting Top K chromosomes to pass them To The Next Generation without making any any changes to them .
Roulette Wheel Selection : each parent is represented in The wheel with a portion depends on his Fitness Value , The Parent with the Best Fitness Value have the best chance to be selected .

Stochastic Universal Sampling Selection (SUS Selection) : Stochastic Universal Sampling is Very similar to Roulette Wheel , but in Sus Selection we use more than one Fixed Point .

Tournament Selection : The First Thing We do is we choose a Number K that represents The Tournament Pool Size , then We select K individuals from The Current Population and we put Them into the Pool , After This we Choose The Best Individual from our Pool (The Individual that have the best Fitness Value ) .

Rank Selection : when the problem is very close to converge , The individuals in our Population have a very close Fitness Value , if we use Roulette wheel , they will have the same probability to be selected , we need to represents our chromosomes in The Wheel Using Different Parameter , instead of Using The Fitness Value we will Use The Rank , so that the chromosomes that have a good ranking they will have a better chance to be selected .

4.2 CrossOver :

The crossing operation is the Process of reproduction of new chromosomes from the parent chromosomes (parents are selected from the old population Using A Selection Method ) , There are several crossing methods among the most used we have :

One Point Crossover : a random Point is chosen to be The CrossOver Point , then we fill the child with genes from both parents .

Multi Point Crossover : a random two Points are chosen to be The CrossOver Points , then we fill the child with genes from both parents .

Davis Order Crossover (OX1) : we Choose two random crossover points in the first parent and we copy that segment into the Child , then we fill the rest of genes in our child with the genes from the second Parent .

Uniform CrossOver : we flip a coin for each genes in our two parents to decide whether or not it’ll be included in the off-spring (Child ).

Whole Arithmetic Recombination : we use this two formula to forms our two children .

Child1 = α.x + (1-α).yChild2 = α.x + (1-α).y

Then we Choose The Best Child (The Child with The Best Fitness Value ).

4.3 Mutation :

the mutation can be defined as a small random modification of the chromosome, to obtain a new solution. It is used to maintain and introduce diversity in the genetic population and is generally applied with a low probability we call it P_m , There are several methods of mutation among the most used ones we have .

Bit flip Mutation : we select one or more random points (Bits) and flip them. This is used for binary encoded Genetic Algorithms .

Swap Mutation : we Choose two Point and we switch them .

Scramble Mutation : we choose a random segment in The Current Chromosome and we interchange the values .

Inversion Mutation : we choose a random segment in The Current Chromosome and we reverse The Order of the values .

5. Applications :

5.1 Using Genetic Algorithm to Optimize a Mathematical Function :

in This Example we will Use Genetic Algorithm to Optimize this Mathematical Function :

f(x) = x^2 +2x -1

but before going further we need to answer this questions :

Which Encoding Method we will use to encode our chromosomes ?

we will Use Binary Encoding .

what is The Fitness Function that we will use to evaluate our candidate Solutions ?

The Fitness Function in Our Case is The Same Function f .

which Selection Method we will use ?

we will use Elitism Selection Combined with Tournament Selection .

which CrossOver Method we will use ?

we will use the most simplest crossOver Method , which is One Point CrossOver .

which Mutation Method we will use ?

we used Binary Encoding to encode our chromosomes , this is why we will use Bit Flip Mutation .

which termination criteria will use ?

we will use The Number of generations as a termination criteria .

Implementation :

The Chromosomes are represented with this class :

The Population In Our Case is Represeted with this class :

The Genetic Algorithm is Represeted with This Class :

The Main class :

Genetic Algorithm gives as this result which very good , I intentionally choose a small population size, so we can see the steps, because the genetic algorithm is very fast to optimize this simple function that we have , if we use a large population size .

5.2 Using Genetic Algorithm to Optimize a Neural Network .

In This Example we’ll see how to optimize a neural network using Genetic Algorithm .

Training a neural network, is the process of finding the best weights and biases that will reduce the loss function, using an optimization algorithm such as gradient descent, in this example we are trying to replace the gradient descent algorithm with the genetic algorithm, instead of using gradient descent to update the weights and biases, we will use the genetic algorithm, the diagram below It accurately explains what we are trying to do.

illustration of the optimization process

This is our simple neural network, which only has a feed Forward function, it’s the only thing we need:

The chromosome in our case is represented by this class , that contains a list of candidate weights and biases ,and the fitness value of each chromosome is represented by the mean squared error :

The Population in our case is represented by this class (list of candidate weights and biases ) :

The Genetic Algorithm is represented by this class :

The Main Class contains this instructions :

This graph represent The Optimization process of the MSE (Mean Squared Error) by the genetic Algorithm :

5.3 Using Genetic Algorithm to Solve The Travelling Salesman Problem :

In This Example we will use The Genetic Algorithm to solve The travelling salesman problem (TSP) , which is an NP-hard problem in combinatorial optimization , we can represent the TSP with this Question :

“Given a list of cities and the distances between each pair of cities, what is the shortest possible route that visits each city exactly once and returns to the origin city?”

The Travelling Salesman can be expressed using This Formula , with T[i] is a candidate Trajectory to our Problem :

TSP Math Formula

but before going further we need to answer this questions :

What Would The Genes be in our case ?

the genes in our case are represented as Cities .

What Would The Chromosomes be in our case ?

The Chromosomes in our case are represented as Tours (candidate trajectories) .

What Would The Population be in our case ?

The Population In Our case is represented as a list of Tours .

Which Encoding Method will use to encode our chromosomes ?

we will Use Order Encoding , because we’re looking for a specific Order of cities that will give us The Shortest Path .

what is The Fitness Function that we will use to evaluate our candidate Solutions ?

The Fitness Function in Our Case is The function that calculate the Distance of candidate path , which is represented as bellow :

Fitness Function

with d(T[i] , T[j]) is the euclidean distance function , that give us the distance between the city number i and the city number j in The T trajectory , we can express this function using this formula :

Euclidean Distance Formula

which Selection Method will use ?

we will use Elitism Selection Combined with Tournament Selection , if chose 100 to be The Population Size , then we will take 20% of this size Using Elitism Selection and The Rest (80%) Using Tournament Selection .
which CrossOver Method will use ?

we will Use Davis Order CrossOver Method (OX1).

which Mutation Method will use ?

We used order coding to encode our own chromosomes, the most convenient method for mutation to use is Swap switch.