Generalized classifier system: Evolving classifiers with cyclic conditions

Accuracy-based XCS classifier system has been shown to evolve classifiers with accurate and maximally general characteristics. XCS generally represents its classifiers with binary conditions encoded in a ternary alphabet, i.e., {0,1, #}, where # is a 'don't care' symbol, which can match with 0 and 1 in inputs. This provides one of the foundations to make XCS evolve an optimal population of classifiers, where each classifier has the possibility to cover a set of perceptions. However, when performing XCS to solve the multi-step problems, i.e., maze control problems, the classifiers only allow the agent to perceive its surrounding environments without the direction information, which are contrary to our human perception. This paper develops an extension of XCS by introducing cyclic conditions to represent the classifiers. The proposed system, named generalized XCS classifier system (GXCS), is dedicated to modify the forms of the classifiers from chains to cycles, which allows them to match with more adjacent environments perceived by the agent from different directions. Accordingly, a more compact population of classifiers can be evolved to perform the generalization feature of GXCS. As a first step of this research, GXCS has been tested on the benchmark maze control problems in which the agent can perceive its 8 surrounding cells. It is confirmed that GXCS can evolve the classifiers with cyclic conditions to successfully solve the problems as XCS, but with much smaller population size.