research-article

An analysis of matching in learning classifier systems

Authors:

Martin V. Butz,

Pier Luca Lanzi,

Daniele LoiaconoAuthors Info & Claims

GECCO '08: Proceedings of the 10th annual conference on Genetic and evolutionary computation

Pages 1349 - 1356

https://doi.org/10.1145/1389095.1389359

Published: 12 July 2008 Publication History

Abstract

We investigate rule matching in learning classifier systems for problems involving binary and real inputs. We consider three rule encodings: the widely used character-based encoding, a specificity-based encoding, and a binary encoding used in Alecsys. We compare the performance of the three algorithms both on matching alone and on typical test problems. The results on matching alone show that the population generality influences the performance of the matching algorithms based on string representations in different ways. Character-based encoding becomes slower and slower as generality increases, specificity-based encoding becomes faster and faster as generality increases. The results on typical test problems show that the specificity-based representation can halve the time required for matching but also that binary encoding is about ten times faster on the most difficult problems. Moreover, we extend specificity-based encoding to real-inputs and propose an algorithm that can halve the time require for matching real inputs using an interval-based representation.

References

[1]

E. Bernadó-Mansilla and T. K. Ho. Domain of competence of XCS classifier system in complexity measurement space. IEEE Trans. Evolutionary Computation, 9(1):82--104, 2005.]]

Digital Library

[2]

M. V. Butz. XCS (+ tournament selection) classifier system implementation in c, version 1.2. Technical Report 2003023, Illinois Genetic Algorithms Laboratory -- University of Illinois at Urbana-Champaign, 2003.]]

[3]

M. V. Butz. Kernel-based, ellipsoidal conditions in the real-valued XCS classifier system. In H.-G. Beyer and U.-M. O'Reilly, editors, GECCO, pages 1835--1842. ACM, 2005.]]

Digital Library

[4]

M. V. Butz. Rule-Based Evolutionary Online Learning Systems: A Principled Approach to LCS Analysis and Design. Studies in Fuzziness and Soft Computing. Springer Verlag, Berlin-Heidelberg, Germany, 2006.]]

[5]

M. V. Butz, T. Kovacs, P. L. Lanzi, and S. W. Wilson. Toward a theory of generalization and learning in XCS. IEEE Transaction on Evolutionary Computation, 8(1):28--46, Feb. 2004.]]

Digital Library

[6]

M. V. Butz, P. L. Lanzi, and S. W. Wilson. Hyper-ellipsoidal conditions in XCS: rotation, linear approximation, and solution structure. In Cattolico {8}, pages 1457--1464.]]

Digital Library

[7]

M. V. Butz and S. W. Wilson. An algorithmic description of XCS. Journal of Soft Computing, 6(3-4):144--153, 2002.]]

[8]

M. Cattolico, editor. Genetic and Evolutionary Computation Conference, GECCO 2006, Proceedings, Seattle, Washington, USA, July 8-12, 2006. ACM, 2006.]]

[9]

M. Dorigo and M. Colombetti. Robot Shaping: An Experiment in Behavior Engineering. MIT Press/Bradford Books, 1998.]]

Digital Library

[10]

D. E. Goldberg. Genetic Algorithms in Search, Optimization, and Machine Learning. Addison-Wesley, Reading, Mass., 1989.]]

Digital Library

[11]

J. H. Holland and J. S. Reitman. Cognitive systems based on adaptive algorithms. 1978. Reprinted in: Evolutionary Computation. The Fossil Record. David B. Fogel (Ed.) IEEE Press, 1998. ISBN: 0-7803-3481-7.]]

[12]

K. A. D. Jong and W. M. Spears. Learning Concept Classification Rules using Genetic Algorithms. In Proceedings of the Twelfth International Conference on Artificial IntelligenceIJCAI-91, volume 2, 1991.]]

[13]

N. M. Josuttis. The C++ Standard Library: A Tutorial and Reference. Addison-Wesley Professional, 1999.]]

Digital Library

[14]

T. Kovacs and M. Kerber. What makes a problem hard for XCS? In P. L. Lanzi, W. Stolzmann, and S. W. Wilson, editors, Advances in Learning Classifier Systems, volume 1996 of LNAI, pages 80--99. Springer-Verlag, Berlin, 2001.]]

Digital Library

[15]

P. L. Lanzi. The XCS library. 2002.]]

[16]

P. L. Lanzi and S. W. Wilson. Using convex hulls to represent classifier conditions. In Cattolico {8}, pages 1481--1488.]]

Digital Library

[17]

X. Llorá and K. Sastry. Software for fast rule matching using vector instructions. http://www.illigal.uiuc.edu/web/xllora/2006/01/19/, Last checked on March 21th 2008.]]

[18]

X. Llorá and K. Sastry. Fast rule matching for learning classifier systems via vector instructions. In Cattolico {8}, pages 1513--1520.]]

Digital Library

[19]

C. Stone and L. Bull. For real! XCS with continuous-valued inputs. Evolutionary Computation, 11(3):298--336, 2003.]]

Digital Library

[20]

S. W. Wilson. Classifier Fitness Based on Accuracy. Evolutionary Computation, 3(2):149--175, 1995.]]

Digital Library

[21]

S. W. Wilson. Generalization in the XCS classifier system. In Genetic Programming 1998: Proceedings of the Third Annual Conference, pages 665--674. Morgan Kaufmann, 1998.]]

[22]

S. W. Wilson. Get real! XCS with continuous-valued inputs. In P. L. Lanzi, W. Stolzmann, and S. W. Wilson, editors, Learning Classifier Systems, volume 1813 of Lecture Notes in Computer Science, pages 209--222. Springer, 1999.]]

Digital Library

[23]

S. W. Wilson. Mining oblique data with XCS. In P. L. Lanzi, W. Stolzmann, and S. W. Wilson, editors, IWLCS, volume 1996 of Lecture Notes in Computer Science, pages 158--176. Springer, 2000.]]

Digital Library

Cited By

Brede MHansmeier TPlatzner MWagner M(2022)XCS on embedded systemsProceedings of the Genetic and Evolutionary Computation Conference Companion10.1145/3520304.3533977(2071-2079)Online publication date: 9-Jul-2022
https://dl.acm.org/doi/10.1145/3520304.3533977
Li XHe WHirasawa K(2014)Generalized classifier system: Evolving classifiers with cyclic conditions2014 IEEE Congress on Evolutionary Computation (CEC)10.1109/CEC.2014.6900457(1682-1689)Online publication date: Jul-2014
https://doi.org/10.1109/CEC.2014.6900457
Bacardit JLlorà XAlba E(2013)Large scale data mining using genetics-based machine learningProceedings of the 15th annual conference companion on Genetic and evolutionary computation10.1145/2464576.2480807(741-764)Online publication date: 6-Jul-2013
https://dl.acm.org/doi/10.1145/2464576.2480807
Show More Cited By

Index Terms

An analysis of matching in learning classifier systems

Recommendations

A population-based approach to finding the matchset of a learning classifier system efficiently
GECCO '09: Proceedings of the 11th Annual conference on Genetic and evolutionary computation

Profiling of the learning classifier system XCS [11] has revealed that its execution time tends to be dominated by rule matching [8], it is therefore important for rule matching to be efficient. To date, the fastest speedups for matching have been ...
Fractional matching preclusion for arrangement graphs
Abstract
The matching preclusion number of a graph is the minimum number of edges whose deletion results in a graph that has neither perfect matchings nor almost perfect matchings. As a generalization, Liu and Liu (2017) recently introduced the ...
Reducing rank-maximal to maximum weight matching

Given a bipartite graph G(V,E), V=A@?@?B where |V|=n,|E|=m and a partition of the edge set into r@?m disjoint subsets E=E"1@?@?E"2@?@?...@?@?E"r, which are called ranks, the rank-maximal matching problem is to find a matching M of G such that |M@?E"1| ...

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences

GECCO '08: Proceedings of the 10th annual conference on Genetic and evolutionary computation

July 2008

1814 pages

ISBN:9781605581309

DOI:10.1145/1389095

Conference Chair:
Conor Ryan
University of Limerick, Ireland
,
Editor:
Maarten Keijzer
Chordiant Software International B.V., The Netherlands

Copyright © 2008 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 12 July 2008

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

GECCO08

Sponsor:

GECCO08: Genetic and Evolutionary Computation Conference

July 12 - 16, 2008

GA, Atlanta, USA

Acceptance Rates

Overall Acceptance Rate 1,669 of 4,410 submissions, 38%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

15
Total Citations
View Citations
209
Total Downloads

Downloads (Last 12 months)1
Downloads (Last 6 weeks)0

Reflects downloads up to 08 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

Brede MHansmeier TPlatzner MWagner M(2022)XCS on embedded systemsProceedings of the Genetic and Evolutionary Computation Conference Companion10.1145/3520304.3533977(2071-2079)Online publication date: 9-Jul-2022
https://dl.acm.org/doi/10.1145/3520304.3533977
Li XHe WHirasawa K(2014)Generalized classifier system: Evolving classifiers with cyclic conditions2014 IEEE Congress on Evolutionary Computation (CEC)10.1109/CEC.2014.6900457(1682-1689)Online publication date: Jul-2014
https://doi.org/10.1109/CEC.2014.6900457
Bacardit JLlorà XAlba E(2013)Large scale data mining using genetics-based machine learningProceedings of the 15th annual conference companion on Genetic and evolutionary computation10.1145/2464576.2480807(741-764)Online publication date: 6-Jul-2013
https://dl.acm.org/doi/10.1145/2464576.2480807
Franco MKrasnogor NBacardit J(2013)GAssist vs. BioHELSoft Computing - A Fusion of Foundations, Methodologies and Applications10.1007/s00500-013-1016-817:6(953-981)Online publication date: 1-Jun-2013
https://dl.acm.org/doi/10.1007/s00500-013-1016-8
Bacardit JLlorí X(2013)Large-scale data mining using genetics-based machine learningWiley Interdisciplinary Reviews: Data Mining and Knowledge Discovery10.1002/widm.10783:1(37-61)Online publication date: 1-Jan-2013
https://dl.acm.org/doi/10.1002/widm.1078
Bacardit JLlorà XMoore J(2012)Large scale data mining using genetics-based machine learningProceedings of the 14th annual conference companion on Genetic and evolutionary computation10.1145/2330784.2330936(1171-1196)Online publication date: 7-Jul-2012
https://dl.acm.org/doi/10.1145/2330784.2330936
Urbanowicz RGranizo-Mackenzie AMoore JMoore J(2012)Instance-linked attribute tracking and feedback for michigan-style supervised learning classifier systemsProceedings of the 14th annual conference on Genetic and evolutionary computation10.1145/2330163.2330291(927-934)Online publication date: 7-Jul-2012
https://dl.acm.org/doi/10.1145/2330163.2330291
Bacardit JLlorà XLanzi P(2011)Large scale data mining using genetics-based machine learningProceedings of the 13th annual conference companion on Genetic and evolutionary computation10.1145/2001858.2002137(1285-1310)Online publication date: 12-Jul-2011
https://dl.acm.org/doi/10.1145/2001858.2002137
Loiacono DLanzi P(2011)Fast prediction computation in learning classifier systems using CUDAProceedings of the 13th annual conference companion on Genetic and evolutionary computation10.1145/2001858.2001953(169-170)Online publication date: 12-Jul-2011
https://dl.acm.org/doi/10.1145/2001858.2001953
Maravall Dde Lope J(2011)Fusion of learning automata theory and granular inference systemsNeurocomputing10.1016/j.neucom.2010.07.02474:8(1237-1242)Online publication date: 1-Mar-2011
https://dl.acm.org/doi/10.1016/j.neucom.2010.07.024
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Figures

Tables

Media

View Table of Conten