Genetic Programming for Finite Algebras

Lee Spector
Cognitive Science, Hampshire College
(lspector@hampshire.edu, http://hampshire.edu/lspector)

David M. Clark
Mathematics, SUNY New Paltz

Ian Lindsay
Hampshire College

Bradford Barr
Hampshire College

Jon Klein
Hampshire College


This page contains material related to "Genetic Programming for Finite Algebras," a paper in the Proceedings of the Genetic and Evolutionary Computation Conference (GECCO-2008), published by The Association of Computing Machinery.

The work reported in this paper was awarded the gold medal in the Human Competitive Results contest at the 2008 Genetic and Evolutionary Computation Conference (press release).


Abstract

We describe the application of genetic programming (GP) to a problem in pure mathematics, in the study of finite algebras. We document the production of human-competitive results in the discovery of particular algebraic terms, namely discriminator, Pixley, majority and Mal'cev terms, showing that GP can exceed the performance of every prior method of finding these terms in either time or size by several orders of magnitude. Our terms were produced using the ECJ and PushGP genetic programming systems in a variety of configurations. We compare the results of GP to those of exhaustive search, random search, and algebraic methods.

Citation

Spector, L., D. M. Clark, I. Lindsay, B. Barr, and J. Klein. 2008, in press. Genetic Programming for Finite Algebras. In Proceedings of the Genetic and Evolutionary Computation Conference (GECCO-2008). ACM Press.

Full paper

Full paper in PDF format: http://hampshire.edu/lspector/pubs/gpfa-gecco-2008.pdf (192KB).

Presentation Slides

Prepared for the GECCO 2008 conference: http://hampshire.edu/lspector/gpfa-gecco-2008/slides.pdf (1.3MB).

Source Code

PushGP: http://hampshire.edu/lspector/gpfa-gecco-2008/algebra-pushgp.zip
ECJ: http://hampshire.edu/lspector/gpfa-gecco-2008/algebra-ecj.tar.gz

Acknowledgments

We thank our anonymous reviewers for thorough and constructive criticism. This material is based upon work supported by the National Science Foundation under Grant No. 0308540. Any opinions, findings, and conclusions or recommendations expressed in this publication are those of the authors and do not necessarily reflect the views of the National Science Foundation.