Improving XCS Performance on Overlapping Binary Problems

Extended classifier systems (XCS) suffer from suboptimal performance when the optimal classifiers of the functions they deal with overlap. As this overlap is the property of Boolean functions and the generalization capabilities of the ternary alphabet {0,1,#}, it is necessary to improve XCS to better deal with those functions that make up most of the possible Boolean functions. This paper proposes two techniques that improve XCS performance, both in terms of system and population state metrics. The first technique, termed Essentiality Assessment, alters the current fitness update mechanism by disallowing competition between potentially essential classifiers. The second technique, named Individualized Learning Rate, proposes an individually computed learning rate for each classifier based on the level of generality of each classifier. The results obtained show improvement and significance both in absolute and statistical terms, for the vast majority of system and population state metrics. This paper is a contribution toward improving XCS performance when dealing with single-step problems that necessarily require overlapping classifiers for their optimal solution.