Smart crossover operator with multiple parents for a Pittsburgh learning classifier system

ABSTRACT

This paper proposes a new smart crossover operator for a Pittsburgh Learning Classifier System. This operator, unlike other recent LCS approaches of smart recombination, does not learn the structure of the domain, but it merges the rules of N parents (N ≥ 2) to generate a new offspring. This merge process uses an heuristic that selects the minimum subset of candidate rules that obtains maximum training accuracy. Moreover the operator also includes a rule pruning scheme to avoid the inclusion of over-specific rules, and to guarantee as much as possible the robust behaviour of the LCS. This operator takes advantage from the fact that each individual in a Pittsburgh LCS is a complete solution, and the system has a global view of the solution space that the proposed rule selection algorithm exploits. We have empirically evaluated this operator using a recent LCS called GAssist. First with the standard LCS benchmark, the 11 bits multiplexer, and later using 25 standard real datasets. The results of the experiments over these datasets indicate that the new operator manages to increase the accuracy of the system over the classical crossover in 16 of the 25 datasets, and never having a significantly worse performance than the classic operator.

REFERENCES

• 1: J. Bacardit. Pittsburgh Genetics-Based Machine Learning in the Data Mining era: Representations, generalization, and run-time. PhD thesis, Ramon Llull University, Barcelona, Catalonia, Spain, 2004. http://www.cs.nott.ac.uk/~jqb/publications/thesis.pdf.
• 2: Jaume Bacardit, Analysis of the initialization stage of a Pittsburgh approach learning classifier system, Proceedings of the 2005 conference on Genetic and evolutionary computation, June 25-29, 2005, Washington DC, USA [doi>10.1145/1068009.1068321]
• 3: C. Blake, E. Keogh, and C. Merz. UCI repository of machine learning databases, 1998. (www.ics.uci.edu/mlearn/MLRepository.html).
• 4: Martin Volker Butz , David E. Goldberg, Rule-based evolutionary online learning systems: learning bounds, classification, and prediction, University of Illinois at Urbana-Champaign, Champaign, IL, 2004
• 5: Kenneth A. De Jong , William M. Spears , Diana F. Gordon, Using Genetic Algorithms for Concept Learning, Machine Learning, v.13 n.2-3, p.161-188, Nov./Dec. 1993 [doi>10.1007/BF00993042]
• 6: David E. Goldberg, The Design of Innovation: Lessons from and for Competent Genetic Algorithms, Kluwer Academic Publishers, Norwell, MA, 2002
• 7: J. J. Grefenstette. Lamarckian learning in multi-agent environments. In Proceedings of the Fourth International Conference on Genetic Algorithms, pages 303--310. Morgan Kaufmann, 1991.
• 8: G. Harik. Linkage learning via probabilistic modeling in the ecga, 1999.
• 9: G. R. Harik, F. G. Lobo, and D. E. Goldberg. The compact genetic algorithm. IEEE-EC, 3(4):287, November 1999.
• 10: P. Larranaga and J. Lozano, editors. Estimation of Distribution Algorithms, A New Tool for Evolutionnary Computation. Genetic Algorithms and Evolutionnary Computation. Kluwer Academic Publishers, 2002.
• 11: Xavier Llorà , Kumara Sastry , David E. Goldberg, The compact classifier system: motivation, analysis, and first results, Proceedings of the 2005 conference on Genetic and evolutionary computation, June 25-29, 2005, Washington DC, USA [doi>10.1145/1068009.1068328]
• 12: M. Pelikan, D. E. Goldberg, and E. Cantú-Paz. BOA: The Bayesian optimization algorithm. In Proceedings of the Genetic and Evolutionary Computation Conference GECCO-99, volume I, pages 525--532. Morgan Kaufmann, 1999.
• 13: J. Rissanen. Modeling by shortest data description. Automatica, vol. 14:465--471, 1978.
• 14: M. Stout, J. Bacardit, J. Hirst, N. Krasnogor, and J. Blazewicz. From hp lattice models to real proteins: coordination number prediction using learning classifier systems. In 4th European Workshop on Evolutionary Computation and Machine Learning in Bioinformatics 2006 (to appear), 2006.
• 15: S. W. Wilson. Classifier fitness based on accuracy. Evolutionary Computation, 3(2):149--175, 1995.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.6 Learning
          Subjects: Concept learning

Additional Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.6 Learning
          Subjects: Induction

General Terms:
Algorithms, Experimentation, Performance

Keywords:
evolutionary algorithms, learning classifier systems, rule induction, smart crossover operator