Studying XCS/BOA learning in Boolean functions: structure encoding and random Boolean functions

ABSTRACT

Recently, studies with the XCS classifier system on Boolean functions have shown that in certain types of functions simple crossover operators can lead to disruption and, consequently, a more effective recombination mechanism is required. Simple crossover operators were replaced by recombination based on estimation of distribution algorithms (EDAs). The combination showed that XCS with such a statistics-based crossover operator can solve challenging hierarchical functions more efficiently. This study elaborates the gained competence further investigating the coding scheme for the EDA component (BOA in our case) of XCS as well as performance in randomly generated Boolean function problems. Results in hierarchical Boolean functions show that the originally used 2-bit coding scheme induces a certain learning bias that stresses additional diversity in the evolving XCS population. A 1-bit coding scheme as well as a restricted 2-bit coding scheme confirm the suspected bias. The alternative encodings decrease the unnecessary bias towards specificity and increase performance robustness. The paper concludes with a discussion on the challenges ahead for XCS in Boolean function problems as well as on the implications of the obtained results for real-valued and multiple-valued classification problems, multi-step problems, and function approximation problems.

REFERENCES

• 1: Ester Bernadó i Mansilla , Xavier Llorà , Josep Maria Garrell i Guiu, XCS and GALE: A Comparative Study of Two Learning Classifier Systems on Data Mining, Revised Papers from the 4th International Workshop on Advances in Learning Classifier Systems, p.115-132, July 07-08, 2001
• 2: Ester Bernadó-Mansilla , Josep M. Garrell-Guiu, Accuracy-based learning classifier systems: models, analysis and applications to classification tasks, Evolutionary Computation, v.11 n.3, p.209-238, Fall 2003 [doi>10.1162/106365603322365289]
• 3: Larry Bull , Jacob Hurst, ZCS redux, Evolutionary Computation, v.10 n.2, p.185-205, Summer 2002 [doi>10.1162/106365602320169848]
• 4: M. V. Butz. Anticipation for learning, cognition, and education. On the Horizon, 2004. in press.
• 5: Martin V. Butz, Kernel-based, ellipsoidal conditions in the real-valued XCS classifier system, Proceedings of the 2005 conference on Genetic and evolutionary computation, June 25-29, 2005, Washington DC, USA [doi>10.1145/1068009.1068320]
• 6: M. V. Butz, D. E. Goldberg, and P. L. Lanzi. Bounding learning time in XCS. Proceedings of the Sixth Genetic and Evolutionary Computation Conference (GECCO-2004): Part II, pages 739--750, 2004.
• 7: M. V. Butz, D. E. Goldberg, and P. L. Lanzi. Gradient Descent Methods in Learning Classifier Systems: Improving XCS Performance in Multistep Problems. IEEE Transactions on Evolutionary Computation, 9:452--473, 2004.
• 8: M. V. Butz, D. E. Goldberg, and P. L. Lanzi. Foundations of Learning Classifier Systems, chapter Computational Complexity of the XCS Classifier System, pages 91--126. Studies in Fuzziness and Soft Computing. Springer-Verlag, Berlin Heidelberg, 2005.
• 9: Martin V. Butz , David E. Goldberg , Kurian Tharakunnel, Analysis and improvement of fitness exploitation in XCS: bounding models, tournament selection, and bilateral accuracy, Evolutionary Computation, v.11 n.3, p.239-277, Fall 2003 [doi>10.1162/106365603322365298]
• 10: 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, 8:28--46, 2004.
• 11: Martin V. Butz , Martin Pelikan , Xavier Llorà , David E. Goldberg, Extracted global structure makes local building block processing effective in XCS, Proceedings of the 2005 conference on Genetic and evolutionary computation, June 25-29, 2005, Washington DC, USA [doi>10.1145/1068009.1068121]
• 12: Martin Butz , Stewart W. Wilson, An Algorithmic Description of XCS, Revised Papers from the Third International Workshop on Advances in Learning Classifier Systems, p.253-272, September 15-16, 2000
• 13: David E. Goldberg, The Design of Innovation: Lessons from and for Competent Genetic Algorithms, Kluwer Academic Publishers, Norwell, MA, 2002
• 14: G. Harik. Linkage learning via probabilistic modeling in the ECGA. IlliGAL report 99010, Illinois Genetic Algorithms Laboratory, University of Illinois at Urbana-Champaign, 1999.
• 15: M. Henrion. Propagating uncertainty in Bayesian networks by probabilistic logic sampling. In J. F. Lemmer and L. N. Kanal, editors, Uncertainty in Artificial Intelligence, pages 149--163. Elsevier, Amsterdam, London, New York, 1988.
• 16: J. H. Holland. Adaptation. In R. Rosen and F. Snell, editors, Progress in theoretical biology, volume 4, pages 263--293. Academic Press, New York, 1976.
• 17: John H. Holland, Hidden order: how adaptation builds complexity, Addison Wesley Longman Publishing Co., Inc., Redwood City, CA, 1996
• 18: J. H. Holland and J. S. Reitman. Cognitive systems based on adaptive algorithms. In D. A. Waterman and F. Hayes-Roth, editors, Pattern directed inference systems, pages 313--329. Academic Press, New York, 1978.
• 19: Tim Kovacs , Manfred Kerber, What Makes a Problem Hard for XCS?, Revised Papers from the Third International Workshop on Advances in Learning Classifier Systems, p.80-102, September 15-16, 2000
• 20: P. Larrañaga. A review on estimation of distribution algorithms. In P. Larrañaga and J. A. Lozano, editors, Estimation of Distribution Algorithms, chapter 3, pages 57--100. Kluwer Academic Publishers, Boston, MA, 2002.
• 21: 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]
• 22: Heinz Mühlenbein , Gerhard Paass, From Recombination of Genes to the Estimation of Distributions I. Binary Parameters, Proceedings of the 4th International Conference on Parallel Problem Solving from Nature, p.178-187, September 22-26, 1996
• 23: R. M. Neal. Probabilistic inference using Markov chain Monte Carlo methods. Technical Report CRG-TR-93-1, Dept. of Computer Science, University of Toronto, 1993.
• 24: M. Pelikan. Hierarchical Bayesian optimization algorithm: Toward a new generation of evolutionary algorithms. Springer-Verlag, 2005.
• 25: M. Pelikan, D. E. Goldberg, and E. Cantu-Paz. BOA: The Bayesian optimization algorithm. Proceedings of the Genetic and Evolutionary Computation Conference (GECCO-99), pages 525--532, 1999.
• 26: Martin Pelikan , David E. Goldberg , Fernando G. Lobo, A Survey of Optimization by Building and Using Probabilistic Models, Computational Optimization and Applications, v.21 n.1, p.5-20, January 2002 [doi>10.1023/A:1013500812258]
• 27: B. Widrow and M. Hoff. Adaptive switching circuits. Western Electronic Show and Convention, 4:96--104, 1960.
• 28: S. W. Wilson. Classifier fitness based on accuracy. Evolutionary Computation, 3(2):149--175, 1995.
• 29: S. W. Wilson. Generalization in the XCS classifier system. Genetic Programming 1998: Proceedings of the Third Annual Conference, pages 665--674, 1998.
• 30: Stewart W. Wilson, Classifiers that approximate functions, Natural Computing: an international journal, v.1 n.2-3, p.211-234, June 2002 [doi>10.1023/A:1016535925043]
• 31: S. W. Wilson. Classifier systems for continuous payoff environments. Proceedings of the Sixth Genetic and Evolutionary Computation Conference (GECCO-2004): Part II, pages 824--835, 2004.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.8 Problem Solving, Control Methods, and Search

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

General Terms:
Algorithms

Keywords:
Bayesian networks, XCS, learning classifier systems, reinforcement learning