Single- and Multi-Objective Genetic Programming: New Bounds for Weighted ORDER and MAJORITY

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

@InProceedings{Nguyen:2013:foga,

• author = "Anh Nguyen and Tommaso Urli and Markus Wagner",
• title = "Single- and Multi-Objective Genetic Programming: New Bounds for Weighted ORDER and MAJORITY",
• booktitle = "Foundations of Genetic Algorithms",
• year = "2013",
• editor = "Frank Neumann and Kenneth {De Jong}",
• pages = "161--172",
• address = "Adelaide, Australia",
• month = "16-20 " # jan,
• organisation = "SigEvo",
• publisher = "ACM",
• keywords = "genetic algorithms, genetic programming, Multi-objective Optimisation, Theory, Runtime Analysis",
• isbn13 = "978-1-4503-1990-4",
• URL = "http://cs.adelaide.edu.au/~markus/pub/2013foga-gp.pdf",
• URL = "http://doi.acm.org/10.1145/2460239.2460254",
• DOI = "doi:10.1145/2460239.2460254",
• acmid = "2460254",
• size = "12 pages",
• abstract = "We consolidate the existing computational complexity analysis of genetic programming (GP) by bringing together sound theoretical proofs and empirical analysis. In particular, we address computational complexity issues arising when coupling algorithms using variable length representation, such as GP itself, with different bloat-control techniques. In order to accomplish this, we first introduce several novel upper bounds for two single- and multi-objective GP algorithms on the generalised Weighted ORDER and MAJORITY problems. To obtain these, we employ well-established computational complexity analysis techniques such as fitness-based partitions, and for the first time, additive and multiplicative drift.

  The bounds we identify depend on two measures, the maximum tree size and the maximum population size, that arise during the optimisation run and that have a key relevance in determining the run time of the studied GP algorithms. In order to understand the impact of these measures on a typical run, we study their magnitude experimentally, and we discuss the obtained findings.",

• notes = "Anh Quang Nguyen Jan 2013: 2013foga-gp.pdf is preproceedings version. Jan 2014: note title change.

  Section 6 'theoretical investigations to complement the recent results on the runtime of two genetic programming algorithms \cite{Durrett:2011:foga} \cite{Neumann:2012:GECCO} \cite{conf/ppsn/UrliWN12}'

  Also known as \cite{Nguyen:2013:SMG:2460239.2460254}. http://www.sigevo.org/foga-2013/index.html",

}

Genetic Programming entries for Anh Quang Nguyen Tommaso Urli Markus Wagner

Citations