Abstract
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 scaling and fitness distribution, the resulting evolutionary fitness pressure may be neither stable nor sufficiently strong. Thus, we apply tournament selection to XCS. In particular, we exhibit the weakness of proportionate selection and suggest tournament selection as a more reliable alternative. We show that tournament selection results in a learning classifier system that is more parameter independent, noise independent, and more efficient in exploiting fitness guidance in single-step problems as well as multistep problems. The evolving population is more focused on promising subregions of the problem space and thus finds the desired accurate, maximally general representation faster and more reliably.
Similar content being viewed by others
References
E. Bernadó, X. Llorà, and J. M. Garrell, “XCS and GALE: A comparative study of two learning classifier systems and six other learning algorithms on classification tasks”, in Advances in Learning Classifier Systems: Fourth International Workshop, IWLCS 2001. P. L. Lanzi, W. Stolzmann, and S. W. Wilson (Eds.), Berlin Heidelberg: Springer-Verlag, 2002, pp. 115–132.
E. Bernadó-Mansilla and J. M. Garrell-Guiu, “Accuracy-based learning classifier systems: Models, analysis, and applications to classification tasks,” Evolutionary Computation, vol. 11, pp. 209–238, 2003.
L. B. Booker, D. E. Goldberg, and J. H. Holland, “Classifier systems and genetic algorithms,” Artificial Intelligence, vol. 40, pp. 235–282, 1989.
M. V. Butz and D. E. Goldberg, “Bounding the population size in XCS to ensure reproductive opportunities,” in Proceedings of the Fifth Genetic and Evolutionary Computation Conference (GECCO-2003) 2003, pp. 1844–1856.
M. V. Butz, D. E. Goldberg, and K. Tharakunnel, “Analysis and improvement of fitness exploitation in XCS: Bounding models, tournament selection, and bilateral accuracy,” Evolutionary Computation, vol. 11, pp. 239–277, 2003a.
M. V. Butz, T. Kovacs, P. L. Lanzi, and S. W. Wilson, “How XCS evolves accurate classifiers,” in Proceedings of the Third Genetic and Evolutionary Computation Conference (GECCO-2001), 2001, pp. 927–934.
M. V. Butz and M. Pelikan, “Analyzing the evolutionary pressures in XCS,” Proceedings of the Third Genetic and Evolutionary Computation Conference (GECCO-2001), 2001, pp. 935–942.
M. V. Butz, K. Sastry, and D. E. Goldberg, “Tournament Selection in XCS,” in Proceedings of the Fifth Genetic and Evolutionary Computation Conference (GECCO-2003), 2003b, pp. 1857–1869.
M. V. Butz and S. W. Wilson, “An algorithmic description of XCS,” in Advances in Learning Classifier Systems: Third International Workshop, IWLCS 2000. P. L. Lanzi, W. Stolzmann, and S. W. Wilson (Eds.), Berlin Heidelberg: Springer-Verlag, 2001, pp. 253–272.
K. A. De Jong and W. M. Spears, “Learning concept classification rules using genetic algorithms,” IJCAI-91 Proceedings of the Twelfth International Conference on Artificial Intelligence, 1991, pp. 651–656.
P. W. Dixon, D. W. Corne, and M. J. Oates, “A preliminary investigation of modified XCS as a generic data mining tool,” in Advances in Learning Classifier Systems: Fourth International Workshop, IWLCS 2001, P. L. Lanzi, W. Stolzmann, and S. W. Wilson (Eds.), Berlin Heidelberg: Springer-Verlag, 2002, pp. 133–150.
D. E. Goldberg, Genetic Algorithms in Search, Optimization and Machine Learning. Addison-Wesley-Reading, MA, 1989.
D. E. Goldberg, The Design of Innovation: Lessons from and for Competent Genetic Algorithms. Kluwer Academic Publishers: Boston, MA, 2002.
D. E. Goldberg and K. Deb, “A comparative analysis of selection schemes used in genetic algorithms,” Foundations of Genetic Algorithms, 1991, pp. 69–93.
D. E. Goldberg and K. Sastry, “A practical schema theorem for genetic algorithm design and tuning,” in Proceedings of the Third Genetic and Evolutionary Computation Conference (GECCO-2001), 2001, pp. 328–335.
G. Harik, “Learning gene linkage to efficiently solve problems of bounded difficulty,” Ph.D. thesis, University of Michigan. also IlliGAL Report No. 97005, University of Illinois at Urbana-Champaign, 1997.
J. H. Holland, 1975, Adaptation in Natural and Artificial Systems. University of Michigan Press, Ann Arbor, ML: 2nd edition 1992.
J. H. Holland, ‘Adaptation’, in Progress in Theoretical Biology, R. Rosen and F. Snell (Eds.), Vol. 4. Academic Press: New York, 1976, pp. 263–293.
L. P. Kaelbling, M. L. Littman, and A. W. Moore, “Reinforcement Learning: A Survey,” Journal of Artificial Intelligence Research, vol. 4, pp. 237–285, 1996.
T. Kovacs, “XCS’s strength based twin: Part I,” in Fifth International Workshop on Learning Classifier Systems (IWLCS-2002), Workshop Working Notes. P. L. Lanzi, W. Stolzmann, and S. W. Wilson (Eds.), Granada, Spain, 2002, pp. 59–79.
T. Kovacs, Strength or Accuracy: Credit Assignment in Learning Classifier Systems. Berlin Heidelberg: Springer-Verlag, 2003.
T. Kovacs and M. Kerber, “What makes a problem hard for XCS?,” in Advances in Learning Classifier Systems: Third International Workshop, IWLCS 2000. P. L. Lanzi, W. Stolzmann, and S. W. Wilson (Eds.), Berlin Heidelberg: Springer-Verlag, 2001, pp. 80–99.
P. L. Lanzi, “An Analysis of Generalization in the XCS Classifier System,” Evolutionary Computation, vol. 7, no. 2, pp. 125–149, 1999a.
P. L. Lanzi, ‘An extension to the XCS classifier system for stochastic environments’. Proceedings of the Genetic and Evolutionary Computation Conference (GECCO-99) 1999b, pp. 353–360.
P. L. Lanzi, “Adaptive agents with reinforcement learning and internal memory,” From Animals to Animats 6: Proceedings of the Sixth International Conference on Simulation of Adaptive Behavior, 2000, pp. 333–342.
P. L. Lanzi, “Learning classifier systems from a reinforcement learning perspective,” Soft Computing: A Fusion of Foundations, Methodologies and Applications, vol. 6, pp. 162–170, 2002.
P. L. Lanzi and S. W. Wilson, “Toward optimal classifier system performance in non-Markov environments,” Evolutionary Computation, vol. 8, no. 4, pp. 393–418, 2000.
M. Pelikan, D. E. Goldberg, and F. Lobo, “A survey of optimization by building and using probabilistic models,” Computational Optimization and Applications, vol. 21 no. 1, pp. 5–20, 2002.
R. S. Sutton and A. G. Barto, Reinforcement Learning: An Introduction. MIT Press: Cambridge, MA, 1998.
D. Thierens and D. E. Goldberg, “Mixing in genetic algorithms,” in Proceedings of the Fifth International Conference on Genetic Algorithms, 1993, pp. 38–45.
G. Venturini, “Adaptation in dynamic environments through a minimal probability of exploration,” in From Animals to Animats 3: Proceedings of the Third International Conference on Simulation of Adaptive Behavior, 1994, pp. 371–381.
C. J. Watkins, C. H., “Learning from Delayed Rewards,” Ph.D. thesis, King’s College, Cambridge, UK, 1989.
S. W. Wilson, “Classifier fitness based on accuracy,” Evolutionary Computation, vol. 3, no. 2, pp. 149–175, 1995.
S. W. Wilson, “Generalization in the XCS classifier system,” Genetic Programming 1998: Proceedings of the Third Annual Conference, 1998, pp. 665–674.
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Butz, M.V., Sastry, K. & Goldberg, D.E. Strong, Stable, and Reliable Fitness Pressure in XCS due to Tournament Selection. Genet Program Evolvable Mach 6, 53–77 (2005). https://doi.org/10.1007/s10710-005-7619-9
Received:
Revised:
Issue Date:
DOI: https://doi.org/10.1007/s10710-005-7619-9