Improved Runtime Analysis of a Multi-Valued Compact Genetic Algorithm on Two Generalized OneMax Problems
Recent research in the runtime analysis of estimation of distribution algorithms (EDAs) has focused on univariate EDAs for multi-valued decision variables. In particular, the runtime of the multi-valued cGA (r-cGA) and UMDA on multi-valued functions has been a significant area of study. Adak and Witt (PPSN 2024) and Hamano et al. (ECJ 2024) independently performed a first runtime analysis of the r-cGA on the r-valued OneMax function (r-OneMax). Adak and Witt also introduced a different r-valued OneMax function called G-OneMax. However, for that function, only empirical results were provided so far due to the increased complexity of its runtime analysis, since r-OneMax involves categorical values of two types only, while G-OneMax encompasses all possible values. In this paper, we present the first theoretical runtime analysis of the r-cGA on the G-OneMax function. We demonstrate that the runtime is O(nr^3 log^2 n log r) with high probability. Additionally, we refine the previously established runtime analysis of the r-cGA on r-OneMax, improving the previous bound to O(nr log n log r), which improves the state of the art by an asymptotic factor of log n and is tight for the binary case. Moreover, we for the first time include the case of frequency borders.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
Runtime Analysis of a Compact Genetic Algorithm on a Truly Multi-valued OneMax Function
Recently, the runtime analysis of multi-valued estimation-of-distribution algorithms in the framework of Ben Jedidia et al. (TCS 2024) has made significant advancements. However, almost all existing analyses are limited …
A Runtime Analysis of the Multi-Valued Compact Genetic Algorithm on Generalized LeadingOnes
In the literature on runtime analyses of estimation of distribution algorithms (EDAs), researchers have recently explored univariate EDAs for multi-valued decision variables. Particularly, Jedidia et al. gave the first r…
Runtime Analysis of a Multi-Valued Compact Genetic Algorithm on Generalized OneMax
A class of metaheuristic techniques called estimation-of-distribution algorithms (EDAs) are employed in optimization as more sophisticated substitutes for traditional strategies like evolutionary algorithms. EDAs general…
Evolutionary AlgorithmsUnderstanding weight-magnitude hyperparameters in training binary networks
Binary Neural Networks (BNNs) are compact and efficient by using binary weights instead of real-valued weights. Current BNNs use latent real-valued weights during training, where several training hyper-parameters are inh…
The Runtime of the Compact Genetic Algorithm on Jump Functions
In the first and so far only mathematical runtime analysis of an estimation-of-distribution algorithm (EDA) on a multimodal problem, Hasen\"ohrl and Sutton (GECCO 2018) showed for any $k = o(n)$ that the compact genetic …
4kEvolutionary Algorithms