|
|
|
|
|
|
|
from some predetermined set U to each structure  (see section 2.1) and successive trials of the same structure will in general yield different performances. (For clarity, this stochastic effect is treated explicitly here, rather than using the formally equivalent approach of subsuming the effect in the stochastic action of the operators.) It will be assumed that each random variable in U has a well-defined mean and variance. |
|
|
|
|
|
|
|
|
The study below shows that the algorithm works well and efficiently when is small (e.g., when has two elements as in the two-armed bandit problem) as well as when is large. When  is small relative to M the genetic operators are unimportant, replication alone (step 4) being adequate to the task. However the algorithm's power is most evident when it is confronted with problems involving high dimensionality (hundreds to hundreds of thousands of attributes, as in genetics and economics) and multitudes of local optima. Computational mathematics has little to offer at present toward the solution of such problems and, when they arise in a natural context, they are consistently a barrier to understanding. For this reason it will be helpful in evaluating the algorithm to keep in mind the case where (and  as well) is a very large set, finite only by virtue of a limited ability to distinguish its elements (e.g., because the detectors have a limited resolution). The ultimate finiteness of is convenient, since then the number of attributes or detectors l can be held fixed, but it is not essential. Chapter 8 will discuss the changes required when l is an unbounded function of t. |
|
|
|
|
|
|
|
|
That step 5.3 assures continued testing of all alleles in all contexts follows from |
|
|
|
|
|
|
|
|
LEMMA 7.1: Under algorithms of type  the expected number of trials of the jth value for the ith attribute (i.e., allele j of detector i), for any i and j, is infinite. |
|
|
|
|
|
|
|
|
Proof: (Essentially this proof is a specialized version of the Borel zero-one criterion.) Let Pij(t) be the probability of occurrence at time t of vij, the jth value for the ith attribute. Then  is the expected number of occurrences of vij over the history of the system. Unless StPij(t)M is infinite, vij can be expected to occur only a finite number of times. That is, unless StPij(t)M is infinite, vij will at best be tested only a finite number of times in each context, and it may not be tested at all in some contexts. (Despite this a plan for which StPij(t)M is large relative to the size of may be quite interesting in practical circumstances.) |
|
|
|
|
|
|
|
|
Since Stct® ¥, we have Stct1PM® ¥. But Pij(t)³ ct1PMM for all t, whence StPij(t)M ³Stct1PMM. Hence StPij(t)M is also infinite in the limit.
Q.E.D. |
|
|
|
|
|