Genetic Algorithms
By
SRUTHI S. NAMBIAR
SAISHREE SRINIVASAN
Background of Genetic
Algorithms(Gas)
• Genetic algorithms are based on the Darwinian principle
of survival of the fittest.
• They were invented by John Holland and presented in
his book "Adaptation in Natural and Artificial Systems"
from 1975 .
• In 1992 John Koza used genetic algorithm to evolve
programs to perform certain tasks. He called this method
“Genetic Programming”.
Genetic Algorithm
• Genetic Algorithm is an Evolutionary Algorithm.
• Genetic algorithms are so far the best and most
robust kind of evolutionary algorithms.
• Genetic Algorithms are search and optimization
techniques based on Darwin’s Principle of Natural
Selection
Basic Algorithm
begin
INITIALIZE population with random candidate solutions;
EVALUATE each candidate;
repeat
SELECT parents;
RECOMBINE pairs of parents;
MUTATE the resulting children;
EVALUATE children;
SELECT individuals for the next generation
until TERMINATION-CONDITION is satisfied
end
Flowchart of Genetic Algorithm
begin
Initialize
population
Flowchart of Genetic Algorithm
Initialization of Population
The randomly generated set or group of
individuals i.e. solutions is called the initial population .
• The population size depends on the nature of the
problem.
• The population is generated randomly, covering the
entire range of possible solutions (the search space)
Recombination
The process that determines which solutions are to be preserved
and allowed to reproduce and which ones deserve to die out is
called recombination.
• Identify the good solutions in a population.
• Make multiple copies of the good solutions.
• Eliminate bad solutions from the population so that
multiple copies of good solutions can be placed in
the population.
Fitness of a Solution
A fitness function quantifies the optimality of a
solution (chromosome) so that that particular
solution may be ranked against all the other
solutions.
• The fitness score is assigned to each
solution depending on how good it is at
solving the problem.
Encoding
The process of representing the solution in the
form of a string that conveys the necessary
Information is called encoding.
• Binary Encoding
• Permutation Encoding
• Value Encoding
• Tree Encoding
Selection
The process of selecting individuals from the population to become parents
on whom operations are performed to get a new child (solution) is called
selection.
• Roulette Wheel Selection
• Rank Selection
• Elitism
• Tournament Selection
• Generational selection
Crossover
It is the process in which two chromosomes (strings) combine
their genetic material (bits) to produce a new offspring which
possesses both their characteristics.
• Single Point Crossover
• Two point crossover
• Uniform crossover
• Arithmetic crossover
Mutation
It is the process by which a string is deliberately
changed so as to maintain diversity in the
population set.
• It is mostly done by changing one or more
characteristics of an individual solution.
• In case of binary encoding one or more bits
are inversed.
Termination
Termination occurs when an optimal solution is
obtained.
• Optimal solution is relative to the given problem.
• It can happen when
a solution in a particular range is obtained.
a particular number of generations have gone by.
or any other condition specified by the programmer has been
satisfied.
•
Advantages
• GAs search for the function optimum starting from a
population of points of the function domain, not a
single point. It means that GAs are global search
methods.
• Parallelism in Gas help in solving problems whose
space of potential solution is very vast.
• GAs know nothing about the problems they are
deployed to solve, hence they may lead to solutions
which can not be perceived by human programmers.
Applications
• Solving optimization problems like
TSP,space allocation, chip designing etc.
• Decision making in gaming.
• Data mining process.
• Pattern recognition
and many more applications….
Conclusion
As incredible it may seem but it is true that Genetic
Algorithms DO WORK.
There really are effective in solving problems which are
so large that they have many possible optimal
solutions spread across the search space.
Genetic Algorithms have a great future in problem
solving across a varied number of fields
Thank You!!!
