|
|
|
|
|
|
|
THEOREM 5.1 (large deviations): The optimal allocation of trials n* to the observed second best of the two random variables corresponding to the 2-armed bandit problem is given by |
|
|
|
|
|
|
|
|
This theorem actually goes a step further than the original version, directly providing a "realizable plan" for sample allocation. The original version was based on a "ideal" plan that could not be directly realized, requiring section 5.2 to show that the losses of the ideal plan could be approached by the losses of an associated "realizable" plan. Section 5.2 is now superfluous. |
|
|
|
|
|
|
|
|
The revised constants for the realizable plan do not affect results in later chapters, because the further analysis of genetic algorithm performance does not depend upon the exact values for the constants. The basic point is that genetic algorithms allocate trials exponentially to the random variables (schemata) corresponding to the arms of an n-armed bandit. Coefficients may vary among schemata, but the implicit parallelism of a genetic algorithm is enough to dominate any differences in the coefficients. |
|
|
|
|
|
|
|
|
There are two other errors that may trouble the close reader, though they are much less important. The first error occurs, at the top of page 71, in the example giving estimated values for schemata. x(3) should be .1000010 . . . 0, with the consequence that |
|
|
|
|
|
|
|
|
The second error occurs, on page 103, in the discussion of the effect of crossover on the increase of schemata. In the derivation just below the middle of the page, the approximation 1/(1-c) ³ 1+ c, for c £ 1, is invoked. But this approximation is in the wrong direction for preserving the inequality for  ;therefore the line that follows the mention of this approximation should be deleted. |
|
|
|
|
|
|
|
|
Finally there is a point of emphasis that may be troublesome. In the discussion of the role of payoff in the formal framework, near the bottom of page 25, the mapping allows the payoff to be any real number, positive or negative. It would have helped the reader to say that payoff is treated as a nonnegative quantity throughout the book, particularly in the discussion of genetic algorithms. |
|
|
|
|
|
