The Compact Genetic Algorithm Struggles on Cliff Functions
The compact genetic algorithm (cGA) is an 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 $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^{\Theta(n)}$ to $2^{\Theta(n)}$.
Code (0)
등록된 구현이 없습니다.
Tasks
Evolutionary AlgorithmsSimilar Papers 제목 키워드 기반
Tail Bounds on the Runtime of Categorical Compact Genetic Algorithm
The majority of theoretical analyses of evolutionary algorithms in the discrete domain focus on binary optimization algorithms, even though black-box optimization on the categorical domain has a lot of practical applicat…
Evolutionary AlgorithmsHow Well Does the Metropolis Algorithm Cope With Local Optima?
The Metropolis algorithm (MA) is a classic stochastic local search heuristic. It avoids getting stuck in local optima by occasionally accepting inferior solutions. To better and in a rigorous manner understand this abili…
Evolutionary AlgorithmsQuaternionic Fourier-Mellin Transform
In this contribution we generalize the classical Fourier Mellin transform [S. Dorrode and F. Ghorbel, Robust and efficient Fourier-Mellin transform approximations for gray-level image reconstruction and complete invarian…
Image ReconstructionT-Count Optimizing Genetic Algorithm for Quantum State Preparation
Quantum state preparation is a crucial process within numerous quantum algorithms, and the need for efficient initialization of quantum registers is ever increasing as demand for useful quantum computing grows. The probl…
Efficient Noisy Optimisation with the Sliding Window Compact Genetic Algorithm
The compact genetic algorithm is an Estimation of Distribution Algorithm for binary optimisation problems. Unlike the standard Genetic Algorithm, no cross-over or mutation is involved. Instead, the compact Genetic Algori…