article

Analysis and improvement of fitness exploitation in XCS: bounding models, tournament selection, and bilateral accuracy

Authors:

Martin V. Butz,

David E. Goldberg,

Kurian TharakunnelAuthors Info & Claims

Evolutionary Computation, Volume 11, Issue 3

Pages 239 - 277

https://doi.org/10.1162/106365603322365298

Published: 01 September 2003 Publication History

Abstract

The evolutionary learning mechanism in XCS strongly depends on its accuracy-based fitness approach. The approach is meant to result in an evolutionary drive from classifiers of low accuracy to those of high accuracy. Since, given inaccuracy, lower specificity often corresponds to lower accuracy, fitness pressure most often also results in a pressure towards higher specificity. Moreover, fitness pressure should cause the evolutionary process to be innovative in that it combines low-order building blocks of lower accurate classifiers, to higher-order building blocks with higher accuracy. This paper investigates how, when, and where accuracy-based fitness results in successful rule evolution in XCS. Along the way, a weakness in the current proportionate selection method in XCS is identified. Several problem bounds are derived that need to be obeyed to enable proper evolutionary pressure. Moreover, a fitness dilemma is identified that causes accuracy-based fitness to be misleading. Improvements are introduced to XCS to make fitness pressure more robust and overcome the fitness dilemma. Specifically, (1) tournament selection results in a much better fitness-bias exploitation, and (2) bilateral accuracy prevents the fitness dilemma. While the improvements stand for themselves, we believe they also contribute to the ultimate goal of an evolutionary learning system that is able to solve decomposable machine-learning problems quickly, accurately, and reliably. The paper also contributes to the further understanding of XCS in general and the fitness approach in XCS in particular.

References

[1]

Baker, J. (1985). Adaptive selection methods for genetic algorithms. In Grefenstette, J. (Ed.), Proceedings of the International Conference on Genetic Algorithms and Their Applications (pp. 14-21). Hillsdale, NJ: Lawrence Erlbaum Associates.]]

Digital Library

[2]

Bernadó, E., Llorà, X., & Garrell, J. M. (2002). XCS and GALE: A comparative study of two learning classifier systems and six other learning algorithms on classification tasks. In Lanzi, P. L., Stolzmann, W., & Wilson, S. W. (Eds.), Advances in Learning Classifier Systems: 4th International Workshop, IWLCS 2001 (pp. 115-132). Berlin Heidelberg: Springer-Verlag.]]

Digital Library

[3]

Bull, L., & Hurst, J. (2002). ZCS redux. Evolutionary Computation, 10(2), 185-205.]]

Digital Library

[4]

Butz, M. V., Kovacs, T., Lanzi, P. L., & Wilson, S. W. (2001). How XCS evolves accurate classifiers. Proceedings of the Genetic and Evolutionary Computation Conference (GECCO 2001), 927-934.]]

[5]

Butz, M. V., Kovacs, T., Lanzi, P. L., & Wilson, S. W. (submitted, 2003). Theory of generalization and learning in XCS. IEEE Transaction on Evolutionary Computation . also available as IlliGAL technical report 2002011 at http://www-illigal.ge.uiuc.edu/techreps.php3.]]

[6]

Butz, M. V., & Pelikan, M. (2001). Analyzing the evolutionary pressures in XCS. Proceedings of the Genetic and Evolutionary Computation Conference (GECCO 2001), 935-942.]]

[7]

Butz, M. V., Sastry, K., & Goldberg, D. G. (in press, 2003). Tournament selection in XCS. Proceedings of the Genetic and Evolutionary Computation Conference (GECCO 2003).]]

[8]

Butz, M. V., & Wilson, S. W. (2001). An algorithmic description of XCS. In Lanzi, P. L., Stolzmann, W., & Wilson, S. W. (Eds.), Advances in Learning Classifier Systems: Third International Workshop, IWLCS 2000 (pp. 253-272). Berlin Heidelberg: Springer-Verlag.]]

Digital Library

[9]

De Jong, K. A., & Spears, W. M. (1991). Learning concept classification rules using genetic algorithms. IJCAI-91 Proceedings of the Twelfth International Conference on Artificial Intelligence, 651-656.]]

[10]

Dixon, P. W., Corne, D. W., & Oates, M. J. (2002). A preliminary investigation of modified XCS as a generic data mining tool. In Lanzi, P. L., Stolzmann, W., & Wilson, S. W. (Eds.), Advances in Learning Classifier Systems: 4th International Workshop, IWLCS 2001 (pp. 133-150). Berlin Heidelberg: Springer-Verlag.]]

Digital Library

[11]

Goldberg, D. E. (1989). Genetic algorithms in search, optimization and machine learning. Reading, MA: Addison-Wesley.]]

Digital Library

[12]

Goldberg, D. E. (2002). The design of innovation: Lessons from and for competent genetic algorithms. Boston, MA: Kluwer Academic Publishers.]]

Digital Library

[13]

Goldberg, D. E., & Deb, K. (1991). A comparative analysis of selection schemes used in genetic algorithms. Foundations of Genetic Algorithms, 69-93.]]

[14]

Goldberg, D. E., & Sastry, K. (2001). A practical schema theorem for genetic algorithm design and tuning. Proceedings of the Genetic and Evolutionary Computation Conference (GECCO 2001), 328-335.]]

[15]

Holland, J. H. (1975). Adaptation in natural and artificial systems. Ann Arbor, MI: University of Michigan Press. second edition 1992.]]

Digital Library

[16]

Holland, J. H. (1976). Adaptation. In Rosen, R., & Snell, F. (Eds.), Progress in Theoretical Biology, Volume 4 (pp. 263-293). New York: Academic Press.]]

[17]

Holland, J. H., & Reitman, J. S. (1978). Cognitive systems based on adaptive algorithms. In Waterman, D. A., & Hayes-Roth, F. (Eds.), Pattern directed inference systems (pp. 313-329). New York: Academic Press.]]

[18]

Kovacs, T. (1997). XCS classifier system reliably evolves accurate, complete, and minimal representations for boolean functions. In Roy, Chawdhry, & Pant (Eds.), Soft computing in engineering design and manufacturing (pp. 59-68). Springer-Verlag, London.]]

[19]

Kovacs, T. (1999). Deletion schemes for classifier systems. Proceedings of the Genetic and Evolutionary Computation Conference (GECCO-99), 329-336.]]

[20]

Kovacs, T. (2000). Strength or Accuracy? Fitness calculation in learning classifier systems. In Lanzi, P. L., Stolzmann, W., & Wilson, S. W. (Eds.), Learning Classifier Systems: From Foundations to Applications (pp. 143-160). Berlin Heidelberg: Springer-Verlag.]]

Digital Library

[21]

Kovacs, T. (2001). Towards a theory of strong overgeneral classifiers. Foundations of Genetic Algorithms 6, 165-184.]]

[22]

Kovacs, T. (2002). XCS's strength based twin: Part I. In Fifth International Workshop on Learning Classifier Systems (IWLCS-2002), Workshop Working Notes (pp. 59-79). Granada, Spain.]]

[23]

Kovacs, T., & Kerber, M. (2001). What makes a problem hard for XCS? In Lanzi, P. L., Stolzmann, W., & Wilson, S. W. (Eds.), Advances in Learning Classifier Systems: Third International Workshop, IWLCS 2000 (pp. 80-99). Berlin Heidelberg: Springer-Verlag.]]

Digital Library

[24]

Lanzi, P. L. (1999). An analysis of generalization in the XCS classifier system. Evolutionary Computation, 7(2), 125-149.]]

Digital Library

[25]

Lanzi, P. L. (2000). Adaptive agents with reinforcemen learning and internal memory. From Animals to Animats 6: Proceedings of the Sixth International Conference on Simulation of Adaptive Behavior, 333-342.]]

[26]

Lanzi, P. L., & Colombetti, M. (1999). An extension to the XCS classifier system for stochastic environments. Proceedings of the Genetic and Evolutionary Computation Conference (GECCO-99), 353-360.]]

[27]

Pelikan, M., Goldberg, D. E., & Lobo, F. (2002). A survey of optimization by building and using probabilistic models. Computational Optimization and Applications, 21(1), 5-20.]]

Digital Library

[28]

Quinlan, J. R. (1993). C4.5: Programs for machine learning. San Francisco, CA: Morgan Kaufmann.]]

Digital Library

[29]

Venturini, G. (1994). Adaptation in dynamic environments through a minimal probability of exploration. From Animals to Animats 3: Proceedings of the Third international Conference on Simulation of Adaptive Behavior, 371-381.]]

Digital Library

[30]

Wilson, S. W. (1995). Classifier fitness based on accuracy. Evolutionary Computation, 3(2), 149-175.]]

Digital Library

[31]

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

[32]

Wilson, S. W. (2000). Get real! XCS with continuous-valued inputs. In Lanzi, P. L., Stolzmann, W., & Wilson, S. W. (Eds), Learning Classifier Systems: From Foundations to Applications (pp. 209-219). Berlin Heidelberg: Springer-Verlag.]]

Digital Library

[33]

Wilson, S. W. (2001). Mining oblique data with XCS. In Lanzi, P. L., Stolzmann, W., & Wilson, S. W. (Eds.), Advances in Learning Classifier Systems: Third International Workshop, IWLCS 2000 (pp. 158-174). Berlin Heidelberg: Springer-Verlag.]]

Digital Library

Cited By

Liu YBrowne WXue B(2021)A Comparison of Learning Classifier Systems’ Rule Compaction Algorithms for Knowledge VisualizationACM Transactions on Evolutionary Learning and Optimization10.1145/34681661:3(1-38)Online publication date: 18-Aug-2021
https://dl.acm.org/doi/10.1145/3468166
Aenugu SSpector LAuger AStützle T(2019)Lexicase selection in learning classifier systemsProceedings of the Genetic and Evolutionary Computation Conference10.1145/3321707.3321828(356-364)Online publication date: 13-Jul-2019
https://dl.acm.org/doi/10.1145/3321707.3321828
Liu YBrowne WXue BAuger AStützle T(2019)Absumption to complement subsumption in learning classifier systemsProceedings of the Genetic and Evolutionary Computation Conference10.1145/3321707.3321719(410-418)Online publication date: 13-Jul-2019
https://dl.acm.org/doi/10.1145/3321707.3321719
Show More Cited By

Index Terms

Analysis and improvement of fitness exploitation in XCS: bounding models, tournament selection, and bilateral accuracy

Recommendations

Strong, Stable, and Reliable Fitness Pressure in XCS due to Tournament Selection

Recent analysis of the XCS classifier system have shown that successful genetic learning strongly depends on the amount of fitness pressure towards accurate classifiers. Since the traditionally used proportionate selection is dependent on fitness ...
Improving genetic search in XCS-based classifier systems through understanding the evolvability of classifier rules

Learning classifier systems (LCSs), an established evolutionary computation technique, are over 30 years old with much empirical testing and foundations of theoretical understanding. XCS is a well-tested LCS model that generates optimal (i.e., maximally ...
Problem solution sustenance in XCS: Markov chain analysis of niche support distributions and the impact on computational complexity

Michigan-style learning classifier systems iteratively evolve a distributed solution to a problem in the form of potentially overlapping subsolutions. Each problem niche is covered by subsolutions that are represented by a set of predictive rules, ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Evolutionary Computation

Evolutionary Computation Volume 11, Issue 3

Fall 2003

129 pages

ISSN:1063-6560

EISSN:1530-9304

Issue’s Table of Contents

Publisher

MIT Press

Cambridge, MA, United States

Publication History

Published: 01 September 2003

Published in EVOL Volume 11, Issue 3

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

48
Total Citations
View Citations
98
Total Downloads

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

Reflects downloads up to 14 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Liu YBrowne WXue B(2021)A Comparison of Learning Classifier Systems’ Rule Compaction Algorithms for Knowledge VisualizationACM Transactions on Evolutionary Learning and Optimization10.1145/34681661:3(1-38)Online publication date: 18-Aug-2021
https://dl.acm.org/doi/10.1145/3468166
Aenugu SSpector LAuger AStützle T(2019)Lexicase selection in learning classifier systemsProceedings of the Genetic and Evolutionary Computation Conference10.1145/3321707.3321828(356-364)Online publication date: 13-Jul-2019
https://dl.acm.org/doi/10.1145/3321707.3321828
Liu YBrowne WXue BAuger AStützle T(2019)Absumption to complement subsumption in learning classifier systemsProceedings of the Genetic and Evolutionary Computation Conference10.1145/3321707.3321719(410-418)Online publication date: 13-Jul-2019
https://dl.acm.org/doi/10.1145/3321707.3321719
Pätzel DStein AHähner JAuger AStützle T(2019)A survey of formal theoretical advances regarding XCSProceedings of the Genetic and Evolutionary Computation Conference Companion10.1145/3319619.3326848(1295-1302)Online publication date: 13-Jul-2019
https://dl.acm.org/doi/10.1145/3319619.3326848
Nakata MBrowne WAuger AStützle T(2019)How XCS can prevent misdistinguishing rule accuracyProceedings of the Genetic and Evolutionary Computation Conference Companion10.1145/3319619.3321942(183-184)Online publication date: 13-Jul-2019
https://dl.acm.org/doi/10.1145/3319619.3321942
Matsumoto KTakano RTatsumi TSato HKovacs TTakadama KTakadama K(2018)XCSR based on compressed input by deep neural network for high dimensional dataProceedings of the Genetic and Evolutionary Computation Conference Companion10.1145/3205651.3208281(1418-1425)Online publication date: 6-Jul-2018
https://dl.acm.org/doi/10.1145/3205651.3208281
Pätzel DHähner JTakadama K(2018)An algebraic description of XCSProceedings of the Genetic and Evolutionary Computation Conference Companion10.1145/3205651.3208248(1434-1441)Online publication date: 6-Jul-2018
https://dl.acm.org/doi/10.1145/3205651.3208248
Nazmi SHomaifar A(2018)Possibility Rule-Based Classification Using Function Approximation2018 IEEE International Conference on Systems, Man, and Cybernetics (SMC)10.1109/SMC.2018.00122(668-674)Online publication date: 7-Oct-2018
https://dl.acm.org/doi/10.1109/SMC.2018.00122
Nakata MBrowne WHamagami TTakadama KBosman P(2017)Theoretical XCS parameter settings of learning accurate classifiersProceedings of the Genetic and Evolutionary Computation Conference10.1145/3071178.3071200(473-480)Online publication date: 1-Jul-2017
https://dl.acm.org/doi/10.1145/3071178.3071200
Fredivianus NGeihs K(2017)Classifier systems with native fuzzy logic control operationProceedings of the Genetic and Evolutionary Computation Conference Companion10.1145/3067695.3082487(1341-1348)Online publication date: 15-Jul-2017
https://dl.acm.org/doi/10.1145/3067695.3082487
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 Article

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Issue’s Table of Contents