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

Sumit Adak*, Carsten Witt

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingArticle in proceedingsResearchpeer-review

Abstract

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 O(r2n log2 r log3 n) with high probability.
Original languageEnglish
Title of host publication18th International Conference on Parallel Problem Solving From Nature PPSN 2024
PublisherSpringer
Publication date2024
Pages53-69
ISBN (Print)978-3-031-70070-5
ISBN (Electronic)978-3-031-70071-2
DOIs
Publication statusPublished - 2024
Event18th International Conference on Parallel Problem Solving From Nature
- Hagenberg, Austria
Duration: 14 Sept 202418 Sept 2024

Conference

Conference18th International Conference on Parallel Problem Solving From Nature
Country/TerritoryAustria
CityHagenberg
Period14/09/202418/09/2024

Keywords

  • Estimation-of-distribution algorithms
  • Multi-valued compact genetic algorithm
  • Genetic drift
  • OneMax

Fingerprint

Dive into the research topics of 'Runtime Analysis of a Multi-valued Compact Genetic Algorithm on Generalized OneMax'. Together they form a unique fingerprint.

Cite this