|
|
|
|
|
|
|
repeated application of crossing-over to the individuals in  yields a "steady state" wherein, at any instant (time-step), each schema x has a well-defined probability of occurrence l(x). It follows that the expected interval between occurrences of x will be just the reciprocal 1/l(x) of this probability. Thus, if the proportions of schemata in are not far removed from steady-state values, 1/l(x) is a reasonable measure of the expected time to an occurrence of x. Of course, no actively adapting system (natural or artificial) following a plan of type  will even begin to approach the steady state. Under such a plan, the steady state is continually "modulated" by changes in the number of instances of various x resulting from reproduction according to  . In effect, with reproduction added, 1/l(x) is a continually changing "background'' testing rate, giving at any time a rough estimate of the expected time to first occurrence of x. These ideas, together with values for l(x) are established rigorously by |
|
|
|
|
|
|
|
|
LEMMA 6.2.2: Repeated crossing-over (with uniform random pairing of individuals and in the absence of other operators) in a population  yields a "steady state" (i.e., a fixed point of the stochastic transformation) in which each schema x occurs with probability l(x) = IIjP(jx) where P(jx) is the overall proportion in of the allele occurring at the jth position of x(if a " " occurs at the jth position take P(jx) = 1). |
|
|
|
|
|
|
|
|
Proof: Let xx1 and xx2be the resultants of a crossing-over of x1 and x2 at point x. Then a crossing-over of the resultants xx1 and xx2at point x will bring back x1 and x2 (i.e., as may be determined directly from its definition, the crossover operator is self-dual). |
|
|
|
|
|
|
|
|
Letting P(x)designate the proportion of (instances of) x in  ,we have P(x1)P(x2)as the probability that x1 will be paired with x2 for crossing-over (under uniform random pairing). Thus the probability that xx1, xx2 arise from a crossing-over of x1, x2 at x is P(x1)P(x2)Px, where Pxis the probability that crossover takes place at x. |
|
|
|
|
|
|
|
|
Similarly the probability of a reversion (x1, x2arising from xx1, xx2by crossover at x)is P(xx1)P(xx2)Px. |
|
|
|
|
|
|
|
|
Considering only the effects of crossing-over at x on the pairs x1, x2and xx1, xx2, there will be no changes in their probabilities of occurrence if |
|
|
|
|
|
|
|
|
If (and only if) such an equation holds for every x and every ordered quadruple (x1, x2, xx1, xx2) will there be no change in the probability of occurrence of any schema. |
|
|
|
|
|
