Discrete dynamical genetic programming in XCS

ABSTRACT

A number of representation schemes have been presented for use within Learning Classifier Systems, ranging from binary encodings to neural networks. This paper presents results from an investigation into using a discrete dynamical system representation within the XCS Learning Classifier System. In particular, asynchronous random Boolean networks are used to represent the traditional condition-action production system rules. It is shown possible to use self-adaptive, open-ended evolution to design an ensemble of such discrete dynamical systems within XCS to solve a number of well-known test problems.

REFERENCES

• 1: Ahluwalia, M. and Bull, L. (1999) A Genetic Programming Classifier System. In W. Banzhaf et al. (Eds) Proceedings of the Genetic and Evolutionary Computation Conference -- GECCO-99. Morgan Kaufmann, pp11--18.
• 2: Andre, D., Koza, J. R., Bennett, F. H. and Keane, M. (1999) Genetic Programming III. MIT Press.
• 3: Wolfgang Banzhaf, Genetic Programming for Pedestrians, Proceedings of the 5th International Conference on Genetic Algorithms, p.628, June 01, 1993
• 4: Larry Bull, On Using Constructivism in Neural Classifier Systems, Proceedings of the 7th International Conference on Parallel Problem Solving from Nature, p.558-567, September 07-11, 2002
• 5: Bull, L., Hurst, J. and Tomlinson, A. (2000) Self-Adaptive Mutation in Classifier System Controllers. In J-A. Meyer et al. (Eds) From Animals to Animats 6. MIT Press, pp460--468.
• 6: Bull, L. and Hurst, J. (2003) A Neural Learning Classifier System with Self-Adaptive Constructivism. In IEEE Congress on Evolutionary Computation. IEEE Press. Vol.2, pp991-- 997.
• 7: 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
• 8: Jia Di , Parag K. Lala, Cellular Array-based Delay-insensitive Asynchronous Circuits Design and Test for Nanocomputing Systems, Journal of Electronic Testing: Theory and Applications, v.23 n.2-3, p.175-192, June 2007 [doi>10.1007/s10836-006-0549-5]
• 9: Di Paolo, E. A. (2001) Rhythmic and Non-rhythmic Attractors in Asynchronous Random Boolean Networks. Biosystems, 59(3):185--195
• 10: Ferreira, C. (2006) Gene Expression Programming. Springer.
• 11: Fogel, L. J., Owens, A.J. and Walsh, M. J. (1965) Artificial Intelligence Through A Simulation of Evolution. In M. Maxfield, A. Callahan and L. J. Fogel (Eds) Biophysics and Cybernetic Systems: Proceedings of the 2nd Cybernetic Sciences Symposium. Spartan Books, pp131--155.
• 12: Carlos Gershenson, Classification of random boolean networks, Proceedings of the eighth international conference on Artificial life, p.1-8, December 09-13, 2002
• 13: Harvey, I. and Bossomaier, T. (1997) Time out of Joint: Attractors in Asynchronous Random Boolean Networks. In P. Husbands and I. Harvey (Eds) Proceedings of the Fourth European Artificial Life Conference. MIT Press, pp67--75.
• 14: John H. Holland, Adaptation in natural and artificial systems, MIT Press, Cambridge, MA, 1992
• 15: Holland, J. H. (1976) Adaptation. In R. Rosen and F. M. Snell (Eds) Progress in Theoretical Biology 4. Plenum, pp263--293.
• 16: Gerard D. Howard , Larry Bull , Pier-Luca Lanzi, Self-adaptive constructivism in Neural XCS and XCSF, Proceedings of the 10th annual conference on Genetic and evolutionary computation, July 12-16, 2008, Atlanta, GA, USA [doi>10.1145/1389095.1389364]
• 17: Ingerson, T and Buvel, R. (1984) Structure in Asynchronous Cellular Automata. Physica D 10 (1-2): 59--68.
• 18: Kauffman, S. A. (1993) The Origins of Order: Self-Organization and Selection in Evolution. Oxford.
• 19: John R. Koza , James P. Rice, Genetic programming (videotape): the movie, MIT Press, Cambridge, MA, 1992
• 20: Lanzi, P-L and Perrucci, A. (1999) Extending the Representation of Classifier Conditions Part II: From Messy Coding to S-Expressions. In W. Banzhaf, J. Daida, A.E. Eiben, M.H. Garzon, V. Honavar, M. Jakiela and R. E. Smith (Eds) Proceedings of the Genetic and Evolutionary Computation Conference -- GECCO--99. Morgan Kaufmann, pp345--352.
• 21: Pier Luca Lanzi , Stewart W. Wilson, Toward Optimal Classifier System Performance in Non-Markov Environments, Evolutionary Computation, v.8 n.4, p.393-418, December 2000 [doi>10.1162/106365600568239]
• 22: Mesot, B. and Teuscher, C. (2005) Deducing Local Rules for Solving Global Tasks with Random Boolean Networks. Physica D 211(1-2):88--106.
• 23: Miller, J. (1999) An Empirical Study of the Efficiency of Learning Boolean Functions using a Cartesian Genetic Programming Approach. In W. Banzhaf, J. Daida, A.E. Eiben, M.H. Garzon, V. Honavar, M. Jakiela and R.E. Smith (Eds) Proceedings of the Genetic and Evolutionary Computation Conference -- GECCO--99. Morgan Kaufmann, pp1135--1142.
• 24: Mitchell, M., Hraber P. and Crutchfield J. (1993) Revisiting the Edge of Chaos: Evolving Cellular Automata to Perform Computations. Complex Systems 7: 83--130.
• 25: Packard, N. (1988) Adaptation Toward the Edge of Chaos. In J. Kelso, A. Mandell and M. Shlesinger (Eds) Dynamic Patterns in Complex Systems. World Scientific, pp293--301.
• 26: João Carlos Figueira Pujol , Riccardo Poli, Efficient Evolution of Asymmetric Recurrent Neural Networks Using a PDGP-inspired Two-Dimensional Representation, Proceedings of the First European Workshop on Genetic Programming, p.130-141, April 14-15, 1998
• 27: Michael Schmidt , Hod Lipson, Comparison of tree and graph encodings as function of problem complexity, Proceedings of the 9th annual conference on Genetic and evolutionary computation, July 07-11, 2007, London, England [doi>10.1145/1276958.1277288]
• 28: Moshe Sipper, Evolution of Parallel Cellular Machines: The Cellular Programming Approach, Springer-Verlag New York, Inc., Secaucus, NJ, 2001
• 29: Moshe Sipper , Eytan Ruppin, Co-evolving architectures for cellular machines, Physica D, v.99 n.4, p.428-441, Jan. 1, 1997 [doi>10.1016/S0167-2789(96)00172-8]
• 30: Teller, A. and Veloso, M. (1996) Neural Programming and an Internal Reinforcement Policy. In J. R. Koza (Ed) Late Breaking Papers at the Genetic Programming 1996 Conference, Stanford University, pp186--192.
• 31: Valenzuela-Rendon, M. (1991) The Fuzzy Classifier System: a Classifier System for Continuously Varying Variables. In L. Booker and R. Belew (Eds) Proceedings of the Fourth International Conference on Genetic Algorithms. Morgan Kaufmann, pp346--353.
• 32: John Von Neumann , Arthur W. Burks, Theory of Self-Reproducing Automata, University of Illinois Press, Champaign, IL, 1966
• 33: Tony Werner , Venkatesh Akella, Asynchronous Processor Survey, Computer, v.30 n.11, p.67-76, November 1997 [doi>10.1109/2.634866]
• 34: Stewart W. Wilson, Classifier fitness based on accuracy, Evolutionary Computation, v.3 n.2, p.149-175, Summer 1995 [doi>10.1162/evco.1995.3.2.149]
• 35: Stewart W. Wilson, Get Real! XCS with Continuous-Valued Inputs, Learning Classifier Systems, From Foundations to Applications, p.209-222, January 2000
• 36: Stewart W. Wilson, Classifier Conditions Using Gene Expression Programming, Learning Classifier Systems: 10th International Workshop, IWLCS 2006, Seattle, MA, USA, July 8, 2006 and 11th International Workshop, IWLCS 2007, London, UK, July 8, 2007, Revised Selected Papers, Springer-Verlag, Berlin, Heidelberg, 2008 [doi>10.1007/978-3-540-88138-4_12]
• 37: Wuensche, A. (2004) Basins of attraction in network dynamics: A conceptual framework for biomolecular networks. In Modularity in Development and Evolution (Eds.). G. Schlosser and G. P. Wagner. Chicago, University Press, pp288--311

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.6 Learning
          Subjects: Knowledge acquisition

General Terms:
Experimentation

Keywords:
learning classifier systems, random boolean networks, reinforcement learning, self-adaptation, xcs