|
|
|
|
|
|
|
couplings between established clusters. Tags survive (or, more carefully, the rules using them survive) if they contribute to useful interactions. Under these evolutionary pressures, the tags develop into a system of experience-based "symbols" for interior use (cf. Hofstadter's [1979] concept of an "active symbol"). The associations provided by these tags flesh out the default hierarchy models. The resulting structures can be quite sophisticated, enabling the system to model new situations by coupling appropriate clusters of established (strong) rules. Moreover, these models can be used in a ''lookahead" fashion, permitting the classifier system to act in anticipatory fashion, selecting actions on the basis of future consequences. The interested reader is referred to Holland 1991 and Riolo 1990. |
|
|
|
|
|
|
|
|
Each of the mechanisms used by the classifier system has been designed to enable the system to continue to adapt to its environment, while using the capabilities it already has to respond instant-by-instant to that environment. In so doing the system is constantly trying to balance exploration (acquisition of new information and capabilities) with exploitation (the efficient use of information and capabilities already available). |
|
|
|
|
|
|
|
|
2. The Optimal Allocation of Trials Revisited |
|
|
|
|
|
|
|
|
Pride of place in the correction category belongs to Dan Frantz's work on one of the main motivating theorems in the book, Theorem 5.1. This theorem concerns the "optimal" allocation of trials in determining which of two random variables has a higher expected value (the well known 2-armed bandit problem). In chapter 5, an "optimal" solution is a solution that minimizes the losses incurred by drawing samples from the random variable of lower expectation. The theorem there shows that these losses are minimized if the number of trials allocated to the random variable with the highest observed expectation increases exponentially relative to the number of trials allocated to the observed second best. |
|
|
|
|
|
|
|
|
Because schemata can be looked upon as random variables, this result illuminates the treatment of schemata under a genetic algorithm (née genetic plan in chapter 7). Under a genetic algorithm, a schema with an above-average fitness in the population increases its proportion exponentially (until its instances constitute a significant fraction of the total population). If we think of the genetic algorithm as generating samples of n random variables (an n-armed bandit), in a search for the best, then this exponential increase is just what Theorem 5.1 suggests it should be. |
|
|
|
|
|
|
|
|
The problem with the proof of the theorem, as given, turns on its particular |
|
|
|
|
|