Lee Spector
David M. Clark
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.
- K. Baker and A. Pixley. Polynomial interpolation and the chinese remainder theorem for algebraic systems. Math. Z., 143:165--174, 1975.Google Scholar
Cross Ref
- D. Clark and B. Davey. Topological Dualities for the Working Algebraist. Studies in Advanced Mathematics Series. Cambridge, UK: Cambridge University Press, 1998.Google Scholar
- D. Clark, B. Davey, J. Pitkethly, and D. Rifqui. Primality from semilattices, 2008. Preprint.Google Scholar
- B. A. Davey, V. J. Schumann, and H. Werner. From the subalgebras of the square to the discriminator. Algebra Universalis, 28:500--519, 1991.Google ScholarCross Ref
- R. O. Davies. On n-valued sheffer functions. Zeitschr. f. math. Logik und Grundlagen d. Math., Bd. 25:293--298, 1979.Google Scholar
- F. Fernandez, M. Tomassini, and L. Vanneschi. An empirical study of multipopulation genetic programming. Genetic Programming and Evolvable Machines, 4(1):21--51, Mar. 2003. Google ScholarDigital Library
- R. Freese and E. Kiss. UACalc: The universal algebra calculator, 2007. www.cs.elte.hu/~ewkiss/software/uaprog/.Google Scholar
- G. Grätzer. Universal Algebra. Springer-Verlag, 1982.Google Scholar
- K. Kaarli and A. Pixley. Polynomial Completeness in Algebraic Systems. New York, NY: Chapman and Hall/CRC, 2001.Google Scholar
- J. Klein. BREVE: a 3d environment for the simulation of decentralized systems and artificial life. In Proc. Artificial Life VIII, the 8th Int. Conf. on the Simulation and Synthesis of Living Sys., pages 329--334. The MIT Press, 2002. http://www.spiderland.org/breve/breve-klein-alife2002.pdf. Google ScholarDigital Library
- 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.Google Scholar
- 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.Google ScholarDigital Library
- J. R. Koza. Genetic Programming: On the Programming of Computers by Means of Natural Selection. MIT Press, Cambridge, MA, USA, 1992. Google ScholarDigital Library
- 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.Google ScholarCross Ref
- S. Luke. Two fast tree-creation algorithms for genetic programming. IEEE Trans. on Evol. Comp., 4(3):274--283, Sept. 2000. Google ScholarDigital Library
- I. A. Mal'cev. On the general theory of algebraic systems (Russian). Mat. Sb., 35:3--22, 1954.Google Scholar
- R. McKenzie, G. McNulty, and W. Taylor. Algebras, Lattices and Varieties, volume 1. Belmont, CA: Wadsworth and Brooks/Cole, 1987.Google Scholar
- 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.Google Scholar
- A. Pixley. Distributivity and permutability of congruence relations in equational classes of algebras. Proc. Amer. Math. Soc., 14:105--119, 1963.Google ScholarCross Ref
- J. Rotman. An introduction to the theory of groups. Springer-Verlag, 1994.Google Scholar
- G. Rousseau. Completeness in finite algebras with a single operation. Proc. Amer. Math. Soc., 18:1009--1013, 1967.Google ScholarCross Ref
- 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.Google Scholar
- J. Slupecki. A criterion of fullness of many-valued systems of propositional logic. Studia Logica, 30:153--157, 1972.Google ScholarCross Ref
- 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.Google ScholarDigital Library
- L. Spector, J. Klein, and M. Keijzer. The Push3 execution stack and the evolution of control. In Proc. Gen. and Evol. Comp. Conf., volume 2, pages 1689--1696. ACM Press, 2005. Google ScholarDigital Library
- L. Spector and A. Robinson. Genetic programming and autoconstructive evolution with the Push programming language. Genetic Programming and Evolvable Machines, 3(1):7--40, Mar. 2002. Google ScholarDigital Library
- H. Werner. Eine Charakterisierung funktional vollständiger Algebren. Archiv d. Math., 21:383--385, 1970.Google Scholar
- H. Werner. Discriminator-Algebras: Algebraic Representation and Model Theoretic Properties. Akademie-Verlag, 1978.Google Scholar
- G. C. Wilson, A. McIntyre, and M. I. Heywood. Resource review: Three open source systems for evolving programs-lilgp, ECJ and grammatical evolution. Genetic Programming and Evolvable Machines, 5(1):103--105, Mar. 2004. Google ScholarDigital Library
Index Terms
- Genetic programming for finite algebras
Recommendations
Neural network crossover in genetic algorithms using genetic programming
AbstractThe use of genetic algorithms (GAs) to evolve neural network (NN) weights has risen in popularity in recent years, particularly when used together with gradient descent as a mutation operator. However, crossover operators are often omitted from ...
Exact Schema Theory and Markov Chain Models for Genetic Programming and Variable-length Genetic Algorithms with Homologous Crossover
Genetic Programming (GP) homologous crossovers are a group of operators, including GP one-point crossover and GP uniform crossover, where the offspring are created preserving the position of the genetic material taken from the parents. In this paper we ...
Evolving dynamic fitness measures for genetic programming
Highlights- Further research is conducted on dynamic fitness measure genetic programming.
- ...
AbstractThis research builds on the hypothesis that the use of different fitness measures on the different generations of genetic programming (GP) is more effective than the convention of applying the same fitness measure individually ...
Comments