An approach to analyze the evolution of symbolic conditions in learning classifier systems

ABSTRACT

In this paper, we introduce an approach for the identification of building blocks in symbolic expressions and apply it to analyze the emergence of building blocks in XCS with symbolic representation. The objective is to extract from a sequence of evolving populations a set of recurrent patterns which identifies pieces of the problem solution, so to track the emergence of the optimal solution. This permits the introduction of better measures of performance which might be useful in diagnosing problems and adapting algorithms.

REFERENCES

• 1: Martin V.Butz, Tim Kovacs, Pier Luca Lanzi, and Stewart W. Wilson. Toward a theory of generalization and learning in xcs. IEEE Transaction on Evolutionary Computation 8(1):28--46, February 2004.
• 2: John R. Koza. Hierarchical automatic function definition in genetic programming. In L. Darrell Whitley, editor, Foundations of Genetic Algorithms 2 pages 297--318, Vail, Colorado, USA, 24-29 1992. Morgan Kaufmann.
• 3: Pier Luca Lanzi and Alessandro Perrucci. Extending the Representation of Classifier Conditions Part II: From Messy Coding to S-Expressions. In Banzhaf the Genetic and Evolutionary Computation Conference (GECCO 99) pages 345--352, Orlando (FL), July 1999. Morgan Kaufmann.
• 4: Wolfram Research. Mathematica 5. http://www.wolfram.com.
• 5: Stefano Rocca and Stefania Solari. Building blocks analysis and exploitation in genetic programming. Master's thesis, April 2006. Master thesis supervisor: Prof. Pier Luca Lanzi.
• 6: Stewart W. Wilson. Classifier Fitness Based on Accuracy. Evolutionary Computation 3(2):149--175, 1995. http://prediction-dynamics.com/.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.1 Models of Computation

General Terms:
Algorithms, Performance

Keywords:
LCS, XCS, representation, symbolic conditions