|
|
|
|
|
|
|
as N increases. (This comparison yields a lower bound on the ratio since the upper bound in one case is being compared to the lower bound in the other. It can be established easily, on comparison of the respective first terms of the two expressions, that the condition on n' is sufficient to assure that the first term of  is always less than the first term of  . It should be noted that the condition on n' can be made as weak as desired by simply choosing nx*,0(0) large enough.) |
|
|
|
|
|
|
|
|
To proceed, substitute the explicit expressions derived earlier for nx*,0 (Lemma 7.3) and m* (Theorem 5.3) in the ratio  , yielding |
|
|
|
|
|
|
|
|
Simplifying and deleting terms which do not affect the direction of the inequality we get |
|
|
|
|
|
|
|
|
 |
|
|
|
|
|
|
|
|
 |
|
|
|
|
|
|
|
|
Thus algorithms of type  effectively exploit their intrinsic parallelism, however intricate the assignment of payoff µ(A) to structures  , reducing their losses by a factor r' in comparison to one-schema-at-a-time searches. We can get some idea of the size of r' by referring to the last few paragraphs of chapter 4. Given a representation produced by l = 32 detectors with k = 2 values (''alleles") each, r' > 9000 when N = 32 and n' = 8 (with all elements of a equally likely, i.e., b0 = g0 = 1). This is a startling "speed-up" for a space which is, after all, small relative to the a spaces in, say, genetics or economics which may involve chromosomes or goods vectors with l » 100. Even small increases in N, or decreases in n' produce dramatic increases in r'; similar increases result from increases in l. Increases in l may result from representing a larger space  , or they may be deliberately introduced for a given (either by selecting k' < k, so that  necessitates l' > l, or else by using additional [redundant] detectors). |
|
|
|
|
|
|
|
|
To get a better picture of the implications of Lemma 7.2 and Theorem 7.4 let us look at two applications. Once again, as in chapter 1, one application is to |
|
|
|
|
|
