Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top
Published in:
One-Class Classification for Anomaly Detection with Kernel Density Estimation and Genetic Programming Read chapter Read first chapter

2016 | OriginalPaper | Chapter

On the Analysis of Simple Genetic Programming for Evolving Boolean Functions

Authors : Andrea Mambrini, Pietro S. Oliveto

Published in: Genetic Programming

Publisher: Springer International Publishing

Log in

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

Abstract

This work presents a first step towards a systematic time and space complexity analysis of genetic programming (GP) for evolving functions with desired input/output behaviour. Two simple GP algorithms, called (1+1) GP and (1+1) GP*, equipped with minimal function (F) and terminal (L) sets are considered for evolving two standard classes of Boolean functions. It is rigorously proved that both algorithms are efficient for the easy problem of evolving conjunctions of Boolean variables with the minimal sets. However, if an extra function (i.e. NOT) is added to F, then the algorithms require at least exponential time to evolve the conjunction of n variables. On the other hand, it is proved that both algorithms fail at evolving the difficult parity function in polynomial time with probability at least exponentially close to 1. Concerning generalisation, it is shown how the quality of the evolved conjunctions depends on the size of the training set s while the evolved exclusive disjunctions generalize equally badly independent of s.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

inform now
previous chapter Scheduling in Heterogeneous Networks Using Grammar-Based Genetic Programming
next chapter Genetic Programming Based Hyper-heuristics for Dynamic Job Shop Scheduling: Cooperative Coevolutionary Approaches
Footnotes
1
We assume the SUB and DEL of an empty tree return an empty tree.
 
2
Simplification is a conceptual tool used for the proofs. The actual tree contains all the variables (i.e., the algorithm does not simplify the trees).
 
Literature
1.
Auger, A., Doerr, B.: Theory of Randomized Search Heuristics: Foundations and Recent Developments. World Scientific, Singapore (2011)CrossRefMATH
2.
Droste, S., Jansen, T., Wegener, I.: On the analysis of the (1+1) evolutionary algorithm. Theor. Comput. Sci. 276(1–2), 51–81 (2002)MathSciNetCrossRefMATH
3.
Kötzing, T., Sutton, A.M., Neumann, F., O’Reilly, U.M.: The max problem revisited: the importance of mutation in genetic programming. Theor. Comp. Sci. 545, 94–107 (2014)MathSciNetCrossRefMATH
4.
Koza, J.R.: Genetic Programming: On the Programming of Computers by Means of Natural Selection. MIT Press, Cambridge (1992)MATH
5.
Koza, J.R.: Genetic Programming II: Automatic Discovery of Reusable Programs. MIT Press, Cambridge (1994)MATH
6.
7.
Luke, S.: Genetic programming produced competitive soccer softbot teams for RoboCup97. In: Proceedings of the Third Annual Conference on Genetic Programming 1998, pp. 214–222. Morgan Kaufmann (1998)
8.
Mitzenmacher, M., Upfal, E.: Probability and Computing. Cambridge University Press, Cambridge (2005)CrossRefMATH
9.
Moraglio, A., Mambrini, A., Manzoni, L.: Runtime analysis of mutation-based geometric semantic genetic programming on boolean functions. In: Proceedings of FOGA XII, pp. 119–132. ACM (2013)
10.
Neumann, F., O’Reilly, U.M., Wagner, M.: Computational complexity analysis of genetic programming - initial results and future directions. In: Riolo, R., Vladislavleva, E., Moore, J.H. (eds.) Genetic Programming Theory and Practice IX. Genetic and Evolutionary Computation, pp. 113–128. Springer, New York (2011)CrossRef
11.
Neumann, F., Witt, C.: Bioinspired Computation in Combinatorial Optimization: Algorithms and Their Computational Complexity. Natural Computing Series. Springer, Heidelberg (2010)CrossRefMATH
12.
Oliveto, P.S., Witt, C.: Simplified drift analysis for proving lower bounds in evolutionary computation. Algorithmica 59(3), 369–386 (2011)MathSciNetCrossRefMATH
13.
O’Neill, M., Vanneschi, L., Gustafson, S., Banzhaf, W.: Open issues in genetic programming. Genet. Program. Evolvable Mach. 11(3–4), 339–363 (2010)CrossRef
14.
O’Reilly, U.-M., Oppacher, F.: Program search with a hierarchical variable length representation: genetic programming, simulated annealing and hill climbing. In: Davidor, Y., Männer, R., Schwefel, H.-P. (eds.) PPSN 1994. LNCS, vol. 866, pp. 397–406. Springer, Heidelberg (1994)CrossRef
15.
16.
Poli, R., McPhee, N.F., Rowe, J.E.: Exact schema theory and Markov chain models for genetic programming and variable-length genetic algorithms with homologous crossover. Genet. Program. Evolvable Mach. 5(1), 31–70 (2004)CrossRef
17.
Spector, L., Barnum, H., Bernstein, H.J., Swamy, N.: Quantum computing applications of genetic programming. In: Spector, L., Langdon, W.B., O’Reilly, U.M., Angeline, P.J. (eds.) Advances in Genetic Programming 3, pp. 135–160. MIT Press, Cambridge (1999)
18.
Metadata
Title
On the Analysis of Simple Genetic Programming for Evolving Boolean Functions
Authors
Andrea Mambrini
Pietro S. Oliveto
Copyright Year
2016
Book
Genetic Programming

Print ISBN: 978-3-319-30667-4

Electronic ISBN: 978-3-319-30668-1

Copyright Year: 2016

DOI
https://doi.org/10.1007/978-3-319-30668-1_7

Premium Partner

    Image Credits