|
|
|
|
|
|
|
Substituting for (t - t0 + 1) in the previous expression we get |
|
|
|
|
|
|
|
|
This lemma holds a fortiori for any schema x consistently exhibiting an effective rate of increase at least equal to 1, i.e.,  , over the interval (t0, t). As noted first in sections 6.2 and 6.3, when l(x)/l is small,  will be small and the factor  will be very close to one. Let x* denote a schema which consistently yields the best observed performance  , among the schemata which persist over that interval. In all but unusual circumstances  will exceed  by more than the factor . If l is large this is the more certain since, until the adaptation is far advanced, l(x)/l will with overwhelming probability be smallsee the discussion at the end of section 6.2. Thus, for any x* for which µx* significantly exceeds  , the number of trials  allocated to x* is an exponential function of  . |
|
|
|
|
|
|
|
|
(For natural systems the reproduction rate is determined by the environmentcf. fitness in geneticshence it cannot be manipulated as a parameter of the adaptive system. However, for artificial systems this is not the case; the adaptive plan can manipulate the observed performance, as a piece of data, to produce more efficient adaptation. In particular, the reproductive step of  algorithms, step 4, can be modified to assure that the reproduction rate of x* automatically exceeds  |
|
|
|
|
|
|
|
|
From all of this it is clear that, whatever the complexity of the function µ, plans of type behave in a way much like that dictated by the optimal allocation criterion: the number of trials allocated to the observed best increasing as an exponential function of the total number of trials nx* allocated to structures which are not instances of x*. However we can learn a good deal more by comparing the expected loss per trial of the genetic plans to the loss rate under optimal allocation. Theorem 5.3 established a lower bound |
|
|
|
|
|
|
|
|
for the expected loss under optimal allocation, where b = s1/(µx* - µr). For the genetic plan, the expected loss per trial is bounded above by |
|
|
|
|
|
|
|
|
where r' is the number of schemata which have received n' or more trials under the genetic plan, and, as in Theorem 5.3, q(Nx*, n') is the probability that a given option other than x* is observed as best. (This expression is simply L'Nr from |
|
|
|
|
|
