What is Genetic Algorithm? (A Simple and Detailed Explanation)

Hello guys, I would be happy to give you a clear explanation about the concept of Genetic Algorithm. And this is very interesting because scientists are kind of succeeding in breaching the gab between biology and artificial intelligence.

I would explain the concept in two ways: Simple and clear non-technical overview Some technical details (if you would like to go further!)

You could stop after the first part if you are not a tech pro, but it’s alright to take up challenges from time to time.

We would cover the following:

  1. Foundation of Genetic Algorithm
  2. What is Genetic Algorithm?
  3. Why Genetic Algorithm
  4. Phases in Genetic Algorithm
  5. Concept of Heuristics
  6. The Simplified Algorithm
  7. Summary
  8. Final Notes

 

 

1. Introduction to Genetic Algorithms (Who did it first?)

Just like you know, the field of technology had made great strides by copying from creation. So you see great inventions actually existed in nature all the while. Take a few examples:

  • Airplanes wings design: existed naturally in birds
  • Air Conditioning Technology: used by termites
  • Antifreeze: existed in some microscopic plants
  • Underwater Breathing technology: used by water beetles
  • Clocks: Many living things keep time naturally
  • Compasses: Used naturally by migrating birds
  • Jet Propulsion: Naturally in squid

Other are Sonar, lighting, submarines, incubator, electricity and more. For an exhaustive list, you could read chapter 12(Who did it First) of the book ‘Creation‘, published by Jehovah’s Witnesses.

The same principle applies to generic algorithm. It is an attempt to mimic the way natural selection occurs  in living things. But what exactly is Genetic Algorithm?

 

 

2. What is Genetic Algorithm?

Genetic algorithm is a procedure used in the field of Computer Science and operations research to solve problems of optimization copying the process of natural selection. Genetic Algorithm attempts to generating the best solution by employing operations such as mutation, cross-over and selection.
So the objective is the start with a very large population (or space) and then gradually reduce the size until you have only the best (kind of survival of the fittest)

 

3. Why Genetic Algorithm?

Genetic algorithm tends to play the same role as Artificial Intelligence. But Genetic Algorithm is sometimes considered to be more robust than AI. This is because, unlike conventional AI systems, GA would adjust on changing inputs and would also be able to handle noisy or fuzzy input. Additionally, GE is able to handle complex problems better.

 

 

4. Phases in Genetic Algorithm

Just as was mentioned, GE begins with a large population and gradually reduces it using some heuristics until only the best is left. So let’s look at the phases

 

(a) Initial Population

The process starts with a set of individuals known as the Population. Each individual member of the population represents the solution to the problem that need to be solved. This is the starting point. Each individual is associated with parameters known as Genes which are joined together into a string to form a Chromosome. The set of genes of a particular individual is represented using a string (these set of string represent the chromosome. This is illustrated in the figure below.

Figure 1: Genes, Chromosomes and Population

 

 

(b) Fitness Function

The fitness function is the relation that determines how fit an individual member of the population is. There is a fitness score associated with each individual. The more fit an individual is, then the higher the fitness score or vice versa. And the higher the fitness score, the higher the probability that individual will be selected for reproduction to the next generation.

 

(c) Selection

This is an idea of deciding which member of the existing generation is selected to breed the new generation and this is based on the fitness of that individual. The more fit the individual, the more likely it would be selected. During the selection process, two individuals are selected to serve as “parents” to be used to produce the next generation.

 

(d) Crossover

Crossover is also called recombination. It is an operation of merging the genetic information from the parents (father and mother) to produce new offspring.
This is illustrated in Figure 2. From the figure, we can see that some of the genes ‘crosses-over’ to produce new set of genes.

Figure 2: Crossover

 

 

(e) Mutation

Mutation just like crossover is a genetic operation. In the case of mutation, the arrangement of the genes in the chromosome kind of alters to produce a totally new chromosome. This happens with very low probability. Evolutionist tent to capitalize on mutation to explain how species evolve into now species. But this is not based on any scientific law.

 

(f) Termination

Just as you know, an algorithm terminates at some point. This process is also called convergence. So the algorithm repeats until certain termination conditions is reached where the offspring is a new generation is not much different from the previous. At this point not much changes occur and this is called termination.

 

5. Concept of Heuristics

I would like to mention the concept of heuristics as it relates to genetic algorithms. Heuristics sometimes is called ‘rule of thumb’. In case of generic algorithm, other rules  are employed to enhance the process and improve the quality of the final solution.

 

 

6. The Simplified Algorithm

I would like to write the simplified algorithm based on what we have discussed so far. This is given in the listing below.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
BEGIN
Generate the Initial Population
Compute Fitness
REPEAT
  Perform Selection
  Perform Crossover
  Perform Mutation
  Compute Fitness
UNTIL population converges
END

Listing 1: Simplified Genetic Algorithm

 

7 Summary

From this brief discussion, we can see that genetic algorithm claims that you can get a good solution (best members of population) by performing certain operations such as crossover and selection as well as applying certain heuristics. Research in Genetic algorithm is currently being carried out in different areas with the objective of creating better products/processes.

 

 

8. Final Notes

We could be sure that there is much dissimilarity in the understanding of what is know and genetic algorithm is natural world and the current trend of research in genetic algorithm. While we can be sure that there is not scientific proof that living organisms evolved into new ones,  the genetic algorithms can be applied today to solve scientific problems and more.

I’ll like to thank you for reading and you could let me know if this is been informative for you in the comment box below or the form to the left of this page.