Please use this identifier to cite or link to this item:
https://hdl.handle.net/2440/136645
Citations | ||
Scopus | Web of Scienceยฎ | Altmetric |
---|---|---|
?
|
?
|
Type: | Conference paper |
Title: | The compact genetic algorithm struggles on Cliff functions |
Author: | Neumann, F. Sudholt, D. Witt, C. |
Citation: | Proceedings of the Genetic and Evolutionary Computation Conference (GECCO'22), 2022 / Fieldsend, J.E. (ed./s), vol.abs/2204.04904, pp.1426-1433 |
Publisher: | Association for Computing Machinery |
Publisher Place: | New York, NY |
Issue Date: | 2022 |
ISBN: | 9781450392372 |
Conference Name: | Genetic and Evolutionary Computation Conference (GECCO) (9 Jul 2022 - 13 Jul 2022 : virtual online) |
Editor: | Fieldsend, J.E. |
Statement of Responsibility: | Frank Neumann, Dirk Sudholt, Carsten Witt |
Abstract: | The compact genetic algorithm (cGA) is a non-elitist estimation of distribution algorithm which has shown to be able to deal with difficult multimodal fitness landscapes that are hard to solve by elitist algorithms. In this paper, we investigate the cGA on the Cliff function for which it has been shown recently that non-elitist evolutionary algorithms and artificial immune systems optimize it in expected polynomial time. We point out that the cGA faces major difficulties when solving the Cliff function and investigate its dynamics both experimentally and theoretically around the Cliff. Our experimental results indicate that the cGA requires exponential time for all values of the update strength ๐พ. We show theoretically that, under sensible assumptions, there is a negative drift when sampling around the location of the cliff. Experiments further suggest that there is a phase transition for ๐พ where the expected optimization time drops from ๐ฮ(๐) to 2ฮ(๐) . |
Keywords: | Estimation-of-distribution algorithms; compact genetic algorithm, evolutionary algorithms; running time analysis; theory |
Rights: | ยฉ 2022 Copyright held by the owner/author(s). Publication rights licensed to ACM.en |
DOI: | 10.1145/3512290.3528776 |
Grant ID: | http://purl.org/au-research/grants/arc/FT200100536 |
Published version: | https://dl.acm.org/doi/proceedings/10.1145/3512290 |
Appears in Collections: | 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.