|
|
|
|
|
|
|
means that simple schemata accumulate samples more rapidly. It is not difficult to show that the rate of accumulation falls off exponentially with the complexity. |
|
|
|
|
|
|
|
|
This automatic differential in sampling rates has a strong influence on what schemata play an important role in rule generation at any point in time. Early on, the system has reliable information only about simple schemata. But simple schemata usually only provide building blocks and estimates for coarse discriminations. Though the classifier system can exploit this information, rules built from these simple schemata are exposed to frequent surprises, departures, and exceptions in more complex contexts. Over time, the system gains more experience, and it gains information about more complicated schemata. This information biases the genetic algorithm toward the construction of more sophisticated, more specific rules. As a consequence, as the classifier system accumulates experience, it is prone to build hierarchies of rules of increasing specificity. These hierarchies grow from early "default" rules, based on simple contexts, to layers of "exception" rules based on later, more detailed contextual information. |
|
|
|
|
|
|
|
|
When simultaneous messages satisfy both a simpler default rule and a more complex exception rule, the latter tends to outcompete the former (though there can be complications; see Riolo's paper in Belew and Booker 1991). The higher specificity of the exception rule causes it to outbid the default rule if their strengths are comparable. The exception rule only survives under the bucket brigade if it corrects inappropriate actions of some default rule; otherwise, the strength of the exception rule diminishes until it is no longer a factor in the competition. When the exception rule does correct the default rule, a kind of symbiosis results. By saving the default rule from paying a bid in a situations where it would not make a profit, the exception rule actually helps the default rule to retain its strength. Thus both the default rule and the system as a whole are better off for the presence of the exception rule. |
|
|
|
|
|
|
|
|
Because successive layers of exception rules are only added as the necessary information becomes available, these rule hierarchies provide a sophisticated, incremental way of modeling the environment. The formal structures corresponding to these default hierarchies, called quasi-homomorphisms,have been defined and studied in Holland et al.(1986). |
|
|
|
|
|
|
|
|
Genetic algorithms have another critical effect on the development of classifier systems. Recombination, under the algorithm, discovers useful schemata for tags in just the way it discovers useful schemata for other parts of the rule. For example, a genetic algorithm can recombine parts of established tags to invent new tags. As a result, established tags spawn related tags, providing new clusters of rules, and new |
|
|
|
|
|