Transcript Genetic Algorithms

COMP305. Part II.
Genetic Algorithms.
Genetic Algorithms
1
Topic 3.
Genetic Algorithms
Terminology.
Genetic Algorithms
2
Genetic Algorithms. Historical Introduction.
1960s – John Holland of Michigan University invented the
Genetic Algorithms (GAs) and later developed the
algorithms with his students and colleagues.
In contrast with “evolutionary strategies” and “evolutionary programming”,
Holland was not interested in finding solutions to particular problems,
but rather formally studied the phenomenon of adaptation as it occurs in
nature and how the algorithm might be used in the computer systems.
1975 – Holland’s book
“Adaptation in Natural and Artificial Systems”
1. presented the Genetic Algorithm as an abstraction of
natural evolution and
2. gave a theoretical framework for adaptation under GAs.
Genetic Algorithms
3
GAs by John Holland.
Holland introduced
• a “population” of binary strings which he called “chromosomes”.
• The “population” evolves using kind of “natural selection” together with the
genetics-inspired operators of crossover, mutation, and inversion.
• Bits in a “chromosome” represent genes, and each “gene” is an instance of a
particular “allele”, 0 or 1.
• The selection operator chooses those chromosomes in the population that will
be allowed to reproduce, and on average the fitter chromosomes produce
more offspring than the less fit ones.
• Crossover exchange subparts of two chromosomes
• Mutation randomly changes the allele values of some locations in the
chromosome.
• Inversion reverses the order of a contiguous section of the chromosome
rearranging the genes order.
Genetic Algorithms
4
Coding for Genetic Algorithms.
In contrast with Nature,
 there is no universal code in GAs,
 every coding is problem dependent.
The art of coding, though left beyond the scope, is very
important in Genetic Algorithms, as from the very
beginning the approach depends on whether or not the
problem can be coded as a string of characters at all.
The above implies serious restrictions on the class of
problems capable of solving by GAs.
Genetic Algorithms
5
GAs by John Holland. Chromosomes.
Definition:
GAs Chromosome is
a string of
“characters”, e.g.
“ABCDE1FGHI2JKL”,
coding
a candidate solution
for the problem in
consideration.
Genetic Algorithms
6
GAs by John Holland. Chromosomes.
Definition:
GAs Chromosome is a string of “characters”,
e.g.
“ABCDE1FGHI2JKL”,
coding a candidate solution for the problem in
consideration.
Often the GA chromosome is defined as a fixed length
binary string, e.g.
“1001111100001101”
Genetic Algorithms
7
GAs by John Holland. Chromosomes.
Definition:
GAs Chromosome is a string of “characters”. Often it
is a fixed length binary string, e.g.
“1001111100001101”
The same as nature blindly operates on real chromosomes
and does not know or care what information is
actually coded in the chromosomes,
Holland had left behind the question of
what particular information and in what way was coded
in the strings of the Genetic Algorithms chromosomes.
Genetic Algorithms
8
GAs by John Holland. Chromosomes.
Definition:
GAs Chromosome is a string of
“characters”. Often it is a fixed length binary string, e.g.
“1001111100001101”
Usually,
o Haploid organisms, i.e. the organisms with non-paired
chromosomes are considered in the Genetic Algorithms.
Genetic Algorithms
9
GAs by John Holland. Chromosomes.
Definition:
GAs Chromosome is a string of “characters”. Often
it is a fixed length binary string, e.g.
“1001111100001101”
Usually,
o GAs chromosome coincides with genotype, i.e. the genotype
consists of a single chromosome.
o For simplicity, there is no phenotype concept in Genetic
Algorithms either, and therefore
GAs chromosome = GAs genotype = GAs organism
Genetic Algorithms
10
GAs by John Holland. Chromosomes.
Definition:
GAs Chromosome is a string of “characters”. Often
it is a fixed length binary string, e.g.
“1001111100001101”
Following that in Genetic Algorithms
GAs chromosome = GAs genotype = GAs organism,
GAs Population is a population of GAs chromosomes,
e.g.
“1001001100001101”,
“1001111100001101”,
“1001100000001101”,
“1001101100001101” , ….Genetic Algorithms
11
GAs by John Holland. Chromosomes.
Definition:
GAs Chromosome is a string of “characters”. Often
it is a fixed length binary string, e.g.
“1001111100001101”
Following that in Genetic Algorithms
GAs chromosome = GAs genotype = GAs organism,
GAs Population is a population of GAs chromosomes,
e.g.
“1001001100001101”,
“1001111100001101”,
It is also called
population of candidate solutions.
“1001100000001101”,
“1001101100001101” , ….
Genetic Algorithms
12
GAs by John Holland. Chromosomes.
Definition:
GAs Chromosome is a string of “characters”. Often
it is a fixed length binary string, e.g.
“1001111100001101”
In a GAs chromosome, a character represents a gene
Possible settings for a gene are called alleles,
e.g. in the example above the alleles are 0s and 1s, and
if a gene codes a trait then an allele is the trait instance.
For binary chromosomes,
the alleles “alphabet” consists of just two characters, 0 and 1;
There might be bigger “alphabets” to represent bigger number of alleles.
Position of a gene in the string is called locus of the gene.
Genetic Algorithms
13
GAs by John Holland. Mutations.
Mutation is
change of allele of a gene at randomly chosen
location.
For binary chromosomes that means a flip of a bit at
randomly chosen locus.
“00000000000000000”
“00000100000000000”
For chromosomes with larger alphabet, mutation means
replacement of a character at randomly chosen location with
randomly chosen new character.
“0123456789”
“0123856789”
Genetic Algorithms
14
Crossover (recombination).
In nature,
crossover occurs
when two parents
exchange parts of
their corresponding
chromosomes:
In a genetic algorithm, crossover
recombines parts of two parent
chromosomes to make two “children”:
Parent1 “111111”
Parent2 “000000”
Child1 “111100”
Child2 “000011”
Or
Parent1 “ABCDEF” Child1 “GHJDEF”
Parent2 “GHJKLN” Child2 “ABCKLN”
Genetic Algorithms
15
Crossover (recombination).
In a genetic algorithm, crossover
recombines parts of two parent
chromosomes to make two “children”:
Parent1 “111111”
Parent2 “000000”
Child1 “111100”
Child2 “000011”
• The crossover cutting
point is chosen
randomly.
• One-point crossover
is considered most
often.
Or
Parent1 “ABCDEF” Child1 “GHJDEF”
Parent2 “GHJKLN” Child2 “ABCKLN”
Genetic Algorithms
16
Inversion and Translocation.
Inversion
is a mutation when part of a chromosome is cut out, rotates
by 180o and then fitted back into the same position:
“0123456789”
“0123654789”
Translocation
is a mutation when part of a chromosome is cut out and
moved to a different location in the chromosome
“0123456789”
“0123786549”
Both Inversion and Translocation need two break points in a chromosome.
Inversion and Translocation are rarely used in modern Genetic Algorithms.
Genetic Algorithms
17
Fitness Function.
To evaluate a chromosome fitness,
i.e. how good the candidate solution
solves the problem,
a Genetic Algorithm uses
fitness function.
The fitness function
1. takes a chromosome as an input and
2. produces its quantitative fitness
evaluation as an output.
Genetic Algorithms
18
Fitness Function.
The same as a particular code to be used
for coding a problem possible
solutions in a form of GAs
chromosomes depends on the
problem itself, a particular form
of the fitness function also depends
on the problem to be solved.
Example:
Maximize the real-valued function
f ( y )  y  | sin( 32 y ) |,
0 y
here the candidate solutions are values of y.
Genetic Algorithms
19
Evolving unit.
The same as in nature,
in GAs Population of chromosomes is the evolving unit.
The GAs population evolves from one generation of
chromosomes to the next generation and so on.
first generation
third generation ...
“1001001100001101”
“1001001100001101”
“1001001100001101”
“1001001100001101”
“1001001100001101”
second generation
“1001001100001101”
“1001001100001101”
“1001001100001111”
“1001001100001101”
“1001001100001101”
Genetic Algorithms
“1001101100101101”
“1001101100001101”
“1001101100001111”
“1001101100001101”
“1001101100001101”
….
….
….
….
….
20
Selection Operator.
To simulate natural evolution of population of chromosomes,
there must be a rule
how to choose which chromosome is more likely to
produce offspring for the next generation.
We shall call that rule a selection operator.
Usually a selection operator is defined in a way that
better fitted chromosome is selected for reproduction
more often and therefore will produce more offspring.
Genetic Algorithms
21
Search Space.
As Genetic Algorithms are to search for the best possible
solution to a problem, it was natural to introduce the concept
of a Search Space for the algorithms.
Definition:
Set of all possible solutions to a problem in
consideration is called a Genetic Algorithm search space.
Thus,
we search through the search space of possible solutions
for the best solution to the problem.
Genetic Algorithms
22
Fitness Landscape.
A fitness landscape is a
representation of all
possible solutions along
with their fitness.
The candidate
solutions are represented
by points in the
coordinate plane, i.e.
the search space, and
corresponding fitness is
measured along an
additional dimension.
Genetic Algorithms
23
Fitness Landscape.
A fitness landscape is a
representation of all
possible solutions along
with their fitness.
There will be “peaks”,
“hills”, and “valleys”
resembling features of
physical landscapes.
Evolution causes
populations move
towards the peaks of
the fitness landscape.
Genetic Algorithms
24