The Compact Genetic Algorithm Struggles on Cliff Functions
Files
(Published version)
Date
2024
Authors
Neumann, F.
Sudholt, D.
Witt, C.
Editors
Fieldsend, J.E.
Wagner, M.
Wagner, M.
Advisors
Journal Title
Journal ISSN
Volume Title
Type:
Journal article
Citation
Algorithmica: an international journal in computer science, 2024; 87(4):507-536
Statement of Responsibility
Frank Neumann, Dirk Sudholt, Carsten Witt
Conference Name
Abstract
Estimation of distribution algorithms (EDAs) are general-purpose optimizers that maintain a probability distribution over a given search space. This probability distribution is updated through sampling from the distribution and a reinforcement learning process which rewards solution components that have shown to be part of good quality samples. The compact genetic algorithm (cGA) is a non-elitist EDA able to deal with difficult multimodal fitness landscapes that are hard to solve by elitist algorithms. We investigate the cGA on the Cliff function for which it was 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. Our experimental results indicate that the cGA requires exponential time for all values of the update strength 1/K. 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 K where the expected optimization time drops from n(n) to 2(n).
School/Discipline
Dissertation Note
Provenance
Description
Access Status
Rights
© The Author(s) 2024.Open Access This article is licensed under a Creative Commons Attribution 4.0 International License, which permits use, sharing, adaptation, distribution and reproduction in any medium or format, as long as you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons licence, and indicate if changes were made. The images or other third party material in this article are included in the article’s Creative Commons licence, unless indicated otherwise in a credit line to the material. If material is not included in the article’s Creative Commons licence and your intended use is not permitted by statutory regulation or exceeds the permitted use, you will need to obtain permission directly from the copyright holder. To view a copy of this licence, visit http://creativecommons.org/licenses/by/4.0/.