A Runtime Analysis of the Multi-valued Compact Genetic Algorithm on Generalized LeadingOnes

Sumit Adak*, Carsten Witt

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingArticle in proceedingsResearch

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.
Original languageEnglish
Title of host publication25th European Conference on Evolutionary Computation in Combinatorial Optimization, EvoCOP 2025
Volume15610
PublisherSpringer
Publication date2025
Pages1-17
ISBN (Print)978-3-031-86848-1
ISBN (Electronic)978-3-031-86849-8
DOIs
Publication statusPublished - 2025
Event25th European Conference on Evolutionary Computation in Combinatorial Optimization - Trieste, Italy
Duration: 23 Apr 202525 Apr 2025

Conference

Conference25th European Conference on Evolutionary Computation in Combinatorial Optimization
Country/TerritoryItaly
CityTrieste
Period23/04/202525/04/2025
SeriesLecture Notes in Computer Science
ISSN0302-9743

Keywords

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

Fingerprint

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

Cite this