On the Analysis of Simple Genetic Programming for Evolving Boolean Functions

Created by W.Langdon from gp-bibliography.bib Revision:1.4420

  author =       "Andrea Mambrini and Pietro S. Oliveto",
  title =        "On the Analysis of Simple Genetic Programming for
                 Evolving Boolean Functions",
  booktitle =    "EuroGP 2016: Proceedings of the 19th European
                 Conference on Genetic Programming",
  year =         "2016",
  month =        "30 " # mar # "--1 " # apr,
  editor =       "Malcolm I. Heywood and James McDermott and 
                 Mauro Castelli and Ernesto Costa and Kevin Sim",
  series =       "LNCS",
  volume =       "9594",
  publisher =    "Springer Verlag",
  address =      "Porto, Portugal",
  pages =        "99--114",
  organisation = "EvoStar",
  keywords =     "genetic algorithms, genetic programming",
  isbn13 =       "978-3-319-30668-1",
  DOI =          "doi:10.1007/978-3-319-30668-1_7",
  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
  notes =        "Part of \cite{Heywood:2016:GP} EuroGP'2016 held in
                 conjunction with EvoCOP2016, EvoMusArt2016 and

Genetic Programming entries for Andrea Mambrini Pietro S Oliveto