Genetically programmed learning classifier system description and results

ABSTRACT

An agent population can be evolved in a complex environment to perform various tasks and optimize its job performance using Learning Classifier System (LCS) technology. Due to the complexity and knowledge content of some real-world systems, having the ability to use genetic programming, GP, to represent the LCS rules provides a great benefit. Methods have been created to extend LCS theory into operation across the power-set of GP-enabled rule content. This system uses a full bucket-brigade system for GP-LCS learning. Using GP in the LCS system allows the functions and terminals of the actual problem environment to be used internally directly in the rule set, enabling more direct interpretation of the operation of the LCS system. The system was designed and built, and underwent a year of independent testing at an advanced technology research laboratory. This paper describes the top-level operation of the system, and includes some of the results of the testing effort, and performance figures.

REFERENCES

• 1: Ahluwalia, M. & Bull, L. A Genetic Programming-based Classifier System. GECCO-99: Proceedings of the Genetic and Evolutionary Computation Conference. Morgan Kaufmann, 1999, 11--18.
• 2: Stolzmann, W.. Anticipatory classifier systems. Proceedings of the Third Annual Genetic Programming Conference, July 22-25, 1998. (University of Wisconsin, Madison, WI). Morgan Kaufmann Publishers, San Francisco, CA, 1998, 658--664.
• 3: Wilson, S.W.. Generalization in the XCS Classifier System. Proceedings of the Third Annual Genetic Programming Conference. (University of Wisconsin, Madison, WI, July 22-25, 1998). Morgan Kaufmann Publishers, San Francisco, CA, 1998, 665--674.
• 4: Bay, J.S. Learning Classifier Systems for Single and Multiple Robots in Unstructured Environments. Web page, Jan. 5. 1999. Internet. http://armyant.ee.vt.edu/
• 5: Bonarini, A., Bonacina, C., and Matteucci, M. Fuzzy and crisp representations of real-values input for learning classifier systems. Proceedings of the Genetic and Evolutionary Computation Conference, 1999, LCS workshop. (Orlando, FL, 1999).
• 6: Booker, L.B. Do we really need to estimate rule utilities in classifier systems? Proceedings of the Genetic and Evolutionary Computation Conference, 1999, LCS workshop. (Orlando, FL, 1999).
• 7: Marco Dorigo, Message-based bucket brigade: an algorithm for the apportionment of credit problem, Proceedings of the European working session on learning on Machine learning, p.235-244, March 1991, Porto, Portugal
• 8: Smith, R.E., Dike, B.A., et al. The fighter aircraft LCS: a case of different LCS goals and techniques. Proceedings of the Genetic and Evolutionary Computation Conference, 1999, LCS workshop. (Orlando, FL, 1999).
• 9: John H. Holland, Emergence: from chaos to order, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1998
• 10: John H. Holland, Adaptation in natural and artificial systems, MIT Press, Cambridge, MA, 1992
• 11: John R. Koza, Genetic programming: on the programming of computers by means of natural selection, MIT Press, Cambridge, MA, 1992
• 12: de la Maza, M. Sigma Truncation in The Boltzmann selection procedure. Practical Handbook of Genetic Algorithms, New Frontiers, Vol. II. Chapman & Hall/CRC, Boca Raton, FL, 1995, 111--138.
• 13: Richards, R. Zeroth-Order Shape Optimization Utilizing a Learning Classifier System. Web page, viewed December 3, 1998. Internet http://www.stanford.edu/~buc/SPHINcsX/book.html
• 14: David E. Goldberg, Genetic Algorithms in Search, Optimization and Machine Learning, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1989
• 15: Jorg P. Muller, The Design of Intelligent Agents: A Layered Approach, Springer-Verlag New York, Inc., Secaucus, NJ, 1997
• 16: Poli, R. and Langdon, W.B. A new schema theory for genetic programming with one--point crossover and point mutation. In Genetic Programming 1997: Proceedings of the Second Annual Conference. (Stanford University, July 13-16, 1997). Morgan Kaufmann, San Francisco, CA, 1997, 35--43.
• 17: Rosca, J.P. Analysis of complexity drift in genetic programming. Genetic Programming 1997: Proceedings of the Second Annual Conference. (Stanford University, July 13-16, 1997). Morgan Kaufmann, San Francisco, CA, 1997, 286--294.
• 18: John H. Holland, Hidden order: how adaptation builds complexity, Addison Wesley Longman Publishing Co., Inc., Redwood City, CA, 1996

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.4 Knowledge Representation Formalisms and Methods
          Subjects: Representations (procedural and rule-based)

Additional Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
        I.2.11 Distributed Artificial Intelligence
            Subjects: Intelligent agents
      I.2.6 Learning

General Terms:
Algorithms, Design, Experimentation, Theory

Keywords:
agent learning, autonomous agent, bucket brigade, complex adaptive system, evolutionary computation, genetic programming, genetics-based machine learning (GBML), intelligent agent, learning classifier system, reinforcement learning