What is Genetic Algorithm?

Akshat Chaturvedi
Last Updated: May 13, 2022

Introduction

The Genetic Algorithm is an optimization algorithm. With the help of the Genetic Algorithm, we find the best solution from many different possible answers.

 

The idea of genetic algorithm is based on the biological evolution in real-world species. We can easily solve a complex problem having a high search space by using the genetic algorithm.

 

To optimize the result with the number of generations, we send only the fittest individuals to the next subsequent generations, same as the theory of evolution, which states “Survival of the Fittest.”

 

Source: www.growthbusiness.co.uk

 

Working of the Genetic Algorithm

The Genetic Algorithm is a Heuristic Search algorithm that we use to find the optimal solution from the search space and optimization problems.

 

Step 1

The first step is to get the initial population of possible solutions. The user can provide the population. The population must have rich diversity; the more diverse the population is, the solution is better.

 

Step 2

Now the second step is to calculate the fitness of the population. The function which gives the best and stable output based on the inputs is known as the fitness function.

 

After calculating the fitness, we’ll select the best individuals/parents with the best fitness value according to the above-generated fitness function after calculating the fitness.

 

Step 3

The next step is Crossover, where we crossover the two best parents that we selected in the above step; after crossover, the mutation in the population will happen, and a new generation will be evolved.

 

The idea here is to generate a new population with better fitness than the previous population.

 

Step 4

The above three steps are repeated until a convergence point is reached. At this point, we have the fittest possible population or the best optimal solution for the problem entered.

 

Python Demonstration

CODE

# Importing necessary libraries
import numpy as np
import matplotlib.pyplot as plt
 
# Defining the range of the plot
x1 = [-100, 100]
x2 = [-100, 100]
 
# This list will store the population
populations = []
def generatePopulation(features, size = 1000):
     
   initial = []
     
   for _ in range(size):
       entity = []
       for feature in features:
           
           val = np.random.randint(*feature)
           entity.append(val)
       initial.append(entity)
     
   return np.array(initial)
 
virusArray = np.array([5, 5])
 
# size 100 implies that only 100 individuals will survive
def fitness(populations, virusArray, size = 100):
     
   scores = []
     
   for index, entity in enumerate(populations): 
       score = np.sum((entity-virus)**2)
       scores.append((score, index))
     
   scores = sorted(scores)[:size]
     
   return np.array(scores)[:, 1]      
     
def reduction(populations, virusArray, size = 100):
     
   fitIndividuals = fitness(populations, virusArray, size) 
 
   new_pop = []
     
   for item in fitIndividuals:
       new_pop.append(populations[item])
         
   return np.array(new_pop)
 
def crossMutation(populations, size = 1000):
     
   new_pop = []
     
   for _ in range(size):
       p = populations[np.random.randint(0, len(populations))]
       m = populations[np.random.randint(0, len(populations))]
     
       entity = []
       entity.append(*p[:len(p)//2])
       entity.append(*m[len(m)//2:])
         
       new_pop.append(entity)
     
   return np.array(new_pop)
def mutations(populations):
     
   return populations + np.random.randint(-10, 10, 2000).reshape(1000, 2)
 
 
# the complete cycle of the above steps
populations = generatePopulation([x1, x2], 1000)
def cycle(populations, virusArray, generations): 
   # changing value of generations will give more fitter next generation
   for _ in range(generations):
       populations = reduction(populations, virusArray, 100)
       populations = crossMutation(populations, 1000)
       populations = mutations(populations)
         
   return populations
def plotGraph(populations, virusArray):
   plt.xlim((-100, 100))
   plt.ylim((-100, 100))
   plt.scatter(populations[:, 0], populations[:, 1], c ='green', s = 12)
   plt.scatter(virusArray[0], virusArray[1], c ='red', s = 60) 
 
populations = cycle(populations, virusArray, 0)
plotGraph(populations, virusArray)

 

OUTPUT

  • Plot for the First Generation-

 

  • Plot for the Second Generation-

 

  • Plot for the Third Generation-

 

  • Plot for the Fourth Generation-

 

Frequently Asked Questions

Q1. What is the core idea behind the Genetic Algorithm?

The main idea of the genetic algorithm is based on the biological evolution in real-world species. Like how species evolve and get better in the real world, we can also optimize our solution with many iterations.

 

Q2. What are the steps in the Genetic Algorithm?

The following are the steps followed in the genetic algorithm:

  1. Feed the initial population,
  2. Find the best fitness function,
  3. Select the best parents with the fitness function,
  4. Crossover between parents,
  5. Mutation in the new species,
  6. Stop if we reach the convergence point; otherwise, repeat the above steps.

 

Q3. What are the functions needed to implement the Genetic Algorithm in Python?

The main functions that we have used to implement the Genetic algorithm are:

  1. generatePopulation: To generate a set random population.
  2. reduction: To reduce the size of the population, keeping only the best 100 ones.
  3. crossMutation: To crossover between the best parents.

 

Key Takeaways

Congrats on reaching the end. This blog explored one fascinating algorithm with a wide range of use-cases in the real world. I hope you clearly understood the topic. Check out this informative article on Reinforcement Learning.

 

Check out this link if you are a Machine Learning enthusiast or want to brush up your knowledge with ML blogs.


If you are preparing for the upcoming Campus Placements, don’t worry. Coding Ninjas has your back. Visit this link for a carefully crafted and designed course on-campus placements and interview preparation.

Was this article helpful ?
1 upvote

Comments

No comments yet

Be the first to share what you think