Theoretical adaptation of multiple rule-generation in XCS

Most versions of the XCS Classifier System have been designed to evolve only two rules for each rule discovery invocation, which restricts the search capacity. A difficulty behind generating multiple rules each time is the increase in the probability of deleting immature rules, which conflicts with the requirement that parent rules be sufficiently updated so that fitness represents worth. Thus the aim of this paper is to argue how XCS determines when rules can be deleted safely. The objectives are to certainly identify inaccurate rules and then to maximize how many rules XCS can generate. The proposed method enables adaptation of rule-generation that maximizes the number of generated rules, under the assumption that the reliably inaccurate rules can be replaced with new rules. Experiments show our modification strongly improves the XCS performance on large scale problems, since it can take advantage of multi-point search more efficiently. For example, on the 135-bit multiplexer problem, XCS with our modification requires 1.57 million less training inputs compared with the standard XCS while utilizing the same number of final rules.