Genetic Algorithm

September 21, 2017 Author: virendra
Print Friendly, PDF & Email

Genetic algorithms are a part of evolutionary computing, which is a rapidly growing area of artificial intelligence. Nature has always been a great source of inspiration to all mankind. Genetic Algorithms (GAs) are search based algorithms based on the concepts of natural selection and genetics. GAs is a subset of a much larger branch of computation known as Evolutionary Computation

Genetic algorithms are inspired by Darwin’s theory about evolution. Simply said, solution to a problem solved by genetic algorithms is evolved. Genetic Algorithms are a family of computational models inspired by evolution These algorithms encode a potential solution to a specific problem on a simple chromosomelike data structure and apply recombination operators to these structures so as to preserve critical information Genetic algorithms are often viewed as function optimizers although the range of problems to which genetic algorithms have been applied is quite broad.



Definition of Genetic algorithm

Genetic Algorithms are heuristic search approaches that are applicable to a wide range of optimization problems. This flexibility makes them attractive for many optimization problems in practice. Evolution is the basis of Genetic Algorithms. The current variety and success of species is a good reason for believing in the power of evolution. Species are able to adapt to their environment. They have developed to complex structures that allow the survival in different kinds of environments. Mating and getting offspring to evolve belong to the main principles of the success of evolution. These are good reasons for adapting evolutionary principles to solving optimization problems.

Genetic Algorithms are heuristic search approaches that are applicable to a wide range of optimization problems. This flexibility makes them attractive for many optimization problems in practice. Evolution is the basis of Genetic Algorithms. The current variety and success of species is a good reason for believing in the power of evolution. Species are able to adapt to their environment. They have developed to complex structures that allow the survival in different kinds of environments. Mating and getting offspring to evolve belong to the main principles of the success of evolution. These are good reasons for adapting evolutionary principles to solving optimization problems. Genetic operators produce new solutions in the chosen representation and allow the walk in solution space. The coding of the solution as representation, which is subject to the evolutionary process, is called genotype or chromosome.

Genetic-Algorithm-Tree-Basic-steps-of-GA-selection-crossover-and-mutation

figure 1 genetic algorithm

Outline of the Basic Genetic Algorithm

  1. [Start]Generate random population of n chromosomes (suitable solutions for the problem)
  2. [Fitness]Evaluate the fitness f(x) of each chromosome x in the population
  3. [New Population]Create a new population by repeating following steps until the new population is complete
    1. [Selection]Select two parent chromosomes from a population according to their fitness (the better fitness, the bigger chance to be selected)
    2. [Crossover]With a crossover probability cross over the parents to form a new offspring (children). If no crossover was performed, offspring is an exact copy of parents.
    3. [Mutation]With a mutation probability mutate new offspring at each locus (position in chromosome).
    4. [Accepting]Place new offspring in a new population
  1. [Replace] Use new generated population for a further run of algorithm
  2. [Test]If the end condition is satisfied, stop, and return the best solution in current population
  3. [Loop] Go to step 2

Operators of Genetic Algorithm

From the above outlines the crossover and mutation are the most important part of the genetic algorithm. The performance is influenced mainly by these two operators. Before we can explain more about crossover and mutation, some information about chromosomes will be given:



Encoding of a Chromosome

The chromosome should in some way contain information about solution which it represents. The most used way of encoding is a binary string. The chromosome then could look like this:

Chromosome 1 1101100100110110
Chromosome 2 1101111000011110

Each chromosome has one binary string. Each bit in this string can represent some characteristic of the solution.

Of course, there are many other ways of encoding. This depends mainly on the solved problem. For example, one can encode directly integer or real numbers; sometimes it is useful to encode some permutations and so on.

Crossover

After we have decided what encoding we will use, we can make a step to crossover. Crossover selects genes from parent chromosomes and creates a new offspring. The simplest way how to do this is to choose randomly some crossover point and everything before this point copy from a first parent and then everything after a crossover point copy from the second parent.

Crossover can then look like this (| is the crossover point):

Chromosome 1 11011 | 00100110110
Chromosome 2 11011 | 11000011110
Offspring 1 11011 | 11000011110
Offspring 2 11011 | 00100110110

There are other ways how to make crossover, for example we can choose more crossover points. Crossover can be rather complicated and very depends on encoding of the encoding of chromosome. Specific crossover made for a specific problem can improve performance of the genetic algorithm.



Mutation

After a crossover is performed, mutation takes place. This is to prevent falling all solutions in population into a local optimum of solved problem. Mutation changes randomly the new offspring. For binary encoding we can switch a few randomly chosen bits from 1 to 0 or from 0 to 1. Mutation can then be following:

Original Offspring 1 1101111000011110
Original Offspring 2 1101100100110110
Mutated Offspring 1 1100111000011110
Mutated Offspring 2 1101101100110110

The mutation depends on the encoding as well as the crossover. For example when we are encoding permutations, mutation could be exchanging two genes.

Algorithm 1 shows the pseudocode of the basic Genetic Algorithm, which can serve as blueprint for many related approaches. At the beginning, a set of solutions, which is denoted as population, is initialized. This initialization is recommended to randomly cover the whole solution space or to model and incorporate expert knowledge. The representation determines the initialization process. For bit string representations a random combination of zeros and ones is reasonable, for example the initial random chromosome 1001001001 as a typical bit string of length 10. The main generational loop of the Genetic Algorithm generates new offspring candidate solutions with crossover and mutation until the population is complete:

ALGORITHM 1: BASIC GENETIC ALGORITHM
1: initialize population

2: repeat

  1. repeat
  2. crossover
  3. mutation
  4. phenotype mapping
  5. fitness computation
  6. until population complete

3: selection of parental population

4: until termination condition

References

[1] O. Kramer, “Genetic Algorithm Essentials, Studies in Computational Intelligence”, Springer International Publishing AG 2017

[2] Carr, Jenna, “An introduction to genetic algorithms”, Senior Project, 1-40. May 16, 2014

[3] “Introduction to Genetic Algorithms”, available online at: http://www.obitko.com/tutorials/genetic-algorithms/index.php

[4] Whitley, Darrell, “A genetic algorithm tutorial”, Statistics and computing 4.2 (1994): pp. 65-85.

 

14 Comments

Leave a Reply

Your email address will not be published. Required fields are marked *

Insert math as
Block
Inline
Additional settings
Formula color
Text color
#333333
Type math using LaTeX
Preview
\({}\)
Nothing to preview
Insert