Transcript The Standard Genetic Algorithm

The Standard Genetic
Algorithm
• Start with a “population” of “individuals”
• Rank these individuals according to their
“fitness”
• Select pairs of individuals to “reproduce”
– Higher fitness  greater probability of selection
• Each pair of “parents” produces two “children”
– Because of “crossover,” children receive “genes” from
both parents
• Introduce random “mutations” in some of the
children
• Repeat until a desired fitness level has been
reached or some number of generations have
Individuals and Fitness
• In this system, the individuals are utility
functions, and the genes are the weights
assigned to the different factors.
• Population size is set by the user and must be a
power of 2.
• Fitness is measured in a single-elimination
tournament.
–
–
–
–
Games are played to a maximum of 40 moves.
A win in the tournament is worth 10 fitness points.
A tie is worth 5 fitness points.
The sum of all individuals’ fitnesses is normalized to 1.
• Parents are selected with probability equal to
Finding Fitnesses
Individual
A
B
C
D
E
F
G
H
Total
The T our namen t
C
+1 0 p ts
C
+1 0 p ts
A
+1 0 p ts
A
0 p ts
B
0 p ts
F
+1 0 p ts
C
+1 0 p ts
C
0 p ts
D
0 p ts
F
+1 0 p ts
E
0 p ts
F
0 p ts
G
+1 0 p ts
G
0 p ts
H
0 p ts
10
0
30
0
0
20
10
0
70
Points Fi
0.1429
0
0.4286
0
0
0.2857
0.1429
0
1
Crossover and Mutation
• Genes are listed in a fixed, arbitrary order, and
crossover occurs at a single, randomly chosen
point in the list.
– One child receives from one parent the set of genes that
occur before the crossover point. It receives from its
other parent the set of genes that occur after the
crossover point.
– The other child receives the complementary set of
genes from each parent.
• Each gene is subject to mutation with a small,
independent probability that is set by the user.
– The size of the mutation is random, but the distribution
is skewed toward smaller changes.
Generating Children
Parents
Children
10
Advancement
Back Row Bridge 2
8
Center Control
Diagonal Moment 3
King Center Control5
5
Total Mobility
Triangle of Oreo 1
4
Threat
10
2
8
3
5
8
2
5
10
3
8
3
5
5
2
5
6
Advancement
Back Row Bridge 9
9
Center Control
Diagonal Moment 1
King Center Control4
8
Total Mobility
Triangle of Oreo 2
5
Threat
6
9
9
1
4
5
1
4
6
8
9
1
4
5
1
4
crossover
mutation
Encoding Knowledge of
Checkers
• Move Generator
– Incorporates all of the rules of the game.
– Computes the legal moves that are available in a given
board state.
• Utility Function
– Attempts to quantify the desirability of a given board
state.
– Consists of a simple linear combination of 16 factors
taken from A. L. Samuel’s original checkers program of
1959.
– Coefficients can take on any value in the range of a Java
double.
– Unfortunately, this function is too simple to represent
the game, since it cannot even represent interactions
The Computer Player
• Basic Strategy: Minimax Search
– Searches forward in time to find the best move to make
now.
– Represents the game as a tree.
• Each level corresponds to a turn.
• Each node corresponds to a possible game state.
• Each edge represents a legal move.
– Assumes that, at each turn, players will choose the
move that is most beneficial.
– In checkers, it is usually impossible to search to the end
of the game because there are so many possible moves
at each turn. In this system, the search is stopped at an
arbitrary depth of 6 moves, and a utility function rates
the desirability of every possible game state.
Minimax Search
100
choose best (max)
–
100
5
20
45
choose worst (min)
121
100
204
choose best (max)
–
100
choose worst (min)
130
100
Example Minimax Search with Depth 5.
Each oval represents a possible game state.
The numbers represent utility values.