Mathematical runtime analysis of a multi-Valued estimation of distribution algorithm

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.