Transcript Genetic Algorithms

GENETIC ALGORITHMS
Ranga Rodrigo
March 5, 2014
1
EVOLUTIONARY COMPUTATION (EC)
2
INTRODUCTION TO EVOLUTIONARY COMPUTATION
• Evolution is this process of adaption with the aim of
improving the survival capabilities through
processes such as
– natural selection,
– survival of the fittest,
– reproduction,
– mutation,
– competition and
– symbiosis.
3
DNA, the molecular
basis for inheritance.
Each strand of DNA is a
chain of nucleotides,
matching each other in
the center to form what
look like rungs on a
twisted ladder.
http://en.wikipedia.org/wiki/Genetics
4
A Punnett square depicting a cross
between two pea plants heterozygous
for purple (B) and white (b) blossoms.
At its most fundamental level,
inheritance in organisms occurs by
passing discrete heritable units, called
genes, from parents to progeny.[31]
This property was first observed by
Gregor Mendel, who studied the
segregation of heritable traits in pea
plants.[12][32] In his experiments
studying the trait for flower color,
Mendel observed that the flowers of
each pea plant were either purple or
white—but never an intermediate
between the two colors. These
different, discrete versions of the same
gene are called alleles.
http://en.wikipedia.org/wiki/Genetics
5
EVOLUTIONARY COMPUTING (EC)
• Evolutionary computing models the processes of
natural evolution.
• It is a computer-based problem solving systems that
use computational models of evolutionary
processes, such as natural selection, survival of the
fittest and reproduction.
6
EVOLUTIONARY ALGORITHM PARADIGMS
Genetic algorithms
•Search or optimization based on genetic evolution: natural selection. By creating a population of
solutions and applying genetic operators such as crossover and mutation to evolve the solutions in
order to find the best one.
Genetic programming
•Evolution of a large number of randomly created computer programs to create program that solves
a high-level problem.
•Based on genetic algorithms where individuals are programs represented as trees.
Evolutionary programming
•Derived from the simulation of adaptive behavior in evolution (i.e., phenotypic evolution).
•Mostly applied to real-valued representations.
Evolutionary strategies
•Modeling the strategic parameters that control variation in evolution, i.e., the evolution of
evolution.
•For real-valued representation.
Differential evolution
Cultural algorithms
Coevolution
•Similar to genetic algorithms, differing in the reproduction mechanism used. Used for optimization
of multi-dimensional real-valued functions.
•Models the evolution of culture of a population and how the culture influences the genetic and
phenotypic evolution of individuals.
•Initially “dumb” individuals evolve through cooperation, or in competition with one another,
acquiring the necessary characteristics to survive.
7
GENETIC ALGORITHMS (GA)
8
INTRODUCTION TO GA
• Genetic algorithms imitate natural optimization
process, natural selection in evolution.
• Developed by John Holland at the University of
Michigan for machine learning in 1975.
• Mostly for binary representations.
9
EVOLUTIONARY SEARCH PROCESS
Initiation:
Selection of
initial
population of
chromosomes
Evaluation of
the fitness of
each
chromosome
Checking for
stopping
criteria
Selection of
chromosomes
Applying
genetic
operators
Creating a
new
population
Presentation
of the best
chromosome
10
Start
Initiation: Selection of initial
population of chromosomes
Evaluation of the fitness of
chromosomes in the population
No
Selection of chromosomes
Stopping
criterion
Yes
Presentation
of the “best”
chromosome
Application of genetic operators
Stop
Creating a new population
11
SELECTION (ROULETTE WHEEL)
• The fittest individuals must
have the greatest chance
of survival.
• Probability of being
selected
pi 
fi
N
f
j 1
j
12
http://www.edc.ncl.ac.uk/highlight/rhjanuary2007g02.php/
GENETIC OPERATORS
• Crossover: combination of genetic material
randomly selected from two or more parents.
• Mutation: process of randomly changing the values
of genes in a chromosome.
13