About this document ...

A Tutorial presented at the Congress on Evolutionary Computation, 2000

**Lee Altenberg, Ph.D.**

Information and Computer Sciences

University of Hawai`i at Manoa

`http://dynamics.org/~altenber/`

=

**Operators,**- (mutation, crossover, inversion, conversion, etc.) acting on the
**Representations**- of the search space (genotypes, strings, programs, designs, etc.), generate a
**Transmission function**,- the probability distribution of offspring types from any combination (one, two, etc., sometimes the whole population) of parent types.
**The relationship**- between the
**transmission function**and the**fitness function**is the main determinant the**performance**of the evolutionary algorithm.

Dynamics:

Where:

*i*- is an individual's type,
*x*_{i}- is the frequency of type
*i*in the population, *w*_{i}- is the fitness coefficient of type
*i*, and - is the probability that type
*j*produces offspring of type*i*(i.e. transformation--mutation, recombination, migration, permutation, etc.). - is when there are two parents, types
*j*and*k*.

evolutionary computation:

**``Fitness proportionate selection'' sounds like**

``Velocity proportionate speed''In other words, in evolutionary biology,

``Temperature proportionate heat''

``Mass proportionate weight''

``Length proportionate distance''

**`Fitness' is the measure of selection.**

**Objective function (phenotype) **** Fitness**

A better term: **`Proportional Fitness'**

The selection operator can be expressed as:

or in vector form:

**A. No: the coefficient ***w*_{i}** needn't be constant:
**

**
In fact can be functions of:
**

- the frequencies of types in the population,
- location,
- time,
- other species, agents, etc.--coevolution,
- or be a random variable.

**Fitness Components:**-
- Viability (survival rate)
- Fecundity (offspring number)
- Fertility (offspring number of particular mating types)

**When multi-parameter fitness coefficients may be required:**-
- Survivorship curves -- age dependent survival
- Fecundity curves -- age dependent reproduction
- Gene Environment interactions

**Q:** Suppose there is an evolutionary game being played between the types in a population. Will the evolutionarily stable strategies (ESS) be the same whether you use constant (`proportional') selection, or truncation selection?

**A:** No! Illustrates the hazard of calling *u*_{ij} the `fitnesses'.

- Lewontin, R. C. 1964. The interaction of selection and linkage: I. General considerations; heterotic models. Genetics 49: 49-67 (esp. pp. 55-56).
- Slatkin, M. 1970. Selection and polygenic characters.
*Proceedings of the National Academy of Sciences U.S.A.*66: 87-93.

**Asexual:**

or in vector form:

where

*x*_{i}= frequency of genotype*x*_{i}in the population, and frequency in the next generation;*w*_{i}= fitness of genotype*i*;-
= probability that genetic operators produce offspring
*i*from parent*j*; and - = mean fitness of the population.

**Sexual**

or in vector form:

(a quadratic operator-- not tractable in general), where

- is the tensor product (see below);
*w*_{ij}- is the fitness of the parental pair (
*i*,*j*) - is the
*n*^{2}by*n*^{2}diagonal matrix of coefficients*w*_{i1 i2}; - = probability that genetic operators produce offspring
*i*from parents*j*and*k*,

; - in this case is the
*n*by*n*^{2}matrix of transmission probabilities;

**Q. What is the limit as **
**?**

**A. For generic mutation and selection:
One attractor, not multiple peaks.**

How is this result derived?

- 1.
- The eigenvalue of with the largest magnitude, (the `spectral radius'), is always real and positive, and strictly larger in magnitude that all other eigenvalues of .
- 2.
- The eigenvector, , corresponding to eigenvalue , is positive.

- 1.
- The eigenvalue of with the largest magnitude, (the `spectral radius'), is always real and positive.
- 2.
- The eigenvector, , corresponding to eigenvalue , is positive.

=5in

There is only one attractor at each value , but an `error catastrophe' is evident for .

- So why do evolutionary algorithms with ergodic mutation seem to get trapped on `local fitness peaks'? e.g. Kauffman's NK Landscapes?
- Answer:
**finite population size**causing**genetic drift**: small random samples have stochastic variation, and types with few copies tend to go extinct rather than grow exponentially.

- Fisher, R. A. 1930.
*The genetical theory of natural selection.*Oxford: Clarendon Press.

- in a large population of individuals that produce an average of 1 offspring each,
- a new mutant appears that produces a average of 1 +
*s*offspring, - with variance ,
and where
*s*is small.

- Wright, S. 1931. Evolution in Mendelian populations.
*Genetics*16:97-159. - Fisher, R. A. 1930.
*The genetical theory of natural selection.*Oxford: Clarendon Press.

How can an evolutionary algorithm with finite population size be modelled? Wright and Fisher had the same idea for modelling for finite populations.

Suppose that each individual of the next generation be created by independent application of selection and genetic operators to the population.

Let:

*N*- be the population size;
- be a vector of the number of individuals of each type
*i*in the population; - be the probability a new individual of type
*i*is generated by selection and genetic operators acting on the population .

Then the chance
that there are individuals of type *i* in next generation is:

The Wright-Fisher model forms a Markov chain. Wright and Fisher analyzed many of the properties of this Markov system, including probabilities of fixation, time to fixation, and stationary distributions of allele frequencies.

The theory of Wright and Fisher is known in the Evolutionary Computation community as the `Nix and Vose model':

- A. E. Nix and M. D. Vose, 1991, Modeling genetic algorithms with Markov chains,
*Annals of Mathematics and Artificial Intelligence*5: 79-88.

Genetic Operator Intensity

- Karlin, Samuel. 1982. Classifications of selection-migration structures and conditions for a protected polymorphism. In Hecht, M. K. and B. Wallace and G. T. Prance,
*Evolutionary Biology*14: 61--204.

- constant selection, and
- asexual genetic operators.

How is this obtained? Let the asexual genetic operator be represented by the Markov matrix , and let is the probability of applying the operator. Then the transmission matrix for the algorithm is:

and the recursion is:

Samuel Karlin developed a theorem to determine when alleles introduced into a multi-deme population would increase in number.

Hence the mean fitness of the global attractor,

is a decreasing function of the operator probability .

Deceptive Function

=

- Roux, C. Z. 1974. Hardy-Weinberg equilibria in random mating populations.
*Theoretical Population Biology*5: 393-416. - Feldman, M. W. and J. Krakauer. 1976. Genetic modification and modifier polymorphisms. pp. 547-583 in
*Population Genetics and Ecology*, ed. S. Karlin and E. Nevo. Academic Press, New York. - Karlin, S. and U. Liberman. 1978. The two-locus multi-allele additive viability model.
*J. Mathematical Biology*5: 201-211.

Useful for:

- Multiple Loci
- Sexual Reproduction
- Compound types: genotype phenotype deme
- Compound operators: mutation recombination migration

Let

and

Then the tensor product is:

In general,

**Frequency Vector of Multiple Loci in Linkage Equilibrium**, i.e. no allele associations between loci:

**Frequency Vector of Genotypes Randomly Spread over Multiple Demes**

where is the vector of genotype frequencies and is the vector of deme sizes (as fractions of the whole meta-population).

When multiple independent operators are acting on the types in the population, the compound operator can be represented by tensor products.

**Mutation at Multiple Loci**

Suppose locus *k* mutates with transition probabilities

Then the mutation operator acting on the entire genotype of

**Mutation + Recombination**

When both recombination and mutation act independently on the genotype, the transmission function can be represented as (*R*=recombination, *M*=mutation, *D*=migration):

**Mutation + Recombination + Migration**

**Generalized Nonepistatic Fitnesses (Karlin and Liberman 1979)**

Does the order vs. produce different evolutionary outcomes?

Assume frequency-independent selection:

**Asexual:**

Clearly,
. However, make a change of variables: let
, and
. Then:

So the operators and produce the same trajectories with mapping between variables .

**Sexual:**

Again let , and .

What is the effect of applying selection to the choice of parents, and then applying selection again to the offspring?

Now, make a change of variables: let , and .

Hence

is equivalent to:

Crossover operators

- Geiringer, H. 1944. On the probability theory of linkage in Mendelian heredity.
*Ann. Math. Statist.*15: 25-57. - Karlin, Sam and Uri Liberman. 1978. Classification and comparisons of multilocus recombination distributions.
*Proc. Natl. Acad. Sci.*75: 6332-6336.

Geiringer (1944) developed a way to represent all possible recombination operators acting on two parents. This includes single point, multiple point, and uniform crossover. She considered which genes get transmitted together into an offspring.

- All the genes transmitted from one parent can be marked with a 0, and
- all the genes transmitted from the other parent can be marked with a 1.
- Hence a particular recombinant offspring can be represented as a binary string, e.g. (0,1,1,0,1,1,0,0,0).
- Hence, the recombination operation corresponds to a
*mask*

- There are possible such recombination operations.
- What defines a crossover operator is the probability of performing a particular recombination operation.
- Thus, a crossover operator can be defined as a probability distribution over the set of masks:

- Since every recombination event can produce an offspring with the genes from the reversed parents, we have the symmetry constraint that:

- Karlin, Sam and Uri Liberman. 1979. Central equilibria in multilocus systems. I. Generalized nonepistatic selection regimes.
*Genetics*91: 777-798.

where each is a diploid fitness matrix.

- Note: Haploidy is the special case where:

- Analytical solutions for the existence and stability of polymorphisms have been found for the general non-epistatic model.
- Generalized non-epistasis is a highly non-generic space of fitness functions.
- Trajectories and equilibria of the general epistatic model are unsolved in closed form.

- Goldberg, D. and Deb. 1991. A comparative analysis of selection schemes used in genetic algorithms. In G. Rawlins, editor,
*Foundations of Genetic Algorithms*, pages 69-93. Morgan Kaufmann, San Mateo, CA.

- Let
*i*be the fittest type; - Calculate, in terms of
*n*, the time for an infinite population to go from*x*_{i}= 1/*n*to*x*_{i}= 1-1/*n*under selection alone.

- Problem: method does not take into account genetic drift in finite populations.

**`Takeover Times' known in Population Genetics as Fixation Times
Keywords:
**

**Fixation:**- When only one variant remains in the populaton.
**Polymorphism:**- When more than one variant exists in the populaton.
**Fixation Time:**- Time until the population goes from polymorphism to fixation.
**Conditional Fixation Time:**- Time until fixation, given that the population fixes on specific genotype.
**Takeover Time:**- Time until the fittest type goes to fixation, given that the population fixes on it.

- Fisher, R. A. 1930.
*The genetical theory of natural selection.*Oxford: Clarendon Press. - Wright, S. 1931. Evolution in Mendelian populations.
*Genetics*16:97-159. - Kimura, M. and T. Ohta. 1969. The average number of generations until fixation of a mutant gene in a finite population.
*Genetics*61: 763-771. - Carr, R. N., and R. F. Nassar. 1970. Effects of selection and drift on the dynamics of finite populations. II. Expected time to fixation or loss of an allele.
*Biometrics*26: 221-227. - Ohta, T., and M. Kimura. 1972. Fixation time of overdominant alleles influenced by random fluctuation of selection intensity.
*Genetical Research*20: 1-7. - Nei, M., and A. K. Roychoudhury. 1973. Probability of fixation and mean fixation time of an overdominant mutation.
*Genetics*74: 371-380. - Nassar, R. F., and R. D. Cook. 1974.
Ultimate probability of fixation and time to fixation or loss of a gene under a variable fitness model.
*Theoretical and Applied Genetics*44: 247-254. - Ewens, W. J.. 1979.
*Mathematical Population Genetics.*Springer-Verlag, Berlin.

of a Fitter Allele

- Kimura, M. and T. Ohta. 1969. The average number of generations until fixation of a mutant gene in a finite population.
*Genetics*61: 763-771.

About this document ...