On the Analysis of Simple Genetic Programming for Evolving Boolean Functions

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

@InProceedings{Mambrini:2016:EuroGP,

• 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 $s$.",
• notes = "Part of \cite{Heywood:2016:GP} EuroGP'2016 held in conjunction with EvoCOP2016, EvoMusArt2016 and EvoApplications2016",

}

Genetic Programming entries for Andrea Mambrini Pietro S Oliveto

Citations