Nothing Special   »   [go: up one dir, main page]

skip to main content
article

Problem solution sustenance in XCS: Markov chain analysis of niche support distributions and the impact on computational complexity

Published: 01 March 2007 Publication History

Abstract

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, termed classifiers. The genetic algorithm is designed to evolve classifier structures that together cover the whole problem space and represent a complete problem solution. An obvious challenge for such an online evolving, distributed knowledge representation is to continuously sustain all problem subsolutions covering all problem niches, that is, to ensure niche support . Effective niche support depends both on the probability of reproduction and on the probability of deletion of classifiers in a niche. In XCS, reproduction is occurrence-based whereas deletion is support-based. In combination, niche support is assured effectively. In this paper we present a Markov chain analysis of the niche support in XCS, which we validate experimentally. Evaluations in diverse Boolean function settings, which require non-overlapping and overlapping solution structures, support the theoretical derivations. We also consider the effects of mutation and crossover on niche support. With respect to computational complexity, the paper shows that XCS is able to maintain (partially overlapping) niches with a computational effort that is linear in the inverse of the niche occurrence frequency.

References

[1]
1. 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 Lanzi et al. {42}, pp. 115-132.
[2]
2. 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.
[3]
3. H.-G. Beyer, U.-M. O'Reily, D. V. Arnold, W. Banzhaf, C. Blum, E. W. Bonabeau, E. Cant-Paz, D. Dasgupta, K. Deb, J. A. Foster, E. D. de Jong, H. Lipson, X. Llora, S. Mancoridis, M. Pelikan, G. R. Raidl, T. Soule, A. M. Tyrrell, J.-P.Watson, and E. Zitzler (eds.). GECCO 2005: Genetic and Evolutionary Computation Conference: Volume 2 . Association for Computing Machinery, Inc: New York, NY, 2005.
[4]
4. C. L. Bridges and D. E. Goldberg, "An analysis of reproduction and crossover in a binary-coded genetic algorithm," in Grefenstette {26}, pp. 9-13.
[5]
5. L. Bull, "Simple Markov models of the genetic algorithm in classifier systems: Accuracy-based fitness," in Lanzi et al. {41}, pp. 21-28.
[6]
6. L. Bull, "Simple Markov models of the genetic algorithm in classifier systems: Multi-step sasks," in Lanzi et al. {41}, pp. 29-36.
[7]
7. L. Bull and J. Hurst, "Self-adaptive mutation in ZCS controllers," in Proceedings of the EvoNet Workshops - EvoRob 2000 , S. Cagnoni, R. Poli, G. Smith, D. Corne, M. Oates, E. Hart, P.-L. Lanzi, E. Willem, Y. Li, B. Paechter, and T. C. Fogarty (eds.), Springer-Verlag: Berlin Heidelberg, 2000, pp. 339-346.
[8]
8. L. Bull and J. Hurst, "ZCS Redux," Evolutionary Computation , vol. 10, pp. 185-205, 2003.
[9]
9. L. Bull, J. Hurst and A. Tomlinson, "Self-adaptive mutation in classifier system controllers," in From Animals to Animats 6: Proceedings of the Sixth International Conference on Simulation of Adaptive Behavior , J.-A. Meyer, A. Berthoz, D. Floreano, H. Roitblat, and S. W. Wilson (eds.), MIT Press: Cambridge, MA, 2000, pp. 460-467.
[10]
10. M. V. Butz, "Documentation of XCS + TS C-Code 1.2," Technical Report 2003023, Illinois Genetic Algorithms Laboratory - University of Illinois at Urbana-Champaign, 2003.
[11]
11. M. V. Butz, "Kernel-based, ellipsoidal conditions in the real-valued XCS classifier system," in Beyer et al. {3}, pp 1835-1842.
[12]
12. M. V. Butz, in Rule-Based EvolutionaryOnline Learning Systems: A Principled Approach to LCS Analysis and Design . Studies in Fuzziness and Soft Computing. Springer-Verlag: Berlin Heidelberg, 2006.
[13]
13. M. V. Butz, D. E. Goldberg, and P. L. Lanzi, "Bounding learning time in XCS," in Genetic and Evolutionary Computation Conference - GECCO 2004: Part II , R. Poli, W. Banzhaf, H.-G. Beyer, E. Burke, P. Darwen, D. Dasgupta, D. Floreano, J. Foster, M. Harman, P. L. Lanzi, L. Spector, A. G. B. Tettamanzi, D. Thierens and A. M. Tyrrell (eds.), Springer-Verlag: Berlin Heidelberg, 2004, pp. 739-750.
[14]
14. M. V. Butz, D. E. Goldberg, P. L. Lanzi, and K. Sastry, "Bounding the population size to ensure niche support in XCS," Technical Report 2004033, Illinois Genetic Algorithms Laboratory - University of Illinois at Urbana-Champaign, 2004.
[15]
15. 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, 2003.
[16]
16. M. V. Butz, T. Kovacs, P. L. Lanzi, and S. W. Wilson,"Toward a theory of generalization and learning in XCS," IEEE Transactions on Evolutionary Computation , vol. 8, pp. 28-46, 2004.
[17]
17. M. V. Butz, K. Sastry, and D. E. Goldberg, "Strong, stable, and reliable fitness pressure in XCS due to tournament selection," Genetic Programming and Evolvable Machines , vol. 6, pp. 53-77, 2004.
[18]
18. M. V. Butz and S. W. Wilson, "An algorithmic description of XCS," Journal of Soft Computing , vol. 6 pp. 144-153, 2002.
[19]
19. W. J. Conover, in Practical Nonparametric Statistics , 3rd edition, John Wiley & Sons: New York, NY, USA, 1998.
[20]
20. K. A. De Jong, "An analysis of the behavior of a class of genetic adaptive systems," PhD thesis, University of Michigan, Ann Arbor, 1975. University Microfilms No. 76-9381.
[21]
21. P. W. Dixon, D. W. Corne, and M. J. Oates, "A preliminary investigation of modified XCS as a generic data mining tool," in Lanzi et al. {42}, pp. 133-150.
[22]
22. R. A. Fisher. Statistical Methods for Research Workers . Oliver and Boyd, Edinburgh, GB, 1925. Available online at http://psychclassics.yorku.ca/Fisher/Methods/.
[23]
23. M. Friendly, Visualizing Categorical Data . SAS Institute: Cary, NC, 2000.
[24]
24. D. Goldberg and P. Segrest, "Finite Markov chain analysis of genetic algorithms," in Grefenstette {26}, pp. 1-8.
[25]
25. D. E. Goldberg, "Simple genetic algorithms and the minimal, deceptive problem," in Genetic Algorithms and Simulated Annealing , L. Davis (eds.), Research Notes in Artificial Intelligence, Pitman, London, 1987, pp. 74-88.
[26]
26. J. J. Grefenstette (ed.), Proceedings of the Second International Conference on Genetic Algorithms , Lawrence Erlbaum Associates, Inc: Mahwah, NJ, USA, 1987.
[27]
27. G. Harik, "Finding multiple solutions in problems of bounded difficulty," in Proceedings of the Sixth International Conference on Genetic Algorithms , L. Eschelman (eds.), Morgan Kaufmann: San Francisco, CA, 1995, pp. 24-31.
[28]
28. G. Harik, E. Cantú-Paz, D. E. Goldberg, and B. L. Miller, "The gambler's ruin problem, genetic algorithms, and the sizing of populations," Evolutionary Computation , vol. 7, pp. 231-253, 1999.
[29]
29. J. H. Holland, Adaptation in Natural and Artificial Systems , 2nd edition, 1992, University of Michigan Press: Ann Arbor, MI, 1975.
[30]
30. J. H. Holland, Hidden Order: How Adaptation Builds Complexity . Perseus Books: Cambridge,MA, USA, 1995.
[31]
31. J. Horn, "Finite Markov chain analysis of genetic algorithms with niching," in Proceedings of the Fifth International Conference on Genetic Algorithms , S. Forrest (eds.), Morgan Kaufmann: San Francisco, CA, 1993, pp. 110-117.
[32]
32. J. Horn, D. E. Goldberg, and K. Deb, "Implicit niching in a learning classifier system: Nature's way," Evolutionary Computation , vol. 2, pp. 37-66, 1994.
[33]
33. J. Hurst and L. Bull, "A Self-Adaptive XCS," in Lanzi et al. {42}, pp. 57-73.
[34]
34. K. A. D. Jong and W. M. Spears, "Learning concept classification rules using genetic algorithms," in Proceedings of the Twelfth International Conference on Artificial Intelligence IJCAI-91 , J. Mylopoulos and R. Reiter (eds.), vol. 2, Morgan Kaufmann: San Francisco, CA, 1991.
[35]
35. L. Kleinroch, Queueing Systems: Theory , John Wiley & Sons: New York, NY, USA, 1975.
[36]
36. T. Kovacs, "XCS classifier system reliably evolves accurate, complete, and minimal representations for boolean functions," in Soft Computing in Engineering Design and Manufacturing , P. K. Chawdhry, R. Roy and R. K. Pant (eds.), Springer-Verlag: New York, NY, USA, 1997, pp. 59-68.
[37]
37. T. Kovacs, "Deletion schemes for classifier systems," in Proceedings of the Genetic and Evolutionary Computation Conference (GECCO-99) , W. Banzhaf, J. Daida, A. E. Eiben, M. H. Garzon, V. Honavar, M. Jakiela and R. E. Smith (eds.), Morgan Kaufmann: San Francisco, CA, 1999, pp. 329-336.
[38]
38. T. Kovacs, Strength or Accuracy: Credit Assignment in Learning Classifier Systems , Springer-Verlag: Berlin Heidelberg, 2003.
[39]
39. P. L. Lanzi, "The XCS library," http://xcslib.sourceforge.net, 2002.
[40]
40. P. L. Lanzi, D. Loiacono, S. W. Wilson and D. E. Goldberg, "Extending XCSF beyond linear approximation," in Beyer et al. {3}, pp. 1827-1834.
[41]
41. P. L. Lanzi, W. Stolzmann, and S. W. Wilson (eds.), Advances in Learning Classifier Systems: Third International Workshop, IWLCS 2000: Paris, France, September 2000: Revised Papers , volume 1996 of LNAI, Springer-Verlag: Berlin Heidelberg, 2001.
[42]
42. P. L. Lanzi, W. Stolzmann, and S. W. Wilson (eds.), Advances in Learning Classifier Systems: 4th International Workshop, IWLCS 2001: San Francisco, CA, USA, July 2001: Revised Papers , volume 2321 of LNAI, Springer-Verlag: Berlin Heidelberg, 2002.
[43]
43. D. G. Luenberger, Introduction to Dynamic Systems: Theory, Models, and Applications , John Wiley & Sons: New York, NY, USA, May 1979.
[44]
44. S. W. Mahfoud, "Crowding and preselection revisited," in Parallel Problem Solving from Nature, 2 , R. Männer and B. Manderick (eds.), Elsevier: Amsterdam, 1992, pp. 27-36.
[45]
45. R. Development Core Team. R: A language and environment for statistical computing . R Foundation for Statistical Computing, Vienna, Austria, 2004. ISBN 3-900051-00-3.
[46]
46. 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 , D. Cliff, P. Husbands, J.-A. Meyer, and S. W. Wilson (eds.), MIT Press: Cambridge, MA, 1994, pp. 371-381.
[47]
47. S. W. Wilson, "Classifier systems and the animat problem," Machine Learning , vol. 2, pp. 199-228, 1987.
[48]
48. S. W. Wilson, "ZCS: A zeroth level classifier system," Evolutionary Computation , vol. 2, pp. 1-18, 1994.
[49]
49. S. W. Wilson, "Classifier fitness based on accuracy," Evolutionary Computation , vol. 3, pp. 149-175, 1995.
[50]
50. S. W. Wilson, "Generalization in the XCS classifier system," in Genetic Programming 1998: Proceedings of the Third Annual Conference , J. R. Koza, W. Banzhaf, K. Chellapilla, K. Deb, M. Dorigo, D. B. Fogel, M. H. Garzon, D. E. Goldberg, H. Iba, and R. Riolo (eds.), Morgan Kaufmann: San Francisco, CA, 1998, pp. 665-674.

Cited By

View all
  • (2020)Absumption and subsumption based learning classifier systemsProceedings of the 2020 Genetic and Evolutionary Computation Conference10.1145/3377930.3389813(368-376)Online publication date: 25-Jun-2020
  • (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
  • (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
  • Show More Cited By

Recommendations

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Genetic Programming and Evolvable Machines
Genetic Programming and Evolvable Machines  Volume 8, Issue 1
March 2007
106 pages

Publisher

Kluwer Academic Publishers

United States

Publication History

Published: 01 March 2007

Author Tags

  1. LCS
  2. Learning classifier systems
  3. Markov chain analysis
  4. Mutation
  5. Niching
  6. Solution sustenance
  7. XCS

Qualifiers

  • Article

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)0
  • Downloads (Last 6 weeks)0
Reflects downloads up to 16 Dec 2024

Other Metrics

Citations

Cited By

View all
  • (2020)Absumption and subsumption based learning classifier systemsProceedings of the 2020 Genetic and Evolutionary Computation Conference10.1145/3377930.3389813(368-376)Online publication date: 25-Jun-2020
  • (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
  • (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
  • (2011)XCSF with local deletionProceedings of the 13th annual conference companion on Genetic and evolutionary computation10.1145/2001858.2002023(383-390)Online publication date: 12-Jul-2011
  • (2011)XCS cannot learn all boolean functionsProceedings of the 13th annual conference on Genetic and evolutionary computation10.1145/2001576.2001749(1283-1290)Online publication date: 12-Jul-2011
  • (2011)Modularization of xcsf for multiple output dimensionsProceedings of the 13th annual conference on Genetic and evolutionary computation10.1145/2001576.2001744(1243-1250)Online publication date: 12-Jul-2011
  • (2009)Facetwise analysis of XCS for problems with class imbalancesIEEE Transactions on Evolutionary Computation10.1109/TEVC.2009.201982913:5(1093-1119)Online publication date: 1-Oct-2009
  • (2009)Fuzzy-UCSIEEE Transactions on Evolutionary Computation10.1109/TEVC.2008.92514413:2(260-283)Online publication date: 1-Apr-2009
  • (2008)Towards increasing learning speed and robustness of XCSFProceedings of the 10th annual conference companion on Genetic and evolutionary computation10.1145/1388969.1389016(2023-2030)Online publication date: 12-Jul-2008

View Options

View options

Media

Figures

Other

Tables

Share

Share

Share this Publication link

Share on social media