Please use this identifier to cite or link to this item:
https://hdl.handle.net/2440/66825
Citations | ||
Scopus | Web of Science® | Altmetric |
---|---|---|
?
|
?
|
Type: | Conference paper |
Title: | Theoretical analysis of fitness-proportional selection: landscapes and efficiency |
Author: | Neumann, F. Oliveto, P. Witt, C. |
Citation: | Proceedings of the 11th Annual conference on Genetic and Evolutionary Computation: GECCO '09, pp.835-842 |
Publisher: | ACM Press |
Publisher Place: | New York |
Issue Date: | 2009 |
ISBN: | 9781605583259 |
Conference Name: | Genetic and Evolutionary Computation Conference (11th : 2009 : Montreal, Canada) |
Editor: | Rothlauf, F. |
Statement of Responsibility: | Frank Neumann, Pietro S. Oliveto, Carsten Witt |
Abstract: | We investigate theoretically how the fitness landscape influences the optimization process of population-based evolutionary algorithms using fitness-proportional selection. Considering the function OneMax, we show that it cannot be optimized in polynomial time with high probability regardless of the population size. This is proved by a generalization of drift analysis. For populations of at most logarithmic size, the negative result transfers to any function with unique optimum. Based on these insights, we investigate the effect of scaling the objective function in combination with a population that is not too small and show that then such algorithms compute optimal solutions for a wide range of problems in expected polynomial time. Finally, relationships with (1+λ)-EAs and (1,λ)-EAs are described. |
Keywords: | Genetic algorithms Running time analysis Selection Theory |
Rights: | Copyright 2009 ACM |
DOI: | 10.1145/1569901.1570016 |
Published version: | http://dx.doi.org/10.1145/1569901.1570016 |
Appears in Collections: | Aurora harvest 5 Computer Science publications |
Files in This Item:
There are no files associated with this item.
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.