Runtime Analysis of a Multi-valued Compact Genetic Algorithm on Generalized OneMax

A class of metaheuristic techniques called estimation-of-distribution algorithms (EDAs) is employed in optimization as a more sophisticated substitute for traditional strategies like evolutionary algorithms. EDAs generally drive the search for the optimum by creating probabilistic models of potential candidate solutions through repeated sampling and selection from the underlying search space. Most theoretical research on EDAs has focused on pseudo-Boolean optimization. Jedidia et al. (GECCO 2023) introduced a framework for EDAs for optimizing problems involving multi-valued decision variables. In addition, they conduct a mathematical runtime analysis of a multi-valued UMDA on the r-valued LeadingOnes function. Using their framework, here we focus on the multi-valued compact genetic algorithm ( \(r\) -cGA) and provide a first runtime analysis of a generalized OneMax function. To prove our results, we investigate the effect of genetic drift and progress of the probabilistic model towards the optimum. After finding the right algorithm parameters, we prove that the \(r\) -cGA solves this r-valued OneMax problem efficiently. We establish that the runtime bound is \(\text {O}(r^2 n \log ^2 r \log ^3 n)\) with high probability.