@inproceedings{6f843227b64e422999a6f733e07f9fa5,
title = "A Runtime Analysis of the Multi-valued Compact Genetic Algorithm on Generalized LeadingOnes",
abstract = "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 and Witt 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(n2r2log3nlog2r) with high probability.",
keywords = "Estimation of distribution algorithms, LeadingOnes, Genetic drift, Multi-valued compact genetic algorithm",
author = "Sumit Adak and Carsten Witt",
year = "2025",
doi = "10.1007/978-3-031-86849-8\_1",
language = "English",
isbn = "978-3-031-86848-1",
volume = "15610",
series = "Lecture Notes in Computer Science",
publisher = "Springer",
pages = "1--17",
booktitle = "25th European Conference on Evolutionary Computation in Combinatorial Optimization, EvoCOP 2025",
note = "25th European Conference on Evolutionary Computation in Combinatorial Optimization, EvoStar ; Conference date: 23-04-2025 Through 25-04-2025",
}