Learning Optimality Theory for Accuracy-Based Learning Classifier Systems
Masaya Nakata, Will N. Browne
Abstract
Evolutionary computation has brought great progress to rule-based learning but this progress is often blind to the optimality of the system design. This article theoretically reveals an optimal learning scheme on the most popular evolutionary rule-based learning approach-the accuracy-based classifier system (or XCS). XCS seeks to form accurate, maximally general rules that together classify the state space of a given domain. Previously, setting up the system to perform well has been a “blackart” as no systematic approach to XCS parameter tuning existed. We derive a theoretical approach that mathematically guarantees that XCS identifies the accurate rules, which also returns a theoretically valid XCS parameter setting. Then, we demonstrate our theoretical setting derives the maximum correctness of rule-identification in the fewest iterations possible. We also experimentally show that our theoretical setting enables XCS to easily solve several challenging problems where it had previously struggled.