Please use this identifier to cite or link to this item:
https://hdl.handle.net/2440/83834
Citations | ||
Scopus | Web of ScienceĀ® | Altmetric |
---|---|---|
?
|
?
|
Type: | Conference paper |
Title: | Single- and multi-objective genetic programming: new bounds for weighted order and majority |
Author: | Nguyen, A. Urli, T. Wagner, M. |
Citation: | Proceedings of the 12th Workshop on Foundations of Genetic Algorithms, FOGA XII, 2013 / pp.161-172 |
Publisher: | ACM |
Publisher Place: | online |
Issue Date: | 2013 |
ISBN: | 9781450319904 |
Conference Name: | Workshop on Foundations of Genetic Algorithms (12th : 2013 : Adelaide, Australia) |
Editor: | Neumann, F. Jong, K.A.D. |
Statement of Responsibility: | Anh Nguyen, Tommaso Urli, Markus Wagner |
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 optimization run and that have a key relevance in determining the runtime 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. |
Keywords: | Genetic Programming Multi-objective Optimization Theory Runtime Analysis |
Rights: | Copyright 2013 ACM |
DOI: | 10.1145/2460239.2460254 |
Description (link): | http://www.sigevo.org/foga-2013/ |
Published version: | http://dx.doi.org/10.1145/2460239.2460254 |
Appears in Collections: | Aurora harvest 4 Computer Science publications |
Files in This Item:
File | Description | Size | Format | |
---|---|---|---|---|
RA_hdl_83834.pdf | Restricted Access | 2.72 MB | Adobe PDF | View/Open |
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.