research-article

Genetic programming for finite algebras

Authors:

David M. Clark,

Jon KleinAuthors Info & Claims

GECCO '08: Proceedings of the 10th annual conference on Genetic and evolutionary computation

Pages 1291 - 1298

https://doi.org/10.1145/1389095.1389343

Published: 12 July 2008 Publication History

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]

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.

Digital Library

[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]

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.

Digital Library

[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.

Digital Library

[13]

J. R. Koza. Genetic Programming: On the Programming of Computers by Means of Natural Selection. MIT Press, Cambridge, MA, USA, 1992.

Digital Library

[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.

Digital Library

[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.

Digital Library

[25]

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.

Digital Library

[26]

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.

Digital Library

[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. 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.

Digital Library

Cited By

Habiballa HVolna EKotyrba M(2021)Automated Generation of EQ-Algebras through Genetic AlgorithmsMathematics10.3390/math90808619:8(861)Online publication date: 14-Apr-2021
https://doi.org/10.3390/math9080861
Danai KLa Cava W(2021)Controller design by symbolic regressionMechanical Systems and Signal Processing10.1016/j.ymssp.2020.107348151(107348)Online publication date: Apr-2021
https://doi.org/10.1016/j.ymssp.2020.107348
Liskowski PKrawiec KToklu NSwan JCoello Coello C(2020)Program synthesis as latent continuous optimizationProceedings of the 2020 Genetic and Evolutionary Computation Conference10.1145/3377930.3390213(359-367)Online publication date: 25-Jun-2020
https://dl.acm.org/doi/10.1145/3377930.3390213
Show More Cited By

Index Terms

Genetic programming for finite algebras
1. Computing methodologies
  1. Symbolic and algebraic manipulation
    1. Symbolic and algebraic algorithms
      1. Algebraic algorithms

Recommendations

Neural network crossover in genetic algorithms using genetic programming
Abstract
The 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.
- ...
Abstract
This 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

Information & Contributors

Information

Published In

cover image ACM Conferences

GECCO '08: Proceedings of the 10th annual conference on Genetic and evolutionary computation

July 2008

1814 pages

ISBN:9781605581309

DOI:10.1145/1389095

Conference Chair:
Conor Ryan
University of Limerick, Ireland
,
Editor:
Maarten Keijzer
Chordiant Software International B.V., The Netherlands

Copyright © 2008 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 12 July 2008

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

GECCO08

Sponsor:

GECCO08: Genetic and Evolutionary Computation Conference

July 12 - 16, 2008

GA, Atlanta, USA

Acceptance Rates

Overall Acceptance Rate 1,669 of 4,410 submissions, 38%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

46
Total Citations
View Citations
182
Total Downloads

Downloads (Last 12 months)3
Downloads (Last 6 weeks)0

Reflects downloads up to 08 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

Habiballa HVolna EKotyrba M(2021)Automated Generation of EQ-Algebras through Genetic AlgorithmsMathematics10.3390/math90808619:8(861)Online publication date: 14-Apr-2021
https://doi.org/10.3390/math9080861
Danai KLa Cava W(2021)Controller design by symbolic regressionMechanical Systems and Signal Processing10.1016/j.ymssp.2020.107348151(107348)Online publication date: Apr-2021
https://doi.org/10.1016/j.ymssp.2020.107348
Liskowski PKrawiec KToklu NSwan JCoello Coello C(2020)Program synthesis as latent continuous optimizationProceedings of the 2020 Genetic and Evolutionary Computation Conference10.1145/3377930.3390213(359-367)Online publication date: 25-Jun-2020
https://dl.acm.org/doi/10.1145/3377930.3390213
Clemens SIskander MYun ZChao G(2020)Genetic Programming for Coplanar Waveguide Continuous Transverse Stub Antenna Array Design2020 IEEE International Symposium on Antennas and Propagation and North American Radio Science Meeting10.1109/IEEECONF35879.2020.9329544(1949-1950)Online publication date: 5-Jul-2020
https://doi.org/10.1109/IEEECONF35879.2020.9329544
Liskowski PKrawiec KToklu N(2020)Neuromemetic Evolutionary OptimizationParallel Problem Solving from Nature – PPSN XVI10.1007/978-3-030-58112-1_43(623-636)Online publication date: 31-Aug-2020
https://doi.org/10.1007/978-3-030-58112-1_43
Spector LMcPhee NSpector LClark DLindsay IBarr BKlein JAuger AStützle T(2019)PushProceedings of the Genetic and Evolutionary Computation Conference Companion10.1145/3319619.3323392(1175-1196)Online publication date: 13-Jul-2019
https://dl.acm.org/doi/10.1145/3319619.3323392
Moore JOlson RChen YSipper M(2019)Automated discovery of test statistics using genetic programmingGenetic Programming and Evolvable Machines10.1007/s10710-018-9338-z20:1(127-137)Online publication date: 1-Mar-2019
https://dl.acm.org/doi/10.1007/s10710-018-9338-z
Veiga RBarbosa HBernardino HFreitas JFeitosa CMatos SAlcântara-Neves NBarreto M(2018)Multiobjective grammar-based genetic programming applied to the study of asthma and allergy epidemiologyBMC Bioinformatics10.1186/s12859-018-2233-z19:1Online publication date: 26-Jun-2018
https://doi.org/10.1186/s12859-018-2233-z
Spector LMcPhee NTakadama K(2018)Expressive genetic programmingProceedings of the Genetic and Evolutionary Computation Conference Companion10.1145/3205651.3207867(977-997)Online publication date: 6-Jul-2018
https://dl.acm.org/doi/10.1145/3205651.3207867
Liskowski PWieloch BKrawiec KTakadama K(2018)Neural estimation of interaction outcomesProceedings of the Genetic and Evolutionary Computation Conference10.1145/3205455.3205600(1055-1062)Online publication date: 2-Jul-2018
https://dl.acm.org/doi/10.1145/3205455.3205600
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Figures

Tables

Media

View Table of Conten