Transcript EC – Tutorial (Lecture 16)

EC – Tutorial (Lecture 16)
Ata Kaban
University of Birmingham
Overview
•
•
•
•
Exam-Style Questions / Answers
Programming Exercises
More examples re last few topics
Plans for next tutorial
4-Player Iterated Prisoner’s
Dilemma
• This is an example for co-evolutionary
learning
• Problem specification given last tutorial
• Any solutions?
• Any difficulties?
Design:•
•
•
•
•
•
Chromosome representation for strategies (players)
Fitness evaluation function
Evolutionary operators (crossover, mutations)
Selection scheme
Comment on parameters of your design.
Comment on strengths and weaknesses of your
design
Which of these items did you find the most difficult /
the easiest?
Representation
• Strategy = lookup table
– Situation (history)  action, for each situation
• How to represent history of the game?
– Let l denote the length of the history considered
• How many histories are possible in this
game?
…representing history
• The player’s own previous l moves
– Requires ……….. bits
• The number of co-operators in the last l moves
– Requires ……….. bits
That is ………. bits in total
•
• An example of encoded history, if l=3:
001111001
What does it mean?
 need a convention as of which bit means what
o Let the first l bits indicate the player’s own actions
o Let the leftmost bit refer to the most recent move
o Let the next groups of 2 bits indicate the nos of
collaborators
o Let the leftmost group refer to the most recent move
001 11 10 01
Now the bit-string ‘makes sense’!
Can you read the story from the bit-string now?
• How many histories are there in total?
If 9 bits are needed to represent a history
Then there are 29 histories possible.
Remember, we agreed that strategies will be stored as
‘lookup tables’:
One strategy is a binary string (0=coop, 1=defect) that
gives an action for all possible histories. How long this
string is?……………
So 29 bits are needed to represent a strategy.
e.g. for history ‘001 11 10 01’=121, the action is
whatever is listed in entry (bit) 121.
• Sure? Anything missing?
• What is missing?
– Actions are taken as function of the history
– What about the very first action?
• Need some more bits to represent l=3 virtual previous
round at the beginning of the game!
– That’s ………….. bits
• Length of bit string that represents one strategy:
– It’s not 29 but 29+9 [NOTE: We need 9 bits to represent the
‘pre-history’ according to which player A will make his first
move!]
• Can you now write this quantity more generally, with
history length l and nos of players N?
– Email me your solution.
Fitness evaluation function
• Fitness of an individual player is evaluated
by playing a number K of 4-player (Nplayer) games with adversaries randomly
drawn from the population & adding the
payoffs obtained
Evolutionary operators
• Since binary strings are used, e.g.
– Uniform crossover
– Bit-wise flipping can be used
Selection scheme
• Fitness ranking or tournament selection
• Important is to maintain the selection
pressure constantly!
Discussion. Strengths, weaknesses
• Strengths:
– Generic, the same design can be applied for more
general number of players N
– Simplicity in evolution and game playing due to bit
string representation
• Weaknesses:
– In N is large, computation time is long
– Inability to capture multiple cooperation levels
• Parameters that influence the results:
– History length
– Nos of generations
52-city TSP Programming
exercise
• This is an example of combinatorial
optimisation. Also an example of constrained
optimisation! (remember the individuals =
tours have to be valid permutations)
• The locations of the towns were given to cutand paste into your program in the last
tutorial.
• What is the minimum distance?
• Any problems encountered?
• Did you encounter edge-failures?
• How did you solve them?
Hints and memory refreshing
• Crossover for Path-Representation
– First: build edge-map
• One row for each town
• Lists the 4 neighbors the town has in both parents
– Second: produce offspring
• Pick random parent
• From edge map, find a neighbor (see below)
• Remove neighbor from map, continue
– Selection of neighbour
• Version 1: Pick neighbour with smallest nos of
edges in its own list
• Randomly break ties
• Version 2: pick closest neighbour with higher
probability
• Version 3: use V.1, but break ties by distance
– Edge failures
• When all neighbours in the edge map have already
been visited
• Solution: chose random remaining town
• V.1. And V.3. Try to minimise edge failures.
…example
Distances:
Two parent genotypes:
<1 6 3 2 4 5>
1
<4 5 1 2 6 3>
2
1
2
3
4
5
6
1
-
10
16
8
12
15
2
10
-
18
16
19
20
3
16
18
-
19
11
15
4
8
16
19
-
14
10
5
12
19
11
14
-
9
6
15
20
15
10
9
-
3
Edgemap:
4
5
6
Offspring (e.g. using version 2):