Finite Population Model

The infinite-population case involves deterministic transitions from to /-'i/~ lj and thus from to

—in an infinite population there are no sampling errors. In contrast, modeling a finite population requires taking account of the stochastic effects of sampling.

To address the finite-population case, Nix and Vose (1991) modeled the simple GA as a Markov chain. Markov chains are stochastic processes in which the probability that the process will be in state j at time t depends only on the state i at time t 1. Many processes in nature can be described as Markov chains. (For an introduction to the mathematics of Markov chains see Feller 1968.)

A "state" of a finite-population GA is simply a particular finite population. The set of all states is the set of possible populations of size n. These can be enumerated in some canonical order and indexed by i. Nix and Vose represent the ith such population as a vector <t>i of length 2l. The yth element of <t>i is the number of occurrences of string y in population Pi. It is clear that under the simple GA the current population Pj depends (stochastically) only on the population at the previous generation. Thus, the GA can be modeled as a Markov chain.

To construct such a model, we need to write down the probability of going from any given population to any other under the simple GA. The set of all possible populations of size n can be represented by a giant matrix, Z, in which the columns are all possible population vectors . How many possible populations of size n are there? The answer is

(Deriving this is left as an exercise.) A given element Zy,i of Z is the number of occurrences of string y in population i.

Here is a simple example of constructing the Z matrix: Let l = 2 and n = 2. The possible populations are

The array Z is

The array Z is

A state for the Markov chain corresponds to a column of Z.

The next step is to set up a Markov transition matrix Q.Q is an N x Nmatrix, and each element Qj is the probability that population Pj will be produced from population Pi under the simple GA. Once this matrix is defined, it can be used to derive some properties of the GA's behavior.

Writing down the transition probabilities Q/,j is a bit complicated but instructive. Let p(y) be the probability that string y will be generated from the selection and recombination process (i.e., steps 3 and 4) of the simple GA acting on population P. The number of occurrences of string y in population Pj is Zy,j, so the probability that the correct number comes from population Pj is simply the probability that Zy,j occurrences of y are produced from population P. This is equal to the probability that y is produced on Zy,j different selection-and-recombination steps times the number of ways in which these Zy,j different selection-and-recombination steps can occur during the total n selection-and-reproduction steps. Following

Nix and Vose, we will enumerate this for each possible string.

The number of ways of choosing Zg,j occurrences of string 0 for the Z0,j slots in population j is

Selecting string 0 Z0,j times leaves n Z 0,j positions to fill in the new population. The number of ways of placing the Zj,j occurrences of string 1 in the n Z 0,j positions is

Continuing this process, we can write down an expression for all possible ways of forming population Pj from a set of n selection-and-recombination steps:

To form this expression, we enumerated the strings in order from 0 to 2l 1. It is not hard to show that performing this calculation using a different order of strings yields the same answer.

The probability that the correct number of occurrences of each string y (in population Pjj) is produced (from population Pi) is

The probability that population Pj is produced from population Pi is the product of the previous two expressions (forming a multinomial distribution):

The only thing remaining to do is derive an expression for pi(y), the probability that string y will be produced from a single selection-and-recombination step acting on population Pi. To do this, we can use the matrices F and 1 i defined above. pi(y) is simply the expected proportion of string y in the population produced from Pj under the simple GA. The proportion of y in Pi is ( , where denotes the sum of the components of vector and (A)y denotes the yth component of vector . The probability that y will be selected at each selection step is and the expected proportion of string y in the next population is

Since piiy) is equivalent to the expected proportion of string y in the next population, we can finally write down a finished expression for Qi,j.

The matrix Qi,j gives an exact model of the simple GA acting on finite populations.

Nix and Vose used the theory of Markov chains to prove a number of results about this model. They showed, for example, that as n ' , the trajectories of the Markov chain converge to the iterates of G (or G p) with probability arbitrarily close to 1. This means that for very large n the infinite-population model comes close to mimicking the behavior of the finite-population GA. They also showed that, if Gp has a single fixed point, as n ' the GA asymptotically spends all its time at that fixed point. If G p has more than one fixed point, then as n ' , the time the GA spends away from the fixed points asymptotically goes to 0. For details of the proofs of these assertions, see Nix and Vose 1991.

Vose (1993) extended both the infinite-population model and the finite-population model. He gave a geometric interpretation to these models by defining the "GA surface" on which population trajectories occur. I will not give the details of his extended model here, but the main result was a conjecture that, as n ' , the fraction of the time the GA spends close to nonstable fixed points asymptotically goes to 0 and the time the GA spends close to stable fixed points asymptotically goes to 1. In dynamical systems terms, the GA is asymptotically most likely to be at the fixed points having the largest basins of attraction. As n ' , the probability that the GA will be anywhere else goes to 0. Vose's conjecture implies that the short-term behavior of the GA is determined by the initial population—this determines which fixed point the GA initially approaches—but the long-term behavior is determined only by the structure of the GA surface, which determines which fixed points have the largest basins of attraction.

What are these types of formal models good for? Since they are the most detailed possible models of the simple GA, in principle they could be used to predict every aspect of the GA's behavior. However, in practice such models cannot be used to predict the GA's detailed behavior for the very reason that they are so detailed—the required matrices are intractably large. For example, even for a very modest GA with, say,/ = 8 and n = 8, Nix and Vose's Markov transition matrix Q would have more than 1029 entries; this number grows very fast with l and n. The calculations for making detailed predictions simply cannot be done with matrices of this size.

This does not mean that such models are useless. As we have seen, there are some less detailed properties that can be derived from these models, such as properties of the fixed-point structure of the "GA surface" and properties of the asymptotic behavior of the GA with respect to these fixed points. Such properties give us some limited insight into the GA's behavior. Many of the properties discussed by Vose and his colleagues are still conjectures; there is as yet no detailed understanding of the nature of the GA surface when F and 1 are combined. Understanding this surface is a worthwhile (and still open) endeavor.

Fitness Resolution Fortress

Fitness Resolution Fortress

Learning About Fitness Resolution Fortress Can Have Amazing Benefits For Your Life And Success! Start Planning To Have Excellent Health And Fitness Today!

Get My Free Ebook


Post a comment