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

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.

Name thesis:degree_name

Ph.D.

Level thesis:degree_level

Dissertation

Discipline thesis:degree_discipline

Computer Science

Grantor

University of Illinois at Urbana-Champaign

Year dc:date

2015

Author dc:creator

• Butz, Martin Volker

Contributors dc:contributor

• Goldberg, David E.

• Computer Science

Language dc:language

eng

Identifier

(MiAaPQ)AAI3153259

OAI identifier oai:identifier

oai:www.ideals.illinois.edu:2142/81646