Transcript Genetic Algorithms Yohai Trabelsi

Genetic
Algorithms
Yohai Trabelsi
Outline
•
•
•
•
Evolution in the nature
Genetic Algorithms and Genetic Programming
A simple example for Genetic Algorithms
An example for Genetic programming
•
•
•
•
Evolution in the nature
Genetic Algorithms and Genetic Programming
A simple example for Genetic Algorithms
An example for Genetic programming
Evolution in the nature
• A Chromosome:
o A string of DNA.
o Each living cell has some.
•
Image by Magnus Manske
Each chromosome
contains a set of genes.
• A gene is a block of DNA.
• Each gene determines
some aspect of the
organism
(e.g., eye colour).
•
Reproduction in the
nature
• Reproduction involves:
1. Recombination of genes from parents.
2. Small amounts of mutation (errors) in copying.
• One type of
recombination is
crossover.
• Reproduction involves:
1. Recombination of genes from parents.
2. Small amounts of mutation (errors) in copying.
• Right image by Jerry Friedman.
• In the nature, fitness describes the ability to survive
and reproduce.
Images by ShwSie
The evolution cycle
Initialization
Upper left image by 慕尼黑啤酒
Parent
selection
Recombination
Mutation
•
•
•
•
Evolution in the nature
Genetic Algorithms and Genetic Programming
A simple example for Genetic Algorithms
An example for Genetic programming
Some history
• First work of computer simulation of evolution- Nils
Aall Barricelli(1954)
• In the 1950s and 1960s several researchers began
independently studying evolutionary systems.
• The field has experienced impressive growth over
the past two decades.
Genetic Algorithms
• The research on Genetic Algorithms focuses on
imitating the evolution cycle in Algorithms.
• That method is applicable for many hard search
and optimization problems.
Initialization
• Initialization is the process of making the first
generation.
• During the algorithm our goal will be to improve
them by imitating the nature.
Termination.
• In the nature we don’t have (yet) a point that the
process stops.
• In many cases an algorithm that runs forever is
useless.
• We should try to find the correct time for
terminating the whole process.
o That time may be after the results are good and/or before the
running time is too long.
The modified evolution
cycle
Initialization
Upper left image by 慕尼黑啤酒
Parent
selection
Recombination
Mutation
GA-Some definitions
• In any generation there is a group of individuals
that belongs to that generation.
We call that group population.
• Fitness will be a function from individuals to real
numbers.
• The product of the recombination process is an
offspring.
Genetic Programming
• Genetic Programming is Genetic Algorithm
wherein the population contains programs rather
than bitstrings.
•
•
•
•
Evolution in the nature
Genetic Algorithms and Genetic Programming
A simple example for Genetic Algorithms
An example for Genetic programming
A simple example
• Problem:
“Find” the binary number 11010010.
Initialization
• We start with 5 random binary numbers with 8 digits
each.
1. 01001010
2. 10011011
3. 01100001
4. 10100110
5. 01010011
The fitness function
• We define the fitness of a number to be the sum of
the distances of its digits from these in the target,
with the sign minus.
• The target: 11010010
• fitness(01001010)=
1−0 + 1−1 + 0−0 + 1−0 + 0−1
−
+ 0 − 0 + 1 − 1 + |0 − 0|
= −3
The target: 11010010
1.
2.
3.
4.
5.
fitness(01001010)=-3
fitness(10011011)=-3
fitness(01100001)=-5
fitness(10100110)=-4
fitness(01010011)=-2
Parent Selection
• In each generation, some constant number of
parents, say, 4 are chosen. Higher is the fitness,
greater is the probability of choosing the individual.
•
•
•
•
{01001010,10011011,01100001,10100110,01010011}
{-3,-3, -5,-4,-2}
Assume we select 10011011, 10100110.
fitness(10011011) > fitness(10100110) 10011011
selected.
…
• We get {01001010,10011011,10100110,01010011}
Recombination
• Two selected parents will be coupled with
probability 0.5.
• (01001010,10011011) , (01001010, 10100110),
(10100110 ,01010011)
• 3 is selected as a random number from 1…8
• Then we do a crossover:
From (01001010,10011011) we get (01011011,10001010)
• We repeat that for each selected couple.
Mutation
• For each digit in each of the offsprings , we make
the bit flip with probability 0.05.
• For 10001010 we have 10011010.
The process and it’s
termination
• We repeat the cycle until one of the numbers that
we get would have fitness 0 (that is would be
identical to the desired one).
• We expect that it will not be too long in comparison
to checking the fitness of all the numbers in the
range.
• Our hope is based on choosing parents with higher
fitness and on producing next generations similarly
to the nature.
Some Results
• Similar example, where the target was “Hello world”
achieved the score in generation 65.
(population size=400 , 2611 options)
• In our simple case there are 28 = 256 options in
total.
•
•
•
•
Evolution in the nature
Genetic Algorithms and Genetic Programming
A simple example for Genetic Algorithms
An example for Genetic programming
American Checkers
• Michel32Nl
Lose Checkers
• The rules are the same as in the original game.
• The goal is opposite to the goal in the original
game: Each player tries to lose all of his pieces.
• Player wins if he doesn’t have any pieces or if he
can’t do any move.
The complexity
• There are roughly 1020 legal positions.
• In chess there are 1043 − 1050 .
Previous work
• There are few recent results on Lose checkers.
• They concentrate either on search or on finding a
good evaluation function.
• They can help to improve good players but they
can’t produce good players.
• Improvements on a random player don’t worth
much.
The algorithm
• The individuals will be trees.
• Each tree will behave like evaluation function for
the board states (more details later).
• A tree represents a chromosome.
• Each tree contains nodes.
• A node represents a gene.
• There are three kinds of nodes:
o Basic Terminal Nodes.
o Basic Function Nodes.
o Domain-Specific Terminal Nodes.
Basic terminal nodes
Node name
Return type
Return
value
ERC
Floating
point
Ephemeral
Random
Constant
False
Boolean
Boolean false
value
True
Boolean
Boolean true
value
One
Floating
point
1
Zero
Floating
point
0
Basic function nodes
Node name
𝐴𝑁𝐷(𝐵1, 𝐵2)
Return
value
Logical AND of parameters
𝐿𝑜𝑤𝑒𝑟𝐸𝑞𝑢𝑎𝑙(𝐹1, 𝐹2) True iff F1 ≤ F2
𝑁𝐴𝑁𝐷(𝐵1, 𝐵2)
𝑁𝑂𝑅(𝐵1, 𝐵2)
𝑵𝑶𝑻𝑮(𝑩𝟏, 𝑩𝟐)
𝑂𝑅(𝐵1, 𝐵2)
𝑰𝑭𝑻(𝑩𝟏, 𝑭𝟏, 𝑭𝟐)
Logical NAND of parameters
Logical NOR of parameters
Logical NOT of B1
Logical OR of parameters
F1 if B1 is true and F2 otherwise
𝑀𝑖𝑛𝑢𝑠(𝐹1, 𝐹2)
F1 − F2
𝑴𝒖𝒍𝒕𝑬𝑹𝑪(𝑭𝟏)
F1 multiplied by preset random number
𝑁𝑢𝑙𝑙𝐽(𝐹1, 𝐹2)
F1
𝑃𝑙𝑢𝑠(𝐹1, 𝐹2)
F1 + F2
Domain-specific nodes
EnemyKingCount
EnemyManCount
EnemyPieceCount
FriendlyKingCount
FriendlyManCount
FriendlyPieceCount
KingCount
FriendlyKingCount − EnemyKingCount
ManCount
FriendlyManCount − EnemyManCount
PieceCount
FriendlyPieceCount −EnemyPieceCount
KingFactor
King factor value
Mobility
The number of plies available to the player
Domain specific- details
of a square
IsEmptySquare(X,Y)
True iff square empty
IsFriendlyPiece(X,Y)
True iff square occupied by friendly piece
IsKingPiece(X,Y)
True iff square occupied by king
IsManPiece(X,Y)
True iff square occupied by man
An example for board
evaluation tree
The algorithm
• Make initial population
• While the termination condition didn’t reached:
o Select the best candidates for being parents.
o Make the new generation by crossover and mutation
o Evaluate the fitness of the new generation.
• Make initial population
• While the termination condition didn’t reached:
o Select the best candidates for being parents.
o Make the new generation by crossover and mutation
o Evaluate the fitness of the new generation.
The initial population
• The size of the population is one of the running
parameters.
• We select the trees randomly.
• Their maximum allowed depth is also a running
parameter.
• We omit the details of the random selection.
• Make initial population
• While the termination condition didn’t reached:
o Select the best candidates for being parents.
o Make the new generation by crossover and mutation
o Evaluate the fitness of the new generation.
Selection
Fitness evaluation
• We define GuideArr to be an array of guide players.
• Some of them are random players which are useful
for evaluating initial runs.
• Others, alpha-beta players, are based on search up
to some level and random behavior since that level.
• CoPlayNum is the number of players which are
selected randomly from the current population for
playing with the individual
under evaluation.
Image by Jon Sullivan
Fitness evaluation
• back
• Make initial population
• While the termination condition didn’t reached:
o Select the best candidates for being parents.
o Make the new generation by crossover and mutation
o Check whether the termination condition reached
Crossover
• Randomly choose two different previously
unselected individuals from the population.
• If 𝐼1. 𝑓𝑖𝑡𝑛𝑒𝑠𝑠 ≥ 𝐼2. 𝑓𝑖𝑡𝑛𝑒𝑠𝑠 then
o Perform one-way crossover with I1 as donor and I2 as receiver
• Else
o Perform two-way crossover with I1 and I2
• End if.
Two way crossover
• Randomly select an internal node in each of the
two individuals.
• Swap the subtrees rooted at these nodes.
One way crossover
• Randomly select an internal node in each of the
two individuals as a root of selected subtree.
• One individual (donor) inserts a copy of its selected
sub-tree into another individual(receiver), in place
of its selected sub-tree, while the donor itself
remains unchanged.
Similar to gene
transfer in
bacteria,
image by Y tambe
• Using the one way crossover gives the fitter
individuals an additional survival advantage.
• They still can change due to the standard two-way
crossover.
Mutation
• We randomly choose a node in the tree for
mutation.
• We do probabilistic decision whether to use the
traditional tree building mutation method or the
Local mutation method.
• The probability for each method is given as a
parameter to our algorithm.
Traditional mutation
• Traditional tree building mutation:
o Done by replacing the selected node with a new subtree.
• The drawback of using only the traditional mutation
is that a mutation can change dramatically the
fitness of an individual.
Local mutation
• Each node that returns a floating-point value
has a floating-point variable attached with it
(initialized to 1).
• The returned value of the node was the normal
value multiplied by the variable.
• The mutation is a small
change in the variable.
• Make initial population
• While the termination condition didn’t reached:
o Select the best candidates for being parents.
o Make the new generation by crossover and mutation
o Check whether the termination condition reached
Termination
•
The number of Generations until the termination will
be a parameter of our program.
The Players
•
•
•
•
Use alpha-beta search algorithm.
Evaluate non-terminal states using the individual
The depth of the search is 3.
There are more methods.
Some Results
•
1000 games were played against some alpha-beta
players.
• The Score: 1 point was
given for win and 0.5
For drawn.