Roff D.A. Modeling Evolution: An Introduction to Numerical Methods
Подождите немного. Документ загружается.
based model to examine the consequences of variation among individuals. The
approaches used in Scenarios 2–7 could be readily adopted for this purpose.
Servedio, M. R. and M. E. Hauber. 2006. To eject or to abandon? Life history
traits of hosts and parasites interact to influence the fitness payoffs of alter-
native anti-parasite strategies. Journal of Evolutionary Biology 19:1585–1594.
Problem: Under what conditions is the fitness payoff of egg ejection greater than
nest abandonment?
Approach: Single generation model based on a normal distribution of phenotypes.
The appendix gives a detailed account of the necessary equations. The results are
determined numerically. As noted by the authors, the model does not consider the
possibility of both behaviors in the population. This deficiency could be remedied
using an individual-based model as described in Scenarios 2 –7.
Eadie, J. M. and J. M. Fryxell. 1992. Density dependence, frequency-dependence,
and alternative nesting strategies in goldeneyes. American Naturalist 140:621–641.
Problem: Influence of frequency- and density-dependence on the evolution of
alternative nesting behaviors (brood parasitism females and parental females) in
the goldeneye.
Approach: Analytical solutions of frequency- and density-dependence are taken
separately followed by a simulation incorporating both effects. In the simulation
clonal inheritance is implicitly assumed with each female producing daughters
that have the same behavior as their mother. The model shows that both beha-
viors can be maintained in the population. Results compare favorably with the
observed data on goldeneyes.
Sinervo, B. 2001. Runaway social games, genetic cycles driven by alternative
male and female strategies, and the origin of morphs. Genetica 112–
113:417–443.
Problem: To explain the persistence of three alternative male strategies in various
lizard species (notably Uta stansburiana).
Approach: Simulation models using either clonal or simple Mendelian models of
inheritance. The models are analogous to the R-P-S models discussed in this
chapter. The results are compared to the observed dynamics of lizard populations.
Wakano, J. Y. and Y. Ihara. 2005. Evolution of male parental care and female
multiple mating: Game-theoretical and two-locus diploid models. American
Naturalist 166:E32–E44.
Problem: The evolution of male parental care and female multiple mating.
Approach: An analytical solution is derived for the case of clonal inheritance and
simulation used to analyze an individual-based model in which inheritance was
determined by a two-allelic, two-locus model. Under some parameter combina-
tions predictions of the two models differed significantly.
338 MODELING EVOLUTION
Beauchamp, G. U. Y. 2000. Learning rules for social foragers: implications for
the producer-scrounger game and ideal free distribution theory. Journal of
Theoretical Biology 207:21–35.
Problem: To determine the ability of various learning rules to predict the behavior
of social foragers under two types of scenarios: a producer-scrounger game and an
ideal free distribution game.
Approach: Simulation of various learning rules in the two scenarios. The ESS was
located numerically by varying the probability of displaying a behavior. By intro-
ducing a mutant using a different learning rule the stability of the ESS was
examined.
GAME THEORETIC MODELS 339
This page intentionally left blank
CHAPTER 6
Dynamic Programming
6.1 Introduction
Many, if not most, traits display phenotypic plasticity, that is, the phenotypic
expression of the trait is contingent on the environment. In some cases, such as
adult morphology, the development of the trait is determined in part by the
environment but does not vary once the trait is established. On the other hand,
other traits, particularly behavioral traits, may be extremely labile. For example,
foraging, oviposition, migration, and parental allocation decisions are all traits
that are typically state-dependent. The techniques presented in Chapter 2 may be
used to analyze such models in some cases (e.g., Scenario 12, which examined the
relationship between propagule size and age), but more frequently a dynamic
programming approach is required, or is at least more efficient. For detailed
discussions on dynamic programming, see Mangel and Clark (1988), Houston
and McNamara (1999), and Clark and Mangel (2000). To illustrate the method I
shall use the patch-foraging model described by Mangel and Clark (1988). As in the
previous chapters I shall set the scenario both in general terms and then with
specific mathematical functions. MATLAB code is provided at the end of the
chapter.
6.1.1 General assumptions in the patch-foraging model
1. The habitat is divided into a number of patches.
2. The animal in question forages among the patches for food or some other
fitness-related resource.
3. Patches vary in quality and hence the benefits obtained by the animal vary with
patch type.
4. There is a metabolic cost to foraging.
5. Independent of the metabolic cost there is a probability of dieing from some
external cause such as a predator or inclement weather conditions. This proba-
bility may vary among patches.
6. Fitness is measured as the probability of being alive at the end of some
time interval (e.g., in a small terrestrial vertebrate this may be the summer
period, the end of the season being the time at which hibernation is entered).
6.1.2 Mathematical assumptions in the patch-foraging model
1. There are three types of patches, which vary with respect to
a. Benefits of the resource, Benefit
i
, if found
b. Probability of obtaining the benefit (e.g., food), Pbenefit
i
c. Probability of mortality, Pmortality
i
2. The cost to foraging, Cost, is fixed and independent of patch type.
3. There is a minimum state, Xcritical, at or below which the animal cannot
survive. The minimum state at which an animal can survive is Xmin.
4. There is limit to the state (e.g., space for storing the resource is limiting), Xmax.
5. Fitness is equal to the maximum probability of surviving until time T, the end
of the season (or some other designated point).
6.1.3 A first look at the model
Specific values for the parameters defined above are Xcritical ¼ 3, Xmax ¼ 10, and
for each patch:
Patch 1 is empty of resources but is a safe haven from sources of mortality other than
that of dieing because the animal’s state is at or below Xcritical. In contrast, patch 3 is
relatively rich in resources but there is also a relatively high probability of dieing. We
can define two transition states, depending on whether the resource is located:
Resource found in patch:
X
tþ1
¼ X
t
Cost þ Benefit; if X
tþ1
> Xmax then X
tþ1
¼ Xmax
OR
if X
tþ1
Xcritical then animal dies
Resource not found in patch:
X
tþ1
¼ X
t
Cost; if X
tþ1
Xcritical then animal dies
Given some starting state we ask “What is the set of decisions that will maxi-
mize the probability of the animal reaching the end of the period?” Because there
are three patches and each patch has itself two states (resource found or resource
not found), there are an extremely large number of possible paths from the start to
the end, most of which will be suboptimal. In mathematical notation we can state
the problem as follows:
Fðx; TÞ¼max Pr ðsurvive from t to TjX
t
¼ xÞð0:1Þ
Patch type Benefit Pbenefit Pmortality Cost
1 0 0.0 0.000 1
...................................................................................................................................................
2 3 0.4 0.004 1
...................................................................................................................................................
3 5 0.6 0.020 1
342 MODELING EVOLUTION
which can be stated in words as “Maximize the probability of surviving from
t until T given that the state of the animal at time t (¼X
t
), is equal to x” (throughout
this chapter X will refer to the state variable while x will refer to a particular value
of the state variable). Now we do know what the final state should be, namely
survival and hence we can write down the value of F(x, T)as
Fðx; TÞ¼
1ifx > Xcritical
0ifx Xcritical
ð0:2Þ
that is, the probability of being alive at time T is certain if the animal’s state
exceeds the lower critical value and is zero if it falls below that value. At time T 1
the animal must pick a patch that maximizes its probability of being alive at the
end of the next (last) interval.
Suppose at time T 1 the animal is in state X
T 1
¼ x ¼ 4: there are six scenarios
we have to analyze.
The animal should choose patch 3 to maximize its survival probability. Note that
this does not guarantee its survival. Suppose the animal is in state X
T 1
¼ x ¼ 5:
The appropriate patch is now patch 1, because, although the animal does not
accumulate any resources, it has a 100% probability of surviving to T. In fact,
provided that the animal’s state exceeds 4, the best choice will always be patch
1 in this time interval. Of course, survival may not be the only consideration: for
example, the amount of resources accumulated by T may also be important (we
consider this in Scenario 1).
To begin the process with survival as our fitness criterion we note, as given
above, that for all final values of x from Xmin to Xmax, where Xmin ¼ Xcritical þ 1,
Fðx; TÞ¼1 ð6:3Þ
Patch X
t
+1 Probablity Probability of Survival
Benefit No Benefit Pbenefit 1–Pbenefit
Patch 1 4 − 1+0=3 4− 1 = 3 0.0 1.0 0 because X
t
+1≤Xcritical
...................................................................................................................................................
Patch 2 4 − 1+3=6 4− 1 = 3 0.4 0.6 (0.996)(0.4 + 0) = 0.3984
...................................................................................................................................................
Patch 3 4 − 1+5=8 4− 1 = 3 0.6 0.4 (0.98)(0.6 + 0) = 0.588
Patch X
t
+1 Probablity Probability of Survival
Benefit No Benefit Pbenefit 1–Pbenefit
Patch 1 5 − 1+0=4 5− 1 = 4 0.0 1.0 (1)(0+1)=1
...................................................................................................................................................
Patch 2 5 − 1+3=7 5− 1 = 4 0.4 0.6 (0.996)(0.4+0.6)=0.996
...................................................................................................................................................
Patch 3 5 − 1+5=9 5− 1 = 4 0.6 0.4 (0.98)(0.6 + 0.4) = 0.98
DYNAMIC PROGRAMMING 343
that is, we are only interested in those individuals that are alive at the end of the
time period.
We now step back one time unit and consider the survival from time T 1toT
for a particular value of x at time T 1 (say x). Depending on whether the animal
finds food or not the value of x will change to x
Food
or x
NoFood
, the particular values
depending on the patch: let these survivals be designated as S(x
Food
, i, T 1) and
S(x
NoFood
, i, T 1), where i is the patch number. Fitness for each patch, W(x, i, T 1)
is then given by
Wðx; i; T 1Þ¼ð1 PmortalityÞ½Sðx
Food
; i; T 1ÞFðx
Food
; T 1Þ
þSðx
NoFood
; i; T 1ÞFðx
NoFood
; T 1Þ
ð6:4Þ
The (1 Pmortality) is the probability of survival, irrespective of the patch. There
are now k fitness values, of which we choose the largest, the associated patch
being the optimal patch choice. The value of Fðx; T 1Þ is given by
Fðx; T 1Þ¼maxfWðx; 1; T 1Þ; Wðx; 2; T 1Þ; Wðx; 3; T 1Þg ð6:5Þ
The above algorithm can be repeated for all possible values of the penultimate
state, which in this case are unit steps from x ¼ 4tox ¼ 10. Thus we arrive at the
optimal set of decisions in the last period for all possible states the animal can be
in at the start of this period.
We now have the best decision for the last time period and the probability
of survival from this period to the end. At this point we can move one
step backward and calculate the best decision for this period. The process is
repeated until the first time period is arrived at. Going backward in this way
we build up a decision matrix in which the columns give the state (Xmin to
Xmax) and the rows give the time. Such a matrix is shown in Table 6.1, with
the bottom half of the table showing F(x, t) (i.e., the probability of surviving
from t to T given
the optimal path). To see how this matrix can be used let
us assume that the animal commences in state 7. In the first time period
the animal should select patch 3 which, if the animal survives, will change its
state from 7 to 7 1 þ 5 ¼ 13, if resources are found or from 7 to 7 1 ¼ 6if
resources are not found. In the first case, the total accumulated exceeds the
capacity of the animal and so its state is set to its maximum of 10 and in
the next time interval the animal selects patch 1. In the second case (no resources
found) the animal selects patch 2.
6.1.4 An algorithm for constructing the decision matrix
The example outlined above is a simple but general example of the type of model
for which dynamic programming is appropriate. The following algorithm can
be modified, as shown in later examples, to deal with most dynamic programming
problems. For convenience the program is divided into the main program
and three functions, called FITNESS, OVER.PATCHES and OVER.STATES. FIT-
NESS calculates the survival probability (fitness) for a given state in a given patch.
The other two functions iterate over patches, where patches may be physical or
344 MODELING EVOLUTION
Table 6.1 Decision matrix (top) and probability of survival, F(x,t,T) (bottom) for foraging model
State (Shown along bottom row)
Time [,1] [,2] [,3] [,4] [,5] [,6] [,7]
[1,] 3333221
...............................................................................................................................................
[2,] 3333221
...............................................................................................................................................
[3,] 3333221
...............................................................................................................................................
[4,] 3333221
...............................................................................................................................................
[5,] 3333221
...............................................................................................................................................
[6,] 3333221
...............................................................................................................................................
[7,] 3333221
...............................................................................................................................................
[8,] 3333221
...............................................................................................................................................
[9,] 3333221
...............................................................................................................................................
[10,] 3333221
...............................................................................................................................................
[11,] 3333221
...............................................................................................................................................
[12,] 3333221
...............................................................................................................................................
[13,] 3333222
...............................................................................................................................................
[14,] 3333221
...............................................................................................................................................
[15,] 3333211
...............................................................................................................................................
[16,] 3333111
...............................................................................................................................................
[17,] 3331111
...............................................................................................................................................
[18,] 3311111
...............................................................................................................................................
[19,] 3111111
...............................................................................................................................................
[20,] 45678910
...............................................................................................................................................
[,1] [,2] [,3] [,4] [,5] [,6] [,7]
...............................................................................................................................................
[1,] 0.514 0.724 0.812 0.846 0.866 0.878 0.886
...............................................................................................................................................
[2,] 0.518 0.73 0.819 0.854 0.874 0.886 0.893
...............................................................................................................................................
[3,] 0.523 0.737 0.826 0.861 0.881 0.893 0.901
...............................................................................................................................................
[4,] 0.527 0.743 0.833 0.869 0.889 0.901 0.909
...............................................................................................................................................
[5,] 0.532 0.75 0.84 0.876 0.897 0.909 0.917
...............................................................................................................................
................
[6,]
0.537 0.756 0.848 0.884 0.904 0.917 0.925
...............................................................................................................................................
[7,] 0.541 0.763 0.854 0.891 0.912 0.925 0.933
...............................................................................................................................................
[8,] 0.546 0.769 0.863 0.9 0.921 0.933 0.941
...............................................................................................................................................
[9,] 0.55 0.776 0.871 0.908 0.928 0.941 0.95
...............................................................................................................................................
[10,] 0.556 0.784 0.878 0.914 0.935 0.95 0.959
...............................................................................................................................................
[11,] 0.561 0.79 0.884 0.921 0.945 0.959 0.966
...............................................................................................................................................
[12,] 0.566 0.794 0.888 0.933 0.955 0.966 0.974
...............................................................................................................................................
[13,] 0.566 0.794 0.909 0.944 0.963 0.974 0.98
...............................................................................................................................................
[14,] 0.566 0.818 0.909 0.944 0.963 0.974 1
...............................................................................................................................................
[15,] 0.588 0.818 0.909 0.944 0.963 1 1
...............................................................................................................................................
[16,] 0.588 0.818 0.909 0.944 1 1 1
...............................................................................................................................................
(continued)
DYNAMIC PROGRAMMING 345
particular decisions such as “forage” or “not forage” (see Scenario 2), and states,
respectively.
The most complex part of the program is the bookkeeping of the survival
probabilities. To do this we first create a matrix called F.vectors that consists
of two columns with the number of rows typically being equal to the number of
states to be analyzed. In the present case, the state variable ranges from 3 (¼ dead)
to 10 (Xmax) and it is most convenient here to create the matrix with the number
of rows going from 1 to Xmax. The reason for this is that the row number then
corresponds to the state and indexing is simple (I consider the case later where the
states cannot be so easily indexed, because they are not integers). The first
column of the matrix contains the values of F(x, t) and the second contains the
values of F(x, t þ 1): Another way to look at it is that the second column contains
the values used in the calculations and the first column contains the updated
values, which are then passed into the second column once all the states have
been processed (the apparent “backward” nature of the indexing is because we
are going backward in time). Initially, all entries in the first column are set to
zero, while in the second column rows 1 to Xcritical are set to zero and the
remaining rows to 1, which is the terminal fitness value. Entries in this matrix
are changed as the program runs.
The program iterates over time commencing with the last interval: this is
accomplished using a while loop:
Horizon <– 20 # Number of time steps
Time <– Horizon # Initialize Time
while ( Time > 1)
{
Time <– Time − 1 # Decrement Time by 1 unit
Lines of coding
}# End of Time loop
At each value of Time the following steps are made:
Table 6.1 (Continued)
State (Shown along bottom row)
Time [,1] [,2] [,3] [,4] [,5] [,6] [,7]
[17,] 0.588 0.818 0.909 1 1 1 1
...............................................................................................................................................
[18,] 0.588 0.818 1 1 1 1 1
...............................................................................................................................................
[19,] 0.588 111111
...............................................................................................................................................
[20,] 45678910
Note: Output from R is slightly modified for display purposes.
346 MODELING EVOLUTION
Step 1: Call function OVER.STATES to iterate through values of state variables.
The first state is Xmin.
Step 2: Call function OVER.PATCHES to iterate through patch types. The first
patch type is patch 1.
Step 3: Call function FITNESS to calculate the fitness (¼ survival) in the selected
patch (presently patch 1) given the selected state (presently Xmin). First we calcu-
late the two new states the animal can achieve, which are labeled X.Food and X.
NoFood, corresponding, respectively, to the situations in which the resource is
found and that in which it is not found. As a general approach we first write down
an Outcome Chart that details the various outcomes (“” indicates that this
condition is not applicable):
The “tricky” part now is to calculate the probability that the animal survives from
this time to the end. At the start of the analysis we are at the end of the time period
and hence we know that this has a probability of one, which is what the second
column of F.vectors contains (except for rows below Xmin, which are zero
since animals in these states are dead). The survival probability for an animal in
state X.Food is thus equal to the probability at F.vectors[X.Food,2], that is,
the row that corresponds to state X.Food. Similarly, the survival probability for an
animal in state X.NoFood is equal to the probability at F.vectors[X.No-
Food,2], that is, the row that corresponds to state X.NoFood. Both of these
will initially be 1. In symbolism, survival if patch i is chosen is given as
Wðx; i; t 1Þ¼ð1 Pmortality
i
Þ½Pbenefit
i
Fðx
Food
; tÞþð1 Pbenefit
i
ÞFðx
NoFood
; tÞ
ð6:6Þ
In R code survival is given by
Term1 <- Pbenefit*F.vectors[X.Food,2] # If food is found
Term2 <- (1-Pbenefit)*F.vectors[X.NoFood,2] # If food is not found
W <- (1 - Pmortality)*(Term1 þ Term2) # Survival in patch
Note that the survival is the probability of surviving this time increment multi-
plied by the probability of surviving from then to T given the optimal patch
choice.
Step 4: Fitness is passed back to OVER.PATCHES where it is stored in a vector
called RHS. The row number of this vector corresponds to the patch type and the
value stored is the fitness (survival).
Food found x > Xcritical Survives x
Yes — Yes min(x – Cost + Benefit
i
, Xmax)
...................................................................................................................................................
No Yes Yes x – Cost
...................................................................................................................................................
No Yes No Set at Xcritical
...................................................................................................................................................
No No ‐ Set at Xcritical
DYNAMIC PROGRAMMING 347