|
|
|
|
|
|
|
Once again f(x) of Figure 10 provides a simple illustration. New instances of a schema such as  increase confidence that the observed average  of evaluations of f(x) for selected  approaches  . At the same time an instance of some previously untried schema, say  , allows a plan of type  to exploit the new schema (by giving it high rank) if it is above average. |
|
|
|
|
|
|
|
|
In modifying the pool of schemata, crossing-over gains tremendous power from its intrinsic parallelism. Each crossing-over affects great numbers of schemata, as established by the following: |
|
|
|
|
|
|
|
|
LEMMA 6.2.1: Let A = a1a2 . . . al and  differ in attribute values at x' positions to the left of x + 1 and x" positions to the right of x. Then either resultant of a single crossing-over of A with A' at x will be an instance of   "new" schemata (instanced by neither A nor A'). It will also be a new instance of  schemata already instanced by A or A' (assuming x' ¹ 0 and x" ¹ 0). |
|
|
|
|
|
|
|
|
Proof: After crossing-over, any schema which is defined at one or more of the x' positions on the left and at one or more of the x" positions on the right will have neither A nor A' as an instance. On the left there are 2x' - 1 ways of combining one or more of the x' attribute values with " "; similarly there are 2x'' - 1 ways on the right; at the other l - (x' + x") positions either an attribute value or a '' " is allowable without restriction. Thus there are   "new" schemata of which the resultant is an instance. |
|
|
|
|
|
|
|
|
If x' > 0 and x" > 0 the remainder of the 2l schemata instanced by the resultant, i.e., 2l-x' + 2l-x" - 2l-(x'+x"), will have a new instance (though they are not "new" schemata) since the resultant must differ by at least one attribute value from both A and A'. Q.E.D. |
|
|
|
|
|
|
|
|
In other words each of the 2l schemata instanced by the resultant arises from a potentially useful manipulation of schemata already in the pool (those instanced by A and A'). Note also that, even when l is only 20, a single operation is processing over a million schemata! |
|
|
|
|
|
|
|
|
We can gain additional insight concerning crossing-over by considering its effect, over an extended interval, on the whole pool of schemata in  . In the absence of reproduction and other operators, crossing-over generates a kind of diffusion from the pool to schemata not represented therein. More precisely, |
|
|
|
|
|