Fast fitness implementation of multiplexer problems for Pittsburgh LCS
by Xavier Llorà (2006). IlliGAL TR No 2006017. Link to the PDF.
Abstract
This technical report describes how to compute the fitness of a rule for an arbitrary size multiplexer without doing any instance matching. Pittsburgh-style learning classifier systems require the accuracy and the error of a rule to compute a fitness that promotes maximally accurate and maximally general rules. The accuracy (α) may be computed as the proportion of overall examples correctly classified, and the error (ε) is the proportion of incorrect classifications issued. Once the accuracy and error of a rule are known, the fitness can be computed as f(r)=α(r)*ε(r). This technical note shows how to computed the fitness only by inspecting the rule, requiring a time proportional to number of possible address values O(2^|a|) instead of the O(2^l) that requires a traditional rule matching strategy against all the possible instances. The proposed method makes tractable for Pittsburgh learning classifier systems multiplexer problems larger than the 11-input one.