XCS-DH: Minimal default hierarchies in XCS

摘要

A default hierarchy is set of rules containing one or more exceptions to one or more default rules e.g. all dogs are friendly, except my neighbour's. Default hierarchies were the subject of considerable interest in early Learning Classifier Systems research, but they were abandoned due to the considerable difficulty of solving the credit assignment problems they involve. The most popular Learning Classifier System, XCS, and its derivatives do not support default hierarchies because in XCS each rule must be accurate, whereas in a default hierarchy an overgeneral rule may be overridden by a correct rule. In this work we enable XCS to evolve minimal default hierarchies by allowing two conditions in one rule, but evaluating only the accuracy and fitness of the whole as a whole. This simple step avoids the credit assignment issues faced by earlier systems. We call this XCS-DH. Preliminary evaluation of XCS-DH on a number of Boolean functions indicates a strong tendency to exploit the increased expressiveness of its rules. On some functions we observe slower learning and a larger population size, which we attribute to the increased rule expressiveness, which increases the search space. However, we also observe that in a problem that is particularly suitable for XCS-DH representation, and that is sufficient difficult for XCS, XCS-DH's learning rate is faster than XCS's. We take this as confirmation of the potential of learning default hierarchies with XCS-DH.