Genetic programming for finite algebras

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.

REFERENCES

• 1: K. Baker and A. Pixley. Polynomial interpolation and the chinese remainder theorem for algebraic systems. Math. Z., 143:165--174, 1975.
• 2: D. Clark and B. Davey. Topological Dualities for the Working Algebraist. Studies in Advanced Mathematics Series. Cambridge, UK: Cambridge University Press, 1998.
• 3: D. Clark, B. Davey, J. Pitkethly, and D. Rifqui. Primality from semilattices, 2008. Preprint.
• 4: B. A. Davey, V. J. Schumann, and H. Werner. From the subalgebras of the square to the discriminator. Algebra Universalis, 28:500--519, 1991.
• 5: R. O. Davies. On n-valued sheffer functions. Zeitschr. f. math. Logik und Grundlagen d. Math., Bd. 25:293--298, 1979.
• 6: Francisco Fernández , Marco Tomassini , Leonardo Vanneschi, An Empirical Study of Multipopulation Genetic Programming, Genetic Programming and Evolvable Machines, v.4 n.1, p.21-51, March 2003 [doi>10.1023/A:1021873026259]
• 7: R. Freese and E. Kiss. UACalc: The universal algebra calculator, 2007. www.cs.elte.hu/~ewkiss/software/uaprog/.
• 8: G. Grätzer. Universal Algebra. Springer-Verlag, 1982.
• 9: K. Kaarli and A. Pixley. Polynomial Completeness in Algebraic Systems. New York, NY: Chapman and Hall/CRC, 2001.
• 10: Jon Klein, breve: a 3D environment for the simulation of decentralized systems and artificial life, Proceedings of the eighth international conference on Artificial life, p.329-334, December 09-13, 2002
• 11: J. Klein and L. Spector. Genetic programming with historically assessed hardness. In R. Riolo, T. Soule, and B. Worzel, editors, Genetic Programming Theory and Practice VI. Springer, in preparation.
• 12: D. E. Knuth. A draft of section 7.2.1.6: Generating all trees. In The Art of Computer Programming, volume 4. Addison-Wesley, Pre-fascicle 4A. www-cs-faculty.stanford.edu/~knuth/fasc4a.ps.gz.
• 13: John R. Koza, Genetic programming: on the programming of computers by means of natural selection, MIT Press, Cambridge, MA, 1992
• 14: W. B. Langdon. The evolution of size in variable length representations. In 1998 IEEE International Conference on Evolutionary Computation, pages 633--638, Anchorage, Alaska, USA, 5-9 May 1998. IEEE Press.
• 15: S. Luke. Two fast tree-creation algorithms for genetic programming. IEEE Trans. on Evol. Comp., 4(3):274--283, Sept. 2000.
• 16: I. A. Mal'cev. On the general theory of algebraic systems (Russian). Mat. Sb., 35:3--22, 1954.
• 17: R. McKenzie, G. McNulty, and W. Taylor. Algebras, Lattices and Varieties, volume 1. Belmont, CA: Wadsworth and Brooks/Cole, 1987.
• 18: V. L. Murskii. A finite basis of identities and other properties of 'almost all' finite algebras. Problémy Kibérnétiki, 30:43--56, 1975.
• 19: A. Pixley. Distributivity and permutability of congruence relations in equational classes of algebras. Proc. Amer. Math. Soc., 14:105--119, 1963.
• 20: J. Rotman. An introduction to the theory of groups. Springer-Verlag, 1994.
• 21: G. Rousseau. Completeness in finite algebras with a single operation. Proc. Amer. Math. Soc., 18:1009--1013, 1967.
• 22: J. Slupecki. Kryterium pelnosci wielowartosciowych systemów logiki zdan. Comptes rendus des séances de la Société des Lettres de Varsovie, Classe III, 32 Année:102--109, 1939.
• 23: J. Slupecki. A criterion of fullness of many-valued systems of propositional logic. Studia Logica, 30:153--157, 1972.
• 24: L. Spector and J. Klein. Trivial geography in genetic programming. In T. Yu, R. L. Riolo, and B. Worzel, editors, Genetic Programming Theory and Practice III, volume 9 of Genetic Programming, chapter 8, pages 109--123. Springer, 2005.
• 25: Lee Spector , Jon Klein , Maarten Keijzer, The Push3 execution stack and the evolution of control, Proceedings of the 2005 conference on Genetic and evolutionary computation, June 25-29, 2005, Washington DC, USA [doi>10.1145/1068009.1068292]
• 26: Lee Spector , Alan Robinson, Genetic Programming and Autoconstructive Evolution with the Push Programming Language, Genetic Programming and Evolvable Machines, v.3 n.1, p.7-40, March 2002 [doi>10.1023/A:1014538503543]
• 27: H. Werner. Eine Charakterisierung funktional vollständiger Algebren. Archiv d. Math., 21:383--385, 1970.
• 28: H. Werner. Discriminator-Algebras: Algebraic Representation and Model Theoretic Properties. Akademie-Verlag, 1978.
• 29: G. C. Wilson , A. Mc Intyre , M. I. Heywood, Resource Review: Three Open Source Systems for Evolving Programs–Lilgp, ECJ and Grammatical Evolution, Genetic Programming and Evolvable Machines, v.5 n.1, p.103-105, March 2004 [doi>10.1023/B:GENP.0000017053.10351.dc]

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.2 Automatic Programming
          Subjects: Program synthesis

Additional Classification:
  I. Computing Methodologies
  I.1 SYMBOLIC AND ALGEBRAIC MANIPULATION
      I.1.2 Algorithms
          Subjects: Algebraic algorithms

General Terms:
Algorithms, Experimentation, Performance

Keywords:
ECJ, PushGP, finite algebras, genetic programming