{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,14]],"date-time":"2026-02-14T11:06:22Z","timestamp":1771067182092,"version":"3.50.1"},"reference-count":30,"publisher":"MIT Press","issue":"2","content-domain":{"domain":["direct.mit.edu"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2025,6,2]]},"abstract":"<jats:p>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 \u03b7 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)\/\u03b7) and \u0398(DlnK\/\u03b7) with high probability, respectively. Our analysis is a generalization for that of the cGA on the binary domain.<\/jats:p>","DOI":"10.1162\/evco_a_00361","type":"journal-article","created":{"date-parts":[[2024,10,1]],"date-time":"2024-10-01T20:19:28Z","timestamp":1727813968000},"page":"141-189","update-policy":"https:\/\/doi.org\/10.1162\/mitpressjournals.corrections.policy","source":"Crossref","is-referenced-by-count":4,"title":["Tail Bounds on the Runtime of Categorical Compact Genetic Algorithm"],"prefix":"10.1162","volume":"33","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-4425-1683","authenticated-orcid":true,"given":"Ryoki","family":"Hamano","sequence":"first","affiliation":[{"name":"CyberAgent, Inc., Tokyo, Japan hamano_ryoki_xa@cyberagent.co.jp"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-4179-6020","authenticated-orcid":true,"given":"Kento","family":"Uchida","sequence":"additional","affiliation":[{"name":"Yokohama National University, Kanagawa, Japan uchida-kento-fz@ynu.ac.jp"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-4659-6108","authenticated-orcid":true,"given":"Shinichi","family":"Shirakawa","sequence":"additional","affiliation":[{"name":"Yokohama National University, Kanagawa, Japan shirakawa-shinichi-bg@ynu.ac.jp"}]},{"ORCID":"https:\/\/orcid.org\/0009-0009-7937-7567","authenticated-orcid":true,"given":"Daiki","family":"Morinaga","sequence":"additional","affiliation":[{"name":"University of Tsukuba, Ibaraki, Japan; RIKEN Center for Advanced Intelligence Project, Tokyo, Japan morinaga@bbo.cs.tsukuba.ac.jp"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-2760-8123","authenticated-orcid":true,"given":"Youhei","family":"Akimoto","sequence":"additional","affiliation":[{"name":"University of Tsukuba, Ibaraki, Japan; RIKEN Center for Advanced Intelligence Project, Tokyo, Japan akimoto@cs.tsukuba.ac.jp"}]}],"member":"281","published-online":{"date-parts":[[2025,6,2]]},"reference":[{"key":"2025060207554936300_B1","doi-asserted-by":"crossref","DOI":"10.1201\/9781420011326","volume-title":"Genetic algorithms and genetic programming: Modern concepts and practical applications","author":"Affenzeller","year":"2009"},{"key":"2025060207554936300_B2","first-page":"1","article-title":"Objective improvement in information-geometric optimization","author":"Akimoto","year":"2013","journal-title":"Proceedings of the Twelfth Workshop on Foundations of Genetic Algorithms XII"},{"key":"2025060207554936300_B3","first-page":"171","article-title":"Adaptive stochastic natural gradient method for one-shot neural architecture search","volume":"97","author":"Akimoto","year":"2019","journal-title":"Proceedings of the 36th International Conference on Machine Learning"},{"key":"2025060207554936300_B4","doi-asserted-by":"publisher","first-page":"251","DOI":"10.1162\/089976698300017746","article-title":"Natural gradient works efficiently in learning","volume":"10","author":"Amari","year":"1998","journal-title":"Neural Computation"},{"key":"2025060207554936300_B5","doi-asserted-by":"crossref","first-page":"230","DOI":"10.1145\/3583131.3590523","article-title":"Estimation-of-distribution algorithms for multi-valued decision variables","author":"Jedidia","year":"2023","journal-title":"Proceedings of the Genetic and Evolutionary Computation Conference (GECCO)"},{"issue":"4","key":"2025060207554936300_B6","doi-asserted-by":"publisher","first-page":"2137","DOI":"10.1109\/TCBB.2021.3066597","article-title":"Compact genetic algorithm-based feature selection for sequence-based prediction of dengue\u2013human protein interactions","volume":"19","author":"Dey","year":"2022","journal-title":"IEEE\/ACM Transactions on Computational Biology and Bioinformatics"},{"key":"2025060207554936300_B7","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/s00453-020-00780-w","article-title":"The runtime of the compact genetic algorithm on jump functions","volume":"83","author":"Doerr","year":"2021","journal-title":"Algorithmica"},{"key":"2025060207554936300_B8","first-page":"174","article-title":"Drift analysis with tail bounds","author":"Doerr","year":"2010","journal-title":"Parallel Problem Solving from Nature"},{"issue":"6","key":"2025060207554936300_B9","doi-asserted-by":"publisher","first-page":"1140","DOI":"10.1109\/TEVC.2020.2987361","article-title":"Sharp bounds for genetic drift in estimation of distribution algorithms","volume":"24","author":"Doerr","year":"2020","journal-title":"IEEE Transactions on Evolutionary Computation"},{"issue":"3","key":"2025060207554936300_B10","doi-asserted-by":"publisher","first-page":"257","DOI":"10.1007\/s11047-006-9001-0","article-title":"A rigorous analysis of the compact genetic algorithm for linear functions","volume":"5","author":"Droste","year":"2006","journal-title":"Natural Computing"},{"issue":"10","key":"2025060207554936300_B11","doi-asserted-by":"publisher","first-page":"3545","DOI":"10.1016\/j.spa.2012.06.009","article-title":"Hoeffding's inequality for supermartingales","volume":"122","author":"Fan","year":"2012","journal-title":"Stochastic Processes and their Applications"},{"issue":"3","key":"2025060207554936300_B12","first-page":"477","article-title":"The compact genetic algorithm is efficient under extreme Gaussian noise","volume":"21","author":"Friedrich","year":"2017","journal-title":"IEEE Transactions on Evolutionary Computation"},{"key":"2025060207554936300_B13","doi-asserted-by":"publisher","first-page":"1105","DOI":"10.1109\/LAWP.2015.2494839","article-title":"Modified compact genetic algorithm for thinned array synthesis","volume":"15","author":"Ha","year":"2016","journal-title":"IEEE Antennas and Wireless Propagation Letters"},{"key":"2025060207554936300_B14","doi-asserted-by":"publisher","first-page":"287","DOI":"10.1109\/4235.797971","article-title":"The compact genetic algorithm","volume":"3","author":"Harik","year":"1999","journal-title":"IEEE Transactions on Evolutionary Computation"},{"key":"2025060207554936300_B15","doi-asserted-by":"crossref","first-page":"967","DOI":"10.1145\/3205455.3205608","article-title":"On the runtime dynamics of the compact genetic algorithm on jump functions","author":"Hasen\u00f6hrl","year":"2018","journal-title":"Proceedings of the 20th Annual Conference on Genetic and Evolutionary Computation Conference (GECCO)"},{"key":"2025060207554936300_B16","first-page":"1391","article-title":"Concentration of first hitting times under additive drift","author":"K\u00f6tzing","year":"2014","journal-title":"Proceedings of the 16th Annual Conference on Genetic and Evolutionary Computation (GECCO)"},{"issue":"3","key":"2025060207554936300_B17","doi-asserted-by":"crossref","first-page":"490","DOI":"10.1007\/s00453-015-0048-0","article-title":"Concentration of first hitting times under additive drift","volume":"75","author":"K\u00f6tzing","year":"2016","journal-title":"Algorithmica"},{"key":"2025060207554936300_B18","first-page":"1","article-title":"Encoding categorical variables in physics-informed graphs for Bayesian optimization","author":"Krummenauer","year":"2022","journal-title":"2022 IEEE International Conference on Omni-layer Intelligent Systems"},{"issue":"4","key":"2025060207554936300_B19","doi-asserted-by":"publisher","first-page":"550","DOI":"10.1017\/S0963548320000565","article-title":"Tail bounds on hitting times of randomized search heuristics using variable drift analysis","volume":"30","author":"Lehre","year":"2021","journal-title":"Combinatorics, Probability and Computing"},{"issue":"4","key":"2025060207554936300_B20","doi-asserted-by":"publisher","first-page":"1096","DOI":"10.1007\/s00453-020-00778-4","article-title":"The complex parameter landscape of the compact genetic algorithm","volume":"83","author":"Lengler","year":"2021","journal-title":"Algorithmica"},{"key":"2025060207554936300_B21","article-title":"Combinatorial Bayesian optimization using the graph Cartesian product","volume-title":"Advances in Neural Information Processing Systems","author":"Oh","year":"2019"},{"issue":"3","key":"2025060207554936300_B22","doi-asserted-by":"publisher","first-page":"369","DOI":"10.1007\/s00453-010-9387-z","article-title":"Simplified drift analysis for proving lower bounds in evolutionary computation","volume":"59","author":"Oliveto","year":"2011","journal-title":"Algorithmica"},{"key":"2025060207554936300_B23","article-title":"Erratum: Simplified drift analysis for proving lower bounds in evolutionary computation","author":"Oliveto","year":"2012"},{"issue":"1","key":"2025060207554936300_B24","first-page":"564","article-title":"Information-geometric optimization algorithms: A unifying picture via invariance principles","volume":"18","author":"Ollivier","year":"2017","journal-title":"Journal of Machine Learning Research"},{"key":"2025060207554936300_B25","doi-asserted-by":"publisher","first-page":"20","DOI":"10.1016\/j.tcs.2013.09.036","article-title":"The choice of the offspring population size in the (1,\u03bb) evolutionary algorithm","volume":"545","author":"Rowe","year":"2014","journal-title":"Theoretical Computer Science"},{"key":"2025060207554936300_B26","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-018-0480-z","article-title":"On the choice of the update strength in estimation-of-distribution algorithms and ant colony optimization","volume":"81","author":"Sudholt","year":"2019","journal-title":"Algorithmica"},{"issue":"6","key":"2025060207554936300_B27","doi-asserted-by":"publisher","first-page":"1035","DOI":"10.1109\/TEVC.2019.2917709","article-title":"Finite-sample analysis of information geometric optimization with isotropic Gaussian distribution on convex quadratic functions","volume":"24","author":"Uchida","year":"2020","journal-title":"IEEE Transactions on Evolutionary Computation"},{"key":"2025060207554936300_B28","doi-asserted-by":"crossref","first-page":"1539","DOI":"10.1145\/3205455.3205581","article-title":"Domino convergence: Why one should hill-climb on linear functions","author":"Witt","year":"2018","journal-title":"Proceedings of the 20th Annual Conference on Genetic and Evolutionary Computation (GECCO)"},{"key":"2025060207554936300_B29","first-page":"73","volume-title":"The differential equation method for random graph processes and greedy algorithms","author":"Wormald","year":"1999"},{"issue":"4","key":"2025060207554936300_B30","doi-asserted-by":"publisher","first-page":"809","DOI":"10.1007\/s10489-011-0298-8","article-title":"A compact genetic algorithm for the network coding based resource minimization problem","volume":"36","author":"Xing","year":"2012","journal-title":"Applied Intelligence"}],"container-title":["Evolutionary Computation"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/direct.mit.edu\/evco\/article-pdf\/33\/2\/141\/2484183\/evco_a_00361.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/direct.mit.edu\/evco\/article-pdf\/33\/2\/141\/2484183\/evco_a_00361.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,2]],"date-time":"2025-06-02T11:56:01Z","timestamp":1748865361000},"score":1,"resource":{"primary":{"URL":"https:\/\/direct.mit.edu\/evco\/article\/33\/2\/141\/124684\/Tail-Bounds-on-the-Runtime-of-Categorical-Compact"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025]]},"references-count":30,"journal-issue":{"issue":"2","published-online":{"date-parts":[[2025,6,2]]},"published-print":{"date-parts":[[2025,6,2]]}},"URL":"https:\/\/doi.org\/10.1162\/evco_a_00361","relation":{},"ISSN":["1063-6560","1530-9304"],"issn-type":[{"value":"1063-6560","type":"print"},{"value":"1530-9304","type":"electronic"}],"subject":[],"published-other":{"date-parts":[[2025]]},"published":{"date-parts":[[2025]]}}}