Extending XCS with Cyclic Graphs for Scalability on Complex Boolean Problems | JoVE Visualize

Area of Science:

Evolutionary Machine Learning
Artificial Intelligence
Computational Intelligence

Background:

Scalable classifier systems are crucial for high-dimensional problems in evolutionary machine learning.
Existing methods like XCSCFC face limitations with deep problem hierarchies and lack cyclic representations.
Evolving finite state machines (FSMs) is challenging due to combinatorial complexity, often requiring supervised learning or subsampling.

Purpose of the Study:

To introduce a novel state-machine-based encoding scheme into XCS (XCSSMA) to overcome limitations of existing scalable classifier systems.
To enhance the ability of evolutionary algorithms to handle problems with inherent cyclic structures.
To develop a more computationally efficient and scalable approach for high-dimensional classification tasks.

Main Methods:

Integration of a state-machine-based encoding scheme into the XCS (eXternal Classifier System) framework, creating XCSSMA.
Systematic testing of XCSSMA on six complex Boolean problem domains: multiplexer, majority-on, carry, even-parity, count ones, and digital design verification.
Comparative performance analysis against established XCS variants (XCSCFA and XCSF).

Main Results:

XCSSMA outperformed XCSCFA and XCSF in three of the six tested Boolean problem domains, with similar performance in others.
The system successfully evolved compact, human-readable general classifiers for the even-parity and carry problems.
Demonstrated the capability of XCSSMA to produce scalable solutions by effectively utilizing cyclic representations inherent in state machines.

Conclusions:

XCSSMA represents a significant advancement in scalable classifier systems by incorporating cyclic representations through state-machine encoding.
The approach shows promise for tackling complex, high-dimensional problems where hierarchical or cyclic structures are prevalent.
Future work may focus on further optimizing XCSSMA for broader applications and exploring its potential in other domains requiring state-based learning.