Estimation of distribution algorithms (EDAs) are powerful optimization techniques that iteratively build probabilistic models based on the best performing solutions, thereby guiding the search process in complex solution landscapes. Classical EDAs handle only binary decision variables, but recent developments have introduced multi-valued EDAs to tackle problems with variables taking more than two values. Despite their growing importance, the theoretical understanding of multi-valued EDAs, especially regarding runtime behavior, remains limited. In this work, we provide theoretical analyses of the multi-valued compact genetic algorithm ( r ‑cGA) on the generalized (multi-valued) LeadingOnes and OneMax benchmark problems. We derive the first runtime bound for the r ‑cGA on the r -valued LeadingOnes function, together with an improved runtime for the r -valued OneMax function. These results also improve and refine previous theoretical analyses of the r ‑cGA, providing new insights into the performance of multi-valued EDAs. In addition, we for the first time include the case of frequency borders in the runtime analysis of the r ‑cGA.

The Compact Genetic Algorithm (cGA) is an estimation-of-distribution algorithm that has been receiving much attention especially in the runtime analysis community in recent years. It comes with a single parameter K determining its strength of updates. Contrary to other estimation-of-distribution algorithms like the UMDA, the standard cGA does not have a parameter controlling its selection pressure.

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.