|
|
|
|
|
|
|
taking on k values, then of the  distinct subsets of  only (k + 1)l can be defined by schemata. However, the question is not so much one of defining all possible subsets, as it is one of defining enough ''enriched" subsets, where an "enriched" subset is one which contains an above-average number of high-performance structures. |
|
|
|
|
|
|
|
|
It is instructive, then, to determine how many schemata (on the given representation) are "enriched" in the foregoing sense. Let contain x structures which are of interest at time t (because their performance exceeds the average by some specified amount). If the attributes are randomly distributed over structures, determination of "enrichment" is a straightforward combinatoric exercise. More precisely, let each di be a pseudo-random function and let Vi= {0, 1}, i = 1,. . . , l, so that a given structure  has property i (i.e., di(A) = 1) with probability ½. Under this arrangement peculiarities of the payoff function cannot bias concentration of exceptional structures in relation to schemata. |
|
|
|
|
|
|
|
|
Now, two exceptional structures can belong to the same schema only if they are assigned the same attributes on the same defining positions. If there are h defining positions this occurs with probability (½)h. For j exceptional structures, instead of 2, the probability is (1/2j-1)h. Since there are  ways of choosing h out of l detectors, and  ways of choosing j out of x exceptional structures, the expected number of schemata defined on h positions and containing exactly j exceptional structures is |
|
|
|
|
|
|
|
|
For example, with l = 40 and x = 105 (so that the density of exceptional structures is x/2l = 105/240@ 10-7), h = 20, and j = 10, this comes to |
|
|
|
|
|
|
|
|
Noting that a schema defined on 20 positions out of 40 has 220 = 106 instances, we see that the 10 exceptional structures occur with density 10-5, an "enrichment" factor of 100. A few additional calculations show that in excess of 20 schemata defined on 20 positions contain 10 or more exceptional structures. |
|
|
|
|
|
|
|
|
For given h and j, the "enrichment" factor rises steeply as l increases. On the other hand an increase in x (corresponding to an extension of interest to structures with performances not so far above the average) acts most directly on the expected number of schemata containing j structures. With an adequate number of pseudo-random functions as detectors (and a procedure for assuring that every combination of attributes designates a testable structure), the adaptive plan will have adequate grist for its mill. Stated another way, even when there can be no |
|
|
|
|
|
