Genetic Algorithms: Based on the ideas of natural selection and genetics.

7 min readMay 31, 2021

Nature has always been a great source of inspiration to all mankind.

Genetic algorithms are stochastic search algorithms inspired by the principles of Genetics and Natural Selection. Genetic algorithms are a subset of a larger branch of computation known as Evolutionary Computation. Genetic algorithms are used to find good-quality solutions for optimization and search problems.

In Genetic algorithms, we have a set of possible solutions to the given problem. These solutions then go through the process of crossovers and mutations (like in natural genetics), produce new children, and this process is repeated over various generations. Each solution (from Population) is assigned a fitness score (based on objective function value) and the individuals with high scores are given a higher chance to mate and yield more “fitter” individuals.

In simple words, they simulate the theory of “survival of the fittest” among individuals of consecutive generations for solving a problem.

The Reason: Why Genetic algorithms are needed

Some of the reasons why Genetic algorithms are used are as follows −

Failure of Gradient Based Methods
Gradient based methods work by starting at a random point and by moving in the opposite direction of the gradient, till we reach the local/global minimum. This method works well for single-peaked objective functions such as the cost function in linear regression. But, in most situations, we have very complex objective functions, which may have many peaks and many valleys, which causes such methods to fail, as they suffer from an inherent tendency of getting stuck at the local minima as shown in the following figure.

2. Genetic Algorithms can deliver a “good-enough” solution “fast-enough”. Some difficult problems like the Travelling Salesperson Problem (TSP), have real-world applications like GPS Navigation system. Imagine you are using your GPS, and it takes hours to compute the “optimal” path from the source to the destination. Delay in such applications is not acceptable and therefore a “good-enough” solution, which is delivered “fast-enough” is what is required.

Basic Terminologies

Before beginning a discussion on Genetic Algorithms, it is essential to be familiar with some basic terminologies which we are going to use during this tutorial.

Population − It is a subset of all the possible solutions to the given problem.

Chromosomes − A chromosome is one such solution to the given problem.

Gene − A gene is one element position of a chromosome.

Allele − It is the value of a gene for a particular chromosome.

Basic Structure

Five phases are considered in a genetic algorithm.

Initial population (Initialization)
Fitness function
Selection
Crossover
Mutation

Let us understand these phases by an example

I am taking the example of the famous Knapsack problem

Problem Statement: Suppose you are going to market during the Covid situation. Some precautions are required before going outside like a mask, sanitizer, etc. . The only constraint is that you can choose at max 3 items from the list. Each item has its own “Survival Points” (mentioned in the table). The objective is to maximize the survival points.

**Table 1:** Image is just for example purpose

Phase 1: Initial Population

The process begins with a set of individuals (candidate solutions) which is called a Population. Each individual is a solution to the problem you want to solve.

Suppose we have 2 possible solutions for this problem-

Solution S1 Chromosome : [110001] {Binary representation, refer Table 1}

Solution S2 Chromosome : [011100] {Binary representation}

Phase 2: Fitness Function

The fitness function determines how fit an individual is and assigned a fitness score to each individual. In this example fitness score is the total survival points.

Let’s calculate the fitness score for our two chromosomes S1 and S2.

For Chromosome S1

For Chromosome S2

Fitness Score:
S1: 37 Survival Points
S2: 28 Survival Points

— Chromosome S1 is more fitter than chromosome S2.

Phase 3: Selection

The idea of the selection phase is to choose the fittest individuals from the population and let them pass their genes to the next generation. Two individuals (parents) are selected. Individuals with high fitness have more chances to be selected for reproduction.

There are many methods to select the chromosomes such as

1. Roulette Wheel Selection
2. Rank Selection
3. Steady State Selection
4. Tournament Selection
5. Elitism Selection
6. Boltzmann Selection
7. Random Selection, etc.

For simplicity, we are taking random selection in our example. Say, S1 and S2 are selected for crossover.

Phase 4: Crossover

Crossover is nothing but reproduction. This step combines the genetic information of two parents to generate new offspring. For each pair of parents to be mated, a crossover point is chosen at random from within the genes.

In our example, consider the crossover point to be 3 as shown below.

Offspring are created by exchanging the genes of parents among themselves until the crossover point is reached.

In our example,

The new offspring A1 and A2 are added to the population.

Phase 5: Mutation

In real world, are the children have the exact characteristics or traits as their parents? The answer is No. There are some unique traits/mutations present in the children’s chromosomes.

These changes are termed as mutations.

Mutation occurs to maintain diversity within the population and prevent premature convergence. Hence GA can come to a better solution by using mutation.

Termination

As Genetic algorithms follow an iterative process, this process needs to be terminated at some stage. We usually want a termination condition such that our solution is close to the optimal or “good-enough”, at the end of the run.

We can use any one or a combination of the following termination conditions−

When there has been no improvement in the population from the last X iterations.
When we reach an absolute number of generations.
when an individual solution reaches a certain prespecified level of fitness.

Advantages and Limitations of Genetic Algorithms:

Advantages:

1. Genetic algorithms algorithms do not deviate easily in the presence of noise.
2. Parallelism: Multiple Genetic algorithms can run together using the same CPU.
3. Does not require any derivative information (which may not be available for many real-world problems).
4. Genetic algorithms can optimizes both continuous and discrete functions and also multi-objective problems.
5. Provides a list of “good” possible solutions, not just a single solution.
6. At every generation there is an answer to the problem, which gets better with each generation.

Limitations:

1.The “better” solution is only in comparison to other solutions in population. As a result, the stop criterion is not clear in every problem.
2. The fitness function identification is a limitation.
3. There is a limitation of selecting the parameters such as crossover, mutation probability, size of population etc.
4. Genetic algorithms are not suited for simple problems specially for which derivative information is available.
5. Fitness value might be computationally expensive for some problems.
6. Being stochastic, there are no guarantees on the optimality of the solution.

Some applications where Genetic algorithms are used:

Optimization Problem: In optimization problems such as job scheduling, TSP, sound quality optimization Genetic algorithms are widely used.
Machine Learning: Genetic algorithms have been used in feature selection and also to solve problems related to classification, prediction, etc.
List of other use cases : Genetic algorithms applications