Coevolution of data samples and classifiers integrated with grammatically-based genetic programming for data classification

ABSTRACT

The present work treats the data classification task by means of evolutionary computation techniques using three ingredients: genetic programming, competitive coevolution, and context-free grammar.

The robustness and symbolic/interpretative qualities of the genetic programming are employed to construct classification trees via Darwinian evolution. The flexible formal structure of the context-free grammar replaces the standard genetic programming representation and describes a language which encodes trees of varying complexity. Finally, competitive coevolution is used to promote competitions between data samples and classification trees in order to create and sustain an evolutionary arms-race for improved solutions.

REFERENCES

• 1: David Andre and Astro Teller. A study in program response and the negative effects of introns in genetic programming. In Genetic Programming 1996: Proc. of the First Annual Conference, pages 12--20, Stanford University, CA, USA, 28-31 July 1996. MIT Press.
• 2: C.L. Blake and C.J. Merz. UCI repository of machine learning databases, 1998.
• 3: David E. Goldberg, Genetic Algorithms in Search, Optimization and Machine Learning, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1989
• 4: Frédéric Gruau, On using syntactic constraints with genetic programming, Advances in genetic programming: volume 2, MIT Press, Cambridge, MA, 1996
• 5: Thomas Haynes , Roger L. Wainwright , Sandip Sen , Dale A. Schoenefeld, Strongly Typed Genetic Programming in Evolving Cooperation Strategies, Proceedings of the 6th International Conference on Genetic Algorithms, p.271-278, July 15-19, 1995
• 6: W. Daniel Hillis, Co-evolving parasites improve simulated evolution as an optimization procedure, Physica D, v.42 n.1-3, p.228-234, June 1990
• 7: John H. Holland, Adaptation in natural and artificial systems, MIT Press, Cambridge, MA, 1992
• 8: Lorenz Huelsbergen. Finding general solutions to the parity problem by evolving machine-language representations. In Genetic Programming 1998: Proc. of the Third Annual Conference, pages 158--166, University of Wisconsin, Madison, Wisconsin, USA, 22-25 July 1998.
• 9: John R. Koza, Genetic programming: on the programming of computers by means of natural selection, MIT Press, Cambridge, MA, 1992
• 10: David J. Montana. Strongly typed genetic programming. Technical Report #7866, Bolt Beranek and Newman, Inc., 10 Moulton Street, Cambridge, MA 02138, USA, 7 1994.
• 11: Michael O'Neill and Conor Ryan. Grammatical evolution. IEEE Transactions on Evolutionary Computation, 5(4):349--358, 2001.
• 12: Jan Paredis, The evolution of behavior: some experiments, Proceedings of the first international conference on simulation of adaptive behavior on From animals to animats, p.419-426, February 1991, Paris, France
• 13: Jan Paredis. Steps towards co-evolutionary classification neural networks. In Proc. of the Fourth Intl. Workshop on the Synthesis and Simulation of Living Systems, pages 102--108, 1994.
• 14: J. Quinlan. Improved use of continuous attributes in C4.5. Journal of Artificial Intelligence Research, 4:77--90, 1996.
• 15: Conor Ryan , J. J. Collins , Michael O'Neill, Grammatical Evolution: Evolving Programs for an Arbitrary Language, Proceedings of the First European Workshop on Genetic Programming, p.83-96, April 14-15, 1998
• 16: S. B. Thrun, J. Bala, E. Bloedorn, I. Bratko, B. Cestnik, J. Cheng, K. De Jong, S. DÇzeroski, S. E. Fahlman, D. Fisher, R. Hamann, K. Kaufman, S. Keller, I. Kononenko, J. Kreuziger, R. S. Michalski, T. Mitchell, P. Pachowicz, Y. Reich, H. Vafaie, W. Van de Welde, W. Wenzel, J. Wnek, and J. Zhang. The MONK's problems: A performance comparison of different learning algorithms. Technical Report CS-91-197, Pittsburgh, PA, 1991.
• 17: P. A. Whigham. Grammatically-based genetic programming. In Justinian P. Rosca, editor, Proceedings of the Workshop on Genetic Programming: From Theory to Real-World Applications, pages 33--41, Tahoe City, California, USA, 1995.
• 18: Peter Alexander Whigham. Grammatical Bias for Evolutionary Learning. PhD thesis, School of Computer Science, University College, University of New South Wales, Australian Defence Force Academy, Canberra, Australia, 14 October 1996.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.5 PATTERN RECOGNITION
      I.5.2 Design Methodology
          Subjects: Classifier design and evaluation

Additional Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.8 Database applications
          Subjects: Data mining

General Terms:
Algorithms, Design, Experimentation

Keywords:
competitive coevolution, context-free grammar, data classification, genetic programming