On the Analysis of Simple Genetic Programming for Evolving Boolean Functions
Created by W.Langdon from
gp-bibliography.bib Revision:1.8028
- @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