{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,18]],"date-time":"2026-03-18T01:50:28Z","timestamp":1773798628629,"version":"3.50.1"},"reference-count":24,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2020,11,4]],"date-time":"2020-11-04T00:00:00Z","timestamp":1604448000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2020,11,4]],"date-time":"2020-11-04T00:00:00Z","timestamp":1604448000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"name":"Swiss Federal Institute of Technology Zurich"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2021,4]]},"abstract":"Abstract<\/jats:title>The compact Genetic Algorithm (cGA) evolves a probability distribution favoring optimal solutions in the underlying search space by repeatedly sampling from the distribution and updating it according to promising samples. We study the intricate dynamics of the cGA on the test functionOneMax<\/jats:sc>, and how its performance depends on the hypothetical population sizeK<\/jats:italic>, which determines how quickly decisions about promising bit values are fixated in the probabilistic model. It is known that the cGA and the Univariate Marginal Distribution Algorithm (UMDA), a related algorithm whose population size is called\u00a0$$\\lambda$$<\/jats:tex-math>\u03bb<\/mml:mi><\/mml:math><\/jats:alternatives><\/jats:inline-formula>, run in expected time$$O(n \\log n)$$<\/jats:tex-math>O<\/mml:mi>(<\/mml:mo>n<\/mml:mi>log<\/mml:mo>n<\/mml:mi>)<\/mml:mo><\/mml:mrow><\/mml:math><\/jats:alternatives><\/jats:inline-formula>when the population size is just large enough ($$K = \\varTheta (\\sqrt{n}\\log n)$$<\/jats:tex-math>K<\/mml:mi>=<\/mml:mo>\u0398<\/mml:mi>(<\/mml:mo>n<\/mml:mi><\/mml:msqrt>log<\/mml:mo>n<\/mml:mi>)<\/mml:mo><\/mml:mrow><\/mml:math><\/jats:alternatives><\/jats:inline-formula>and$$\\lambda = \\varTheta (\\sqrt{n}\\log n)$$<\/jats:tex-math>\u03bb<\/mml:mi>=<\/mml:mo>\u0398<\/mml:mi>(<\/mml:mo>n<\/mml:mi><\/mml:msqrt>log<\/mml:mo>n<\/mml:mi>)<\/mml:mo><\/mml:mrow><\/mml:math><\/jats:alternatives><\/jats:inline-formula>, respectively) to avoid wrong decisions being fixated. The UMDA also shows the same performance in a very different regime ($$\\lambda =\\varTheta (\\log n)$$<\/jats:tex-math>\u03bb<\/mml:mi>=<\/mml:mo>\u0398<\/mml:mi>(<\/mml:mo>log<\/mml:mo>n<\/mml:mi>)<\/mml:mo><\/mml:mrow><\/mml:math><\/jats:alternatives><\/jats:inline-formula>, equivalent to$$K = \\varTheta (\\log n)$$<\/jats:tex-math>K<\/mml:mi>=<\/mml:mo>\u0398<\/mml:mi>(<\/mml:mo>log<\/mml:mo>n<\/mml:mi>)<\/mml:mo><\/mml:mrow><\/mml:math><\/jats:alternatives><\/jats:inline-formula>in the cGA) with much smaller population size, but for very different reasons: many wrong decisions are fixated initially, but then reverted efficiently. If the population size is even smaller ($$o(\\log n)$$<\/jats:tex-math>o<\/mml:mi>(<\/mml:mo>log<\/mml:mo>n<\/mml:mi>)<\/mml:mo><\/mml:mrow><\/mml:math><\/jats:alternatives><\/jats:inline-formula>), the time is exponential. We show that population sizes in between the two optimal regimes are worse as they yield larger runtimes: we prove a lower bound of$$\\varOmega (K^{1\/3}n + n \\log n)$$<\/jats:tex-math>\u03a9<\/mml:mi>(<\/mml:mo>K<\/mml:mi>1<\/mml:mn>\/<\/mml:mo>3<\/mml:mn><\/mml:mrow><\/mml:msup>n<\/mml:mi>+<\/mml:mo>n<\/mml:mi>log<\/mml:mo>n<\/mml:mi>)<\/mml:mo><\/mml:mrow><\/mml:math><\/jats:alternatives><\/jats:inline-formula>for the cGA onOneMax<\/jats:sc>for$$K = O(\\sqrt{n}\/\\log ^2 n)$$<\/jats:tex-math>K<\/mml:mi>=<\/mml:mo>O<\/mml:mi>(<\/mml:mo>n<\/mml:mi><\/mml:msqrt>\/<\/mml:mo>log<\/mml:mo>2<\/mml:mn><\/mml:msup>n<\/mml:mi>)<\/mml:mo><\/mml:mrow><\/mml:math><\/jats:alternatives><\/jats:inline-formula>. For$$K = \\varOmega (\\log ^3 n)$$<\/jats:tex-math>K<\/mml:mi>=<\/mml:mo>\u03a9<\/mml:mi>(<\/mml:mo>log<\/mml:mo>3<\/mml:mn><\/mml:msup>n<\/mml:mi>)<\/mml:mo><\/mml:mrow><\/mml:math><\/jats:alternatives><\/jats:inline-formula>the runtime increases with growing\u00a0K<\/jats:italic>before dropping again to$$O(K\\sqrt{n} + n \\log n)$$<\/jats:tex-math>O<\/mml:mi>(<\/mml:mo>K<\/mml:mi>n<\/mml:mi><\/mml:msqrt>+<\/mml:mo>n<\/mml:mi>log<\/mml:mo>n<\/mml:mi>)<\/mml:mo><\/mml:mrow><\/mml:math><\/jats:alternatives><\/jats:inline-formula>for$$K = \\varOmega (\\sqrt{n} \\log n)$$<\/jats:tex-math>K<\/mml:mi>=<\/mml:mo>\u03a9<\/mml:mi>(<\/mml:mo>n<\/mml:mi><\/mml:msqrt>log<\/mml:mo>n<\/mml:mi>)<\/mml:mo><\/mml:mrow><\/mml:math><\/jats:alternatives><\/jats:inline-formula>. This suggests that the expected runtime for the cGA is a bimodal function in\u00a0K<\/jats:italic>with two very different optimal regions and worse performance in between.<\/jats:p>","DOI":"10.1007\/s00453-020-00778-4","type":"journal-article","created":{"date-parts":[[2020,11,4]],"date-time":"2020-11-04T05:02:41Z","timestamp":1604466161000},"page":"1096-1137","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":32,"title":["The Complex Parameter Landscape of the Compact\u00a0Genetic\u00a0Algorithm"],"prefix":"10.1007","volume":"83","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-0004-7629","authenticated-orcid":false,"given":"Johannes","family":"Lengler","sequence":"first","affiliation":[]},{"given":"Dirk","family":"Sudholt","sequence":"additional","affiliation":[]},{"given":"Carsten","family":"Witt","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2020,11,4]]},"reference":[{"key":"778_CR1","doi-asserted-by":"publisher","first-page":"352","DOI":"10.1017\/S0963548315000127","volume":"25","author":"J-B Baillon","year":"2016","unstructured":"Baillon, J.-B., Cominetti, R., Vaisman, J.: A sharp uniform bound for the distribution of sums of bernoulli trials. Combinat. Probab. Comput. 25, 352\u2013361 (2016)","journal-title":"Combinat. Probab. Comput."},{"key":"778_CR2","doi-asserted-by":"publisher","first-page":"668","DOI":"10.1007\/s00453-018-0507-5","volume":"81","author":"D-C Dang","year":"2019","unstructured":"Dang, D.-C., Lehre, P.K., Nguyen, P.T.H.: Level-based analysis of the univariate marginal distribution algorithm. Algorithmica 81, 668\u2013702 (2019)","journal-title":"Algorithmica"},{"issue":"3","key":"778_CR3","doi-asserted-by":"publisher","first-page":"257","DOI":"10.1007\/s11047-006-9001-0","volume":"5","author":"S Droste","year":"2006","unstructured":"Droste, S.: A rigorous analysis of the compact genetic algorithm for linear functions. Nat. Comput. 5(3), 257\u2013283 (2006)","journal-title":"Nat. Comput."},{"key":"778_CR4","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511581274","volume-title":"Concentration of measure for the analysis of randomized algorithms","author":"DP Dubhashi","year":"2009","unstructured":"Dubhashi, D.P., Panconesi, A.: Concentration of measure for the analysis of randomized algorithms. Cambridge University Press, Cambridge (2009)"},{"key":"778_CR5","volume-title":"An Introduction to Probability Theory and Its Applications","author":"W Feller","year":"1968","unstructured":"Feller, W.: An Introduction to Probability Theory and Its Applications, vol. 1. Wiley, New York (1968)"},{"issue":"3","key":"778_CR6","first-page":"477","volume":"21","author":"T Friedrich","year":"2017","unstructured":"Friedrich, T., K\u00f6tzing, T., Krejca, M.S., Sutton, A.M.: The compact genetic algorithm is efficient under extreme gaussian noise. IEEE Trans. Evolut. Comput. 21(3), 477\u2013490 (2017)","journal-title":"IEEE Trans. Evolut. Comput."},{"key":"778_CR7","doi-asserted-by":"crossref","DOI":"10.1093\/oso\/9780198572237.001.0001","volume-title":"Probab. Random Process.","author":"G Grimmett","year":"2001","unstructured":"Grimmett, G., Stirzaker, D.: Probab. Random Process. Oxford University Press, Oxford (2001)"},{"issue":"3","key":"778_CR8","doi-asserted-by":"publisher","first-page":"231","DOI":"10.1162\/evco.1999.7.3.231","volume":"7","author":"GR Harik","year":"1999","unstructured":"Harik, G.R., Cant\u00fa-Paz, E., Goldberg, D.E., Miller, B.L.: The gambler\u2019s ruin problem, genetic algorithms, and the sizing of populations. Evolut. Comput. 7(3), 231\u2013253 (1999)","journal-title":"Evolut. Comput."},{"issue":"4","key":"778_CR9","doi-asserted-by":"publisher","first-page":"287","DOI":"10.1109\/4235.797971","volume":"3","author":"GR Harik","year":"1999","unstructured":"Harik, G.R., Lobo, F.G., Goldberg, D.E.: The compact genetic algorithm. IEEE Trans. Evolut. Comput. 3(4), 287\u2013297 (1999)","journal-title":"IEEE Trans. Evolut. Comput."},{"issue":"1","key":"778_CR10","doi-asserted-by":"publisher","first-page":"21","DOI":"10.1023\/B:NACO.0000023417.31393.c7","volume":"3","author":"J He","year":"2004","unstructured":"He, J., Yao, X.: A study of drift analysis for estimating computation time of evolutionary algorithms. Nat. Comput. 3(1), 21\u201335 (2004)","journal-title":"Nat. Comput."},{"key":"778_CR11","doi-asserted-by":"publisher","first-page":"490","DOI":"10.1007\/s00453-015-0048-0","volume":"75","author":"T K\u00f6tzing","year":"2016","unstructured":"K\u00f6tzing, T.: Concentration of first hitting times under additive drift. Algorithmica 75, 490\u2013506 (2016)","journal-title":"Algorithmica"},{"key":"778_CR12","doi-asserted-by":"crossref","unstructured":"Krejca, M.S., Witt, C.: Lower bounds on the run time of the univariate marginal distribution algorithm on OneMax. In: Proc. of FOGA \u201917, pp. 65\u201379. ACM Press, (2017)","DOI":"10.1145\/3040718.3040724"},{"key":"778_CR13","first-page":"406","volume-title":"Theory of Evolutionary Computation: Recent Developments in Discrete Optimization","author":"MS Krejca","year":"2019","unstructured":"Krejca, M.S., Witt, C.: Theory of estimation-of-distribution algorithms. In: Doerr, B., Neumann, F. (eds.) Theory of Evolutionary Computation: Recent Developments in Discrete Optimization, pp. 406\u2013442. Springer, Berlin (2019)"},{"key":"778_CR14","doi-asserted-by":"crossref","unstructured":"Lehre, P.K., Nguyen, P.T.H.: Tight bounds on runtime of the univariate marginal distribution algorithm via anti-concentration. In: Proc. of GECCO \u201917, pp. 1383\u20131390. ACM Press, (2017)","DOI":"10.1145\/3071178.3071317"},{"key":"778_CR15","doi-asserted-by":"crossref","unstructured":"Lengler, J., Sudholt, D., Witt, C.: Medium step sizes are harmful for the compact genetic algorithm. In: Proc. of GECCO \u201918, pp. 1499\u20131506. ACM Press, (2018)","DOI":"10.1145\/3205455.3205576"},{"issue":"1","key":"778_CR16","doi-asserted-by":"publisher","first-page":"25","DOI":"10.1162\/evco.1993.1.1.25","volume":"1","author":"H M\u00fchlenbein","year":"1993","unstructured":"M\u00fchlenbein, H., Schlierkamp-Voosen, D.: Predictive models for the breeder genetic algorithm, I: continuous parameter optimization. Evolut. Comput. 1(1), 25\u201349 (1993)","journal-title":"Evolut. Comput."},{"key":"778_CR17","doi-asserted-by":"crossref","unstructured":"Neumann, F., Sudholt, D., Witt, C.: A few ants are enough: ACO with iteration-best update. In: Proc. of GECCO \u201910, pp 63\u201370. ACM Press, (2010)","DOI":"10.1145\/1830483.1830493"},{"issue":"3","key":"778_CR18","doi-asserted-by":"publisher","first-page":"369","DOI":"10.1007\/s00453-010-9387-z","volume":"59","author":"PS Oliveto","year":"2011","unstructured":"Oliveto, P.S., Witt, C.: Simplified drift analysis for proving lower bounds in evolutionary computation. Algorithmica 59(3), 369\u2013386 (2011)","journal-title":"Algorithmica"},{"key":"778_CR19","unstructured":"Oliveto, P.S., Witt, C.: Erratum: Simplified Drift Analysis for Proving Lower Bounds in Evolutionary Computation. ArXiv e-prints, (2012)"},{"key":"778_CR20","doi-asserted-by":"publisher","first-page":"20","DOI":"10.1016\/j.tcs.2013.09.036","volume":"545","author":"JE Rowe","year":"2014","unstructured":"Rowe, J.E., Sudholt, D.: The choice of the offspring population size in the (1,$$\\lambda$$) evolutionary algorithm. Theor. Comp. Sci. 545, 20\u201338 (2014)","journal-title":"Theor. Comp. Sci."},{"key":"778_CR21","doi-asserted-by":"crossref","unstructured":"Sudholt, D., Witt, C.: Update strength in EDAs and ACO: How to avoid genetic drift. In: Proc. of GECCO \u201916, pp. 61\u201368. ACM Press, (2016)","DOI":"10.1145\/2908812.2908867"},{"issue":"4","key":"778_CR22","doi-asserted-by":"publisher","first-page":"1450","DOI":"10.1007\/s00453-018-0480-z","volume":"81","author":"D Sudholt","year":"2019","unstructured":"Sudholt, D., Witt, C.: On the choice of the update strength in estimation-of-distribution algorithms and ant colony optimization. Algorithmica 81(4), 1450\u20131489 (2019)","journal-title":"Algorithmica"},{"key":"778_CR23","doi-asserted-by":"crossref","unstructured":"Witt, C.: Upper bounds on the runtime of the Univariate Marginal Distribution Algorithm on OneMax. In: Proc. of GECCO \u201917, pp. 1415\u20131422. ACM Press, (2017)","DOI":"10.1145\/3071178.3071216"},{"key":"778_CR24","doi-asserted-by":"publisher","first-page":"632","DOI":"10.1007\/s00453-018-0463-0","volume":"81","author":"C Witt","year":"2019","unstructured":"Witt, C.: Upper bounds on the running time of the univariate marginal distribution algorithm on OneMax. Algorithmica 81, 632\u2013667 (2019)","journal-title":"Algorithmica"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-020-00778-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-020-00778-4\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-020-00778-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,8,16]],"date-time":"2024-08-16T21:59:31Z","timestamp":1723845571000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-020-00778-4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,11,4]]},"references-count":24,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2021,4]]}},"alternative-id":["778"],"URL":"https:\/\/doi.org\/10.1007\/s00453-020-00778-4","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,11,4]]},"assertion":[{"value":"14 December 2018","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"16 October 2020","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"4 November 2020","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}