EUVIMEDEUVIMED entdecken
Crossref

Tail Bounds on the Runtime of Categorical Compact Genetic Algorithm

Ryoki Hamano iD, Kento Uchida iD, Shinichi Shirakawa iD, Daiki Morinaga iD, Youhei Akimoto iD

Evolutionary Computation · 2025

DOI: 10.1162/evco_a_00361 ↗

Kurz gefasst

Fachartikel in der Zeitschrift Evolutionary Computation, 2025. Verfasst von Ryoki Hamano und 4 weiteren Autor:innen. Beteiligte Einrichtung: CyberAgent, Inc., Tokyo, Japan hamano_ryoki_xa@cyberagent.co.jp. Hauptthemen laut MEDLINE: Algorithms, Models, Genetic. Die Arbeit wurde bisher 6-mal zitiert (Crossref) und nennt 30 Literaturangaben.

AbstractSchlagwörterBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

The majority of theoretical analyses of evolutionary algorithms in the discrete domain focus on binary optimization algorithms, even though black-box optimization on the categorical domain has many practical applications. In this paper, we consider a probabilistic model-based algorithm using the family of categorical distributions as its underlying distribution and set the sample size as two. We term this specific algorithm the categorical compact genetic algorithm (ccGA). The ccGA can be considered as an extension of the compact genetic algorithm (cGA), which is an efficient binary optimization algorithm. We theoretically analyze the dependency of the number of possible categories K, the number of dimensions D, and the learning rate η on the runtime. We investigate the tail bound of the runtime on two typical linear functions on the categorical domain: categorical OneMax (COM) and KVal. We derive that the runtimes on COM and KVal are O(Dln(DK)/η) and Θ(DlnK/η) with high probability, respectively. Our analysis is a generalization for that of the cGA on the binary domain.

Schlagwörter

MeSH-Schlagwörter (MEDLINE)

AlgorithmsModels, GeneticModels, StatisticalProbabilityComputer SimulationGenetic Algorithms

Stichwörter der Autor:innen

Runtime analysiscategorical optimization problemdrift theorem.

Autor:innen und Institutionen

  • CyberAgent, Inc., Tokyo, Japan hamano_ryoki_xa@cyberagent.co.jp.
  • Yokohama National University, Kanagawa, Japan uchida-kento-fz@ynu.ac.jp.
  • Yokohama National University, Kanagawa, Japan shirakawa-shinichi-bg@ynu.ac.jp.
  • University of Tsukuba, Ibaraki, Japan; RIKEN Center for Advanced Intelligence Project, Tokyo, Japan morinaga@bbo.cs.tsukuba.ac.jp.
  • University of Tsukuba, Ibaraki, Japan; RIKEN Center for Advanced Intelligence Project, Tokyo, Japan akimoto@cs.tsukuba.ac.jp.

ORCID-Profile: Ryoki Hamano, Kento Uchida, Shinichi Shirakawa, Daiki Morinaga, Youhei Akimoto

Zitieren

APA

Hamano, R., Uchida, K., Shirakawa, S., Morinaga, D., & Akimoto, Y. (2025). Tail Bounds on the Runtime of Categorical Compact Genetic Algorithm. Evolutionary Computation. https://doi.org/10.1162/evco_a_00361

Vancouver

Hamano R, Uchida K, Shirakawa S, Morinaga D, Akimoto Y. Tail Bounds on the Runtime of Categorical Compact Genetic Algorithm. Evolutionary Computation. 2025. doi:10.1162/evco_a_00361

BibTeX
@article{Hamano2025,
  author = {Hamano, Ryoki and Uchida, Kento and Shirakawa, Shinichi and Morinaga, Daiki and Akimoto, Youhei},
  title = {Tail Bounds on the Runtime of Categorical Compact Genetic Algorithm},
  journal = {Evolutionary Computation},
  year = {2025},
  doi = {10.1162/evco_a_00361}
}
Kostenlos starten →