Please use this identifier to cite or link to this item:
Scopus Web of Science® Altmetric
Type: Conference paper
Title: PAC learning and genetic programming
Author: Kotzing, T.
Neumann, F.
Spohel, R.
Citation: GECCO'11: Proceedings of the 13th Annual Conference on Genetic and Evolutionary Computation, held in Dublin, Ireland, 12-16 July, 2011: pp.2091-2096
Publisher: ACM Press
Publisher Place: New York
Issue Date: 2011
ISBN: 9781450305570
Conference Name: Genetic and Evolutionary Computation Conference (13th : 2011 : Dublin, Ireland)
Statement of
Timo Kötzing, Frank Neumann and Reto Spöhel
Abstract: Genetic programming (GP) is a very successful type of learning algorithm that is hard to understand from a theoretical point of view. With this paper we contribute to the computational complexity analysis of genetic programming that has been started recently. We analyze GP in the well-known PAC learning framework and point out how it can observe quality changes in the the evolution of functions by random sampling. This leads to computational complexity bounds for a linear GP algorithm for perfectly learning any member of a simple class of linear pseudo-Boolean functions. Furthermore, we show that the same algorithm on the functions from the same class finds good approximations of the target function in less time.
Keywords: Genetic programming; PAC learning; theory; runtime analysis
Rights: Copyright 2011 ACM
RMID: 0020118207
DOI: 10.1145/2001576.2001857
Published version:
Appears in Collections:Computer Science publications

Files in This Item:
File Description SizeFormat 
RA_hdl_71908.pdfRestricted Access511.41 kBAdobe PDFView/Open

Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.