Overview

  1. Static fitness functions
  2. Competitive fitness functions
  3. Co-evolutionary algorithms
  4. Introduction to evolutionary game-theory
  5. Game-theoretic co-evolutionary algorithms

Fitness functions

\(F(i | \eta)\)

Fitness landscapes

Ecology

Co-evolution

\(F(i | j, k, \ldots )\)

Evolutionary Arms-Races

Hosts and parasites

Co-evolutionary algorithms

Co-evolving sorting networks

Hillis, W. D. (1992). Co-evolving parasites improve simulated evolution as an optimization procedure. Physica D: Nonlinear Phenomena, 42(1–3), 228–234.

Co-evolving sorting networks

Co-evolutionary “pathologies”

Ficici & Pollack (1998)

The logic of animal conflict

Common side-blotched lizards

Sinervo et al. (1996).

Mating strategies

Modelling co-evolution

Expected fitness

Hawks and Doves

As a competitive fitness function

\[F(H|D) = V\]

\[F(D|D) = V/2\]

\[F(H|H) = (V-C)/2\]

\[F(D|H) = 0\]

As a payoff matrix

\(H\) \(D\)
\(H\) \((V-C)/2\) \(V\)
\(D\) \(0\) \(V/2\)

Examples

\(V=30, C=40\)

\(H\) \(D\)
\(H\) \(-5\) \(30\)
\(D\) \(0\) \(15\)

\(V=40, C=30\)

\(H\) \(D\)
\(H\) \(5\) \(40\)
\(D\) \(0\) \(20\)

Frequency-dependent fitness

Fitness functions

Hawk:

\begin{align} F(H|x) & = & x \times F(H|H) + (1-x) \times F(H|D) \& = & x(V - C)/2 + (1-x)V \end{align}

Dove:

\begin{align} F(D|x) & = & x \times F(D|H) + (1-x) \times F(D|D) \& = & (1-x)V/2 \end{align}

Population dynamics

\[F(x) = x \times F(H|x) + (1-x) \times F(D|x)\]

\begin{align} x' & = & x \frac{F(H|x)}{F(x)} \ & = & \frac{x}{C x2 - V} (C x + V x - 2 V) \end{align}

Numerical example

replicate <- function(x, V, C) {
 x*(C*x + V*x - 2*V)/(C*x**2 - V)
}

simulate <- function(x0, period, V, C) {
  result = c()
  x <- x0
  for(t in period) {
    result = c(result, x)
    x = replicate(x, V, C)
  } 
  result
}

t <- 0:13
result <- simulate(0.01, t, V=4, C=3)

Numerical example - data

x
1 0.01
2 0.02
3 0.04
4 0.08
5 0.14
6 0.25
7 0.41
8 0.60
9 0.78
10 0.91
11 0.98
12 1.00
13 1.00
14 1.00

Numerical example - plot

plot of chunk unnamed-chunk-3

Using matrix algebra

\[\mathbf{A} = \begin{bmatrix}(V-C)/2 & V\ 0 & V/2 \end{bmatrix}\]

\[F(i, \mathbf{x}) = (\mathbf{A}\mathbf{x})_i\]

\[F(\mathbf{x}) = \mathbf{x}^T \mathbf{A} \mathbf{x}\]

\[x_i' = x_i \frac{F(i, \mathbf{x})}{F(\mathbf{x})}\]

Continuous time

\begin{align} \frac{dN_i}{dt} = F(i, \mathbf{x}) \times N_i \ \frac{dN}{dt} = F(\mathbf{x}) \times N \ x_i = N_i / N \ \frac{dx_i}{dt} = x_i ( F(i, \mathbf{x}) - F(\mathbf(x)) ) \ \end{align}

Hawk-Dove in Continuous Time

require(deSolve)

HD <- function (time, state, parms) {
  with(as.list(c(state, parms)), {
    return(list(x*(C*x**2 - C*x - V*x + V)/2))
  })
}

IntegrateHD  <- function(t, state =  c(x = 0.01), payoffs = c(V=4, C=3)) {
  ode(func = HD, y = state, parms = payoffs, times = t)
}  

t <- seq(0, 10, by=0.01)
sim1 <- IntegrateHD(t, state = c(x = 0.01), payoffs = c(V=4, C=3))
sim2 <- IntegrateHD(t, state = c(x = 0.60), payoffs = c(V=4, C=3))

Hawk-Dove in Continuous Time

plot of chunk unnamed-chunk-5

Different initial conditions

plot of chunk unnamed-chunk-6

Different initial conditions

plot of chunk unnamed-chunk-7

Fitness

hawk.payoff <- function(x, parms) {
  with(parms,  
    x * (V - C)/2 + (1-x)*V)
}

dove.payoff <- function(x, parms) {
   with(parms,  
     (1 - x)*V/2)
}

av.payoff <- function(x, parms) {
  x * hawk.payoff(x, parms) + (1-x) * dove.payoff(x, parms)
} 

Fitness

plot of chunk unnamed-chunk-9

\(V < C\)

t <- seq(0, 15, by=0.01)
sim1 <- IntegrateHD(t, state = c(x = 0.01), payoffs = c(V=3, C=6))
sim2 <- IntegrateHD(t, state = c(x = 0.99), payoffs = c(V=3, C=6))

\(V < C\)

plot of chunk unnamed-chunk-11

Fitness

plot of chunk unnamed-chunk-12

Payoff to a mixed strategy

Evolutionarily Stable Strategies

Reproduced from Tuyls (2004).

ESS conditions

\[F(\mathbf{x}, (1 - \epsilon) \mathbf{x} + \epsilon \mathbf{y}) > F(\mathbf{y}, \epsilon \mathbf{y} + (1 - \epsilon) \mathbf{y}) \ \forall \mathbf{y} \neq \mathbf{x}\]

Implies:

\[F(\mathbf{x}, \mathbf{x}) > F(\mathbf{y}, \mathbf{x}) \; \forall \mathbf{y}\]

or

\[F(\mathbf{x}, \mathbf{x}) = F(\mathbf{y}, \mathbf{x}) \wedge F(\mathbf{x}, \mathbf{y}) > F(\mathbf{y}, \mathbf{y}) \; \forall \mathbf{y} \neq \mathbf{x} \]

Three strategies

\[A = \begin{bmatrix}0 & -1 & 1\ 1 & 0 & -1\ -1 & 1 & 0 \end{bmatrix}\]

Integrating the replicator equations

RPS <- function (time, state, parms) {
  with(as.list(c(state)), {
    dR = R*(S - P)
    dP = P*(R - S)
    dS = S*(P - R)
    return(list(c(dR, dP, dS)))
  })
}

IntegrateRPS  <- function(t, state =  c(R = 0.2, P = 0.2, S = 0.6)) {
  as.data.frame(ode(func = RPS, y = state, times = t))
}  

t <- seq(0, 300, by=0.01)
population.frequencies <- IntegrateRPS(t)[,2:4]

Time series

plot of chunk unnamed-chunk-14

Visualising population states

Visualising population states

Visualising population states

RPS phase space

plot of chunk unnamed-chunk-15

RPS in nature

Siverno et al (1996).

Co-evolutionary pathologies

Robust strategies

Game-theoretic co-evolution

Bibliography