Transcript Gov 2015 Introduction to Computational Modeling for Social

Advanced Computational Modeling
of Social Systems
Artificial life and
artificial intelligence
Lars-Erik Cederman and Luc Girardin
Center for Comparative and International Studies (CIS)
Swiss Federal Institute of Technology Zurich (ETH)
http://www.icr.ethz.ch/teaching/compmodels
Today’s agenda
2
•
•
•
•
Complex Adaptive Systems
Artificial intelligence
Artificial life
Genetic algorithms
– Foundation
– Genetic operators
• GeneIPD
Complexity theory
3
Complex adaptive systems
exhibit properties that
emerge from local
interactions among many
heterogeneous agents
mutually constituting their
own environment
“Boids”
A model of the Internet
The Santa Fe Institute
Complex Adaptive Systems
4
A CAS is a network exhibiting aggregate
properties that emerge from primarily local
interaction among many, typically heterogeneous
agents mutually constituting their own
environment.





Emergent properties
Large numbers of diverse agents
Local and/or selective interaction
Adaptation through selection
Endogenous, non-parametric environment
What is the mind?
5
•
•
•
•
•
•
•
•
Marionettes (ancient Greeks)
Hydraulics (Descartes)
Pulleys and gears (Industrial Revolution)
Telephone switchboard (1930’s)
Boolean logic (1940’s)
Digital computer (1960’s)
Hologram (1970’s)
Neural networks (1980’s - ?)
Bottom-up vs top-down
approach
Intelligence
model this
model these
Life
6
Definition of life
7
• No universally agreed definition of life.
• Typical features
–
–
–
–
–
–
–
–
–
–
Self-organization
Emergence
Autonomy
Growth
Development
Reproduction
Adaptation
Responsiveness
Evolution
Metabolism
Artificial life
8
• “By the middle of this century, mankind
has acquired the power to extinguish life
on Earth.”
• “By the middle of next century, it will be
able to create it. Of the two it is hard to say
which places the largest responsibility on
our shoulders”
Chris Langton
Artificial life
9
•
•
•
•
•
•
Theoretical biology
Artifactual (man-made), not unreal
Bottom up, not top down
Synthesis, not analysis
Leverages emergence
“The ‘artificial’ in Artificial Life refers to the
component parts, not the emergent processes.
If the component parts are implemented
correctly, the processes they support are
genuine—every bit as genuine as the natural
processes they imitate.” (Langton)
Boids
10
• Craig Reynolds (1987) work on flocking behavior
• Virtual birds with basic flight capability
• 3 rules
– (i) collision avoidance – avoid collisions with nearby
flock-mates
– (ii) velocity matching – attempt to match velocity with
nearby flock-mates.
– (iii) flock centering – attempt to stay close to nearby
flock-mates
• Each boid is a basic unit that “sees”
only its nearby flock-mates and
“flies” according to the 3 rules.
Boids (cont.)
11
Boids (cont.)
12
• Result: boids flocked and flew as a cohesive
group. When obstacles appeared in their way
they spontaneously split into 2 subgroups,
without central guidance, and rejoined after
clearing obstruction.
• Illustrate basic principles of Alife systems
– Large number of simple elemental units
– Units interacting with nearby neighbors with no
central controller
– High-level emergent phenomena from low level
interactions
Novelty
13
Genetic algorithms
14
• Genetic algorithms (GA’s)
are an optimization
technique
• GA’s are based on Darwin’s
theory of evolution
• Genetic algorithms combine
search algorithms with the
genetics of nature.
• Invented by John Holland in
mid 70’s
Charles Darwin
1809-1882
John Holland
Biological terminology
15
• Cell nucleus contain the genetic
information
• Genetic information is stored in
the chromosomes
• The chromosome is divided in
parts: genes
• The different settings of the
genes for one property is called:
allele
• Every gene has an unique
position on the chromosome:
Reproduction
16
• During sexual reproduction,
crossover occurs
• This recombination of
chromosomes become the
new individual
• Hence genetic information
is shared between the
parents in order to create
new offspring
• During reproduction “errors”
occur: mutation
Natural selection
17
• The Origin of Species:
“Preservation of favourable
variations and rejection of
unfavourable variations.”
• There are more individuals born
than can survive, so there is a
continuous struggle for life.
• Individuals with an advantage
have a greater chance to
survive: survival of the fittest.
How does it works?
18
Why genetic algorithms?
19
• If nature can do it, why can’t computers?
• Power of evolution to solve optimization
problems
• Particularly well suited for hard problems
where little is known about the underlying
search space
Selection
20
• Main idea: better individuals get
higher chance
• Roulette-wheel sampling gives more
fit individuals better chance:
1/6 = 17%
A
3/6 = 50%
B
C
f(A) = 3
f(B) = 1
2/6 = 33%
f(C) = 2
1-point crossover
21
• Sexual reproduction is performed by mixing genes from
the parents
• With a certain probability, we cross over some couples.
• Choose a random point on the two parents
• Split parents at this crossover point
• Create children by exchanging tails
Mutation
22
• Occurs at the isolated gene level within a chromosome
• Can result in changes, both positive and negative, in the
fitness of an individual
• When positive, can help increase individual’s chance of
being selected to be a parent of next generation
A standard genetic
algorithm
1.
2.
3.
Start with a randomly generated population of n
chromosomes (genotypes)
Calculate the fitness developed by each
chromosomes in the population
Repeat the following steps until n offspring have been
created:
a) Select a pair of parent chromosomes from the current population, the
probability of selection being an increasing function of fitness
b) Crossover the pair, with probability pc (crossover rate), at one or two
randomly chosen points, to produce two new offspring
c) Mutate the offspring at each locus with probability pm (mutation rate),
and place the resulting chromosomes in the new population
4.
5.
Replace the current population with the new
population
Go to step 2 (next generation)
23
Iterated Prisoner’s Dilemma
24
• Cohen, Riolo, and Axelrod. 1999. “The
Emergence of Social Organization in the
Prisoner's Dilemma” (SFI Working Paper 99-01002)
http://www.santafe.edu/research/publications/wpabstract/199901002
• In The Evolution of Cooperation, Robert Axelrod
(1984) created a computer tournament of IPD
– cooperation sometimes emerges
– Tit For Tat a particularly effective strategy
Prisoner’s Dilemma Game
25
Column:
C
C
Row:
D
D
3,3
0,5
5,0
1,1
One-Step Memory
Strategies
Strategy = (i, p, q)
C
p
Memory:
C
D
q
C
t
D
D
t-1
i = prob. of cooperating
at t = 0
p =prob. of cooperating
if opponent
cooperated
q =prob. of cooperating
if opponent defected
26
The Four Strategies
27
Name
i
p
q
ALLC
1
1
1
TFT
1
1
0
ATFT
0
0
1
ALJD
0
0
0
TFT meets ALLD
28
Cumulated
Payoff
p=1; q=0
0
Row
(TFT)
Column
(ALLD)
+
1
+
1
+
1
=3
1
=8
i=1
C
D
D
D
D
D
D
D
C
D
i=0
5
+
1
+
1
+
p=0; q=0
0
1
2
3
4
t
Payoffs for 4x4 strategies
29
Other‘s strategy
Own
ALLC
ALLC
TFT
pay/move
pay/move
pay/move
3333
3333
0000
0000
3333
12
3333
12
ATFT
5555
0153
5103
5555
9
9
3
1000
8
1555
8
0
0111
1313
5111
20
0
12
20
ALLD
ALLD
pay/move
12
TFT
ATFT
1
1111
16
4
Genetic encoding for IPD
model
• For each of the possible historical cases –
encode a move.
History
Future
Player
1
CDDCDCDDDCCDDCC
CDC
C
Player
2
DD D C D C D D C C C C C C C
DCC
D
Sliding window
(memory depth = 3)
30
Genetic encoding for IPD
(cont.)
Memory depth = 2
Second
phantom
move
C
D
0
D
D
C
C
C
1
Two-rounds
memory
C
Initial
phantom
move
C
1
31
C
1
D
D
D
D
D
0
D
C
1
D
0
C
1
D
0
C
1
D
0
C
1
D
0
C
1
D
0
C
1
D
0
C
1
D
0
GeneIPD
32
•
•
•
•
Do cooperation emerge in a spatial world?
Do defection emerge in a soup?
Is this always the case?
How does the crossover and mutation
rates affect the simulation?
Definition of life
34
• What is life? Is “artificial” life possible?
• Webster dictionary
– 1a. The quality that distinguishes a vital and
functional being from a dead body or purely
chemical matter.
– 1b. The state of a material complex or
individual characterized by the capacity to
perform certain functional activities including
metabolism, growth and reproduction
Life versus Intelligence
35
• Life is…
Islands of information that persist and
reproduce.
• Intelligence is…
The use of information to persist and
reproduce.
Alternative Crossover
Operators
• Performance with 1-point crossover depends on
the order that variables occur in the
representation
– More likely to keep together genes that are near each
other
– Can never keep together genes from opposite ends of
string
– This is known as Positional Bias
– Can be exploited if we know about the structure of our
problem, but this is not usually the case
36
n-point crossover
37
•
•
•
•
Choose n random crossover points
Split along those points
Glue parts, alternating between parents
Generalization of 1 point (still some positional
bias)
Uniform crossover
38
• Assign 'heads' to one parent, 'tails' to the other
• Flip a coin for each gene of the first child
• Make an inverse copy of the gene for the second
child
• Inheritance is independent of position
Genetic encoding for IPD
(cont.)
Tit-For-Tat
• 1 move remembered:
If CC (case 1), then
C
If CD (case 2), then
D
If DC (case 3), then
C
If DD (case 4), then
D
• Can be encoded as the string “CDCD” or “1010”
• For two possible moves remembered ->
16 (4 x 4) possibilities (16 bits string)
• For three possible moves remembered ->
64 (4 x 4 x 4) possibilities (64 bits string)
39
Genetic encoding for IPD
(cont.)
• But this is not enough, as the strategy
requires results from previous games
• Extra genes to encode hypothetical
moves:
1 move memory: 4 + 1 = 5 bits
2 moves memory: 16 + 3 =19 bits
3 moves memory: 64 + 7 = 71 bits
• Number of potential strategies for 3 moves
history is in the order of 1021
40