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 runtime analysis of the multi-valued UMDA on the r-valued LeadingOnes (r-LeadingOnes) functions and Adak et al. gave the first runtime analysis of the multi-valued cGA (r-cGA) on the r-valued OneMax function. We utilize their framework to conduct an analysis of the multi-valued cGA on the r-valued LeadingOnes function. Even for the binary case, a runtime analysis of the classical cGA on LeadingOnes was not yet available. In this work, we show that the runtime of the r-cGA on r-LeadingOnes is O(n^2r^2 log^3 n log^2 r) with high probability.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
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 AlgorithmsRuntime 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 …
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 U…
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 AlgorithmsEstimation-of-Distribution Algorithms for Multi-Valued Decision Variables
The majority of research on estimation-of-distribution algorithms (EDAs) concentrates on pseudo-Boolean optimization and permutation problems, leaving the domain of EDAs for problems in which the decision variables can t…