Genetic Algorithm

Introduction:

The field of genetics is seeing a lot of attention in AI these days. We have seen breakthroughs happening in scientific research lately but most people cannot make head or tails of how to even begin understanding this field.

A genetic algorithm is a search heuristic that is inspired by Charles Darwin’s theory of natural evolution. This algorithm reflects the process of natural selection where the fittest individuals are selected for reproduction in order to produce offspring of the next generation.

Genetic algorithm is a heuristic, derivative-free optimization technique involving iterative search procedures which reflects the process of natural selection where the fittest individuals are selected for reproduction in order to produce offspring of the next generation.

It basically uses biologically inspired operators such as mutation , crossover and selection.

It belongs to the larger class of evolutionary algorithms.

Components of Genetic Algorithm:

  1. Initial Population
  2. Fitness Function
  3. Selection
  4. Crossover
  5. Mutation

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 (string of 1s and 0s). We say that we encode the genes in a chromosome.

Fitness and Objective Function:

The fitness function determines how fit an individual is (the ability of an individual to compete with other individuals). It gives a fitness score to each individual. The probability that an individual will be selected for reproduction is based on its fitness score.

The objective function is the function being optimized while the fitness function is what is used to guide the optimization.

A fitness function is a particular type of objective function that is designed to guide the genetic algorithm towards optimal solution.

Selection:

The Focus of the selection step is to select the fittest individuals to pass their genes to the next generation.

Two pairs of individuals(parents) are selected on their fitness scores.

Individuals with high fitness have more chance to be selected for reproduction.

Various types of selection

Elitism:

Elitism involves copying a small proportion of the fittest candidates, unchanged, into the next generation.

This strategy is known as elitist selection and guarantees that the solution quality obtained by the genetic algorithm will not decrease from one generation to the next.

Example of Elitism

Roulette Wheel Selection:

Here the better individual gets higher chance and chances are proportional to the fitness.

Roulette Technique:

  1. Each individual is assigned to a part of the wheel based on its fitness.
  2. Spin the wheel k times to select the best individuals.
  3. Fitness individual has the largest share of the roulette wheel and weakest individual has the smallest share of the roulette wheel.
Example of Roulette Selection

Tournament Selection:

Several tournaments are held between the individuals of current generation.

A group of n(n is the tournament size) individuals are chosen randomly from the current population and the one with the best fitness is selected.

Example of Tournament Selection

Crossover:

Crossover, also called recombination, is a genetic operator used to combine the genetic information of two parents to generate new offspring.

Cr is called the crossover rate. If the population size is 10 and Cr is 0.8; then 80% that is, 8 offspring(new chromosomes) are made by crossover.

If it is 0%, crossover operation will not performed at all(direct copy).

Example of Crossover

Mutation:

Mutation is a genetic operator used to maintain genetic diversity from one generation of a population of genetic algorithm chromosomes to the next.

Mutation alters one or more gene values in a chromosome from its initial state.

Example of Mutation

Flow Chart of Genetic Algorithm Process:

Implementation of Genetic Algorithm Using Python:

  1. Importing the Libraries:

2. Initializing the map procedure:

Procedure and the print function for printing the population

3. Initializing the Map function:

4. Initializing the map using complex function in order to get better output.

5. defining two function one for creating new population and another one for calculating the fitness of the individuals:

6. Defining the crossover function:

7. Defining the mutation function:

8. Defining function for generating a new member and scoring the population:

9. Defining the function pick mate for selecting the individual on the basis of there scores

10. Defining the main function and function for plotting the result:

11. Visualizing the plots:

The source code of this is available on my github repository.

Closing Note: I hope this blog will help you in learning genetic algorithm in a better way.

I wanted to thank my mentor Mr Rajdeep Chatterjee for guiding me through out this project and for providing me all the necessary resources required to carry out this project smoothly. It was a great experience working with such a great personality. Anyone wanted to know more about my mentor can visit his linkedin profile. If anyone wanted to know about his research work can visit his Research Gate profile.

For any queries related to my project contact me over my email id: powerakash8@gmail.com

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store