Rule -Based Evolutionary Online Learning Systems: Learning Bounds, Classification, and Prediction

277 p.Thesis (Ph.D.)--University of Illinois at Urbana-Champaign, 2004.Rule-based evolutionary online learning systems, often referred to as Michigan-style learning classifier systems (LCSs), were proposed nearly thirty years ago (Holland, 1976; Holland, 1977) originally calling them cognitive systems. LCSs combine the strength of reinforcement learning with the generalization capabilities of genetic algorithms promising a flexible, online generalizing, solely reinforcement dependent learning system. However, despite several initial successful applications of LCSs and their interesting relations with animal learning and cognition, understanding of the systems remained somewhat obscured. Questions concerning learning complexity or convergence remained unanswered. Performance in different problem types, problem structures, concept spaces, and hypothesis spaces stayed nearly unpredictable. This thesis has the following three major objectives: (1) to establish a facetwise theory approach for LCSs that promotes system analysis, understanding, and design; (2) to analyze, evaluate, and enhance the XCS classifier system (Wilson, 1995) by the means of the facetwise approach establishing a fundamental XCS learning theory; (3) to identify both the major advantages of an LCS-based learning approach as well as the most promising potential application areas. Achieving these three objectives leads to a rigorous understanding of LCS functioning that enables the successful application of LCSs to diverse problem types and problem domains. The quantitative analysis of XCS shows that the interactive, evolutionary-based online learning mechanism works machine learning competitively yielding a low-order polynomial learning complexity. Moreover, the facetwise analysis approach facilitates the successful design of more advanced LCSs including Holland's originally envisioned cognitive systems.U of I OnlyRestricted to the U of I community idenfinitely during batch ingest of legacy ETD