{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,29]],"date-time":"2025-09-29T20:32:31Z","timestamp":1759177951611,"version":"3.40.2"},"reference-count":32,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2024,11,17]],"date-time":"2024-11-17T00:00:00Z","timestamp":1731801600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2024,11,17]],"date-time":"2024-11-17T00:00:00Z","timestamp":1731801600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100000923","name":"Australian Research Council","doi-asserted-by":"crossref","award":["FT200100536"],"award-info":[{"award-number":["FT200100536"]}],"id":[{"id":"10.13039\/501100000923","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/501100004836","name":"Danmarks Frie Forskningsfond","doi-asserted-by":"publisher","award":["8021-00260B"],"award-info":[{"award-number":["8021-00260B"]}],"id":[{"id":"10.13039\/501100004836","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100005192","name":"Technical University of Denmark","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100005192","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2025,4]]},"abstract":"<jats:title>Abstract<\/jats:title>\n          <jats:p>Estimation of distribution algorithms (EDAs) are general-purpose optimizers that maintain a probability distribution over a given search space. This probability distribution is updated through sampling from the distribution and a reinforcement learning process which rewards solution components that have shown to be part of good quality samples. The compact genetic algorithm (cGA) is a non-elitist EDA able to deal with difficult multimodal fitness landscapes that are hard to solve by elitist algorithms. We investigate the cGA on the <jats:sc>Cliff<\/jats:sc> function for which it was shown recently that non-elitist evolutionary algorithms and artificial immune systems optimize it in expected polynomial time. We point out that the cGA faces major difficulties when solving the <jats:sc>Cliff<\/jats:sc> function and investigate its dynamics both experimentally and theoretically. Our experimental results indicate that the cGA requires exponential time for all values of the update strength\u00a01\/<jats:italic>K<\/jats:italic>. We show theoretically that, under sensible assumptions, there is a negative drift when sampling around the location of the cliff. Experiments further suggest that there is a phase transition for\u00a0<jats:italic>K<\/jats:italic> where the expected optimization time drops from <jats:inline-formula>\n              <jats:alternatives>\n                <jats:tex-math>$$n^{\\Theta (n)}$$<\/jats:tex-math>\n                <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:msup>\n                    <mml:mi>n<\/mml:mi>\n                    <mml:mrow>\n                      <mml:mi>\u0398<\/mml:mi>\n                      <mml:mo>(<\/mml:mo>\n                      <mml:mi>n<\/mml:mi>\n                      <mml:mo>)<\/mml:mo>\n                    <\/mml:mrow>\n                  <\/mml:msup>\n                <\/mml:math>\n              <\/jats:alternatives>\n            <\/jats:inline-formula> to <jats:inline-formula>\n              <jats:alternatives>\n                <jats:tex-math>$$2^{\\Theta (n)}$$<\/jats:tex-math>\n                <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:msup>\n                    <mml:mn>2<\/mml:mn>\n                    <mml:mrow>\n                      <mml:mi>\u0398<\/mml:mi>\n                      <mml:mo>(<\/mml:mo>\n                      <mml:mi>n<\/mml:mi>\n                      <mml:mo>)<\/mml:mo>\n                    <\/mml:mrow>\n                  <\/mml:msup>\n                <\/mml:math>\n              <\/jats:alternatives>\n            <\/jats:inline-formula>.<\/jats:p>","DOI":"10.1007\/s00453-024-01281-w","type":"journal-article","created":{"date-parts":[[2024,11,17]],"date-time":"2024-11-17T10:34:43Z","timestamp":1731839683000},"page":"507-536","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["The Compact Genetic Algorithm Struggles on Cliff Functions"],"prefix":"10.1007","volume":"87","author":[{"given":"Frank","family":"Neumann","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Dirk","family":"Sudholt","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Carsten","family":"Witt","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2024,11,17]]},"reference":[{"key":"1281_CR1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-17339-4","volume-title":"Analyzing Evolutionary Algorithms: The Computer Science Perspective","author":"T Jansen","year":"2013","unstructured":"Jansen, T.: Analyzing Evolutionary Algorithms: The Computer Science Perspective. Springer, Berlin, Heidelberg (2013)"},{"volume-title":"Theory of Evolutionary Computation: Recent Developments in Discrete Optimization","year":"2020","key":"1281_CR2","unstructured":"Doerr, B., Neumann, F. (eds.): Theory of Evolutionary Computation: Recent Developments in Discrete Optimization. Springer, Berlin, Heidelberg (2020)"},{"key":"1281_CR3","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-16544-3","volume-title":"Bioinspired Computation in Combinatorial Optimization: Algorithms and Their Computational Complexity","author":"F Neumann","year":"2010","unstructured":"Neumann, F., Witt, C.: Bioinspired Computation in Combinatorial Optimization: Algorithms and Their Computational Complexity. Springer, Berlin, Heidelberg (2010)"},{"key":"1281_CR4","first-page":"899","volume-title":"Handbook of Computational Intelligence","author":"M Pelikan","year":"2015","unstructured":"Pelikan, M., Hauschild, M., Lobo, F.G.: Estimation of distribution algorithms. In: Kacprzyk, J., Pedrycz, W. (eds.) Handbook of Computational Intelligence, pp. 899\u2013928. Springer, Berlin, Heidelberg (2015)"},{"issue":"3","key":"1281_CR5","doi-asserted-by":"publisher","first-page":"111","DOI":"10.1016\/j.swevo.2011.08.003","volume":"1","author":"M Hauschild","year":"2011","unstructured":"Hauschild, M., Pelikan, M.: An introduction and survey of estimation of distribution algorithms. Swarm Evolut. Comput. 1(3), 111\u2013128 (2011)","journal-title":"Swarm Evolut. Comput."},{"key":"1281_CR6","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, Heidelberg (2019)"},{"issue":"3","key":"1281_CR7","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":"1281_CR8","doi-asserted-by":"crossref","unstructured":"Dang, D., Lehre, P.K.: Simplified runtime analysis of estimation of distribution algorithms. In: Proceedings of the Genetic and Evolutionary Computation Conference (GECCO\u00a0\u201915), pp. 513\u2013518 (2015)","DOI":"10.1145\/2739480.2754814"},{"key":"1281_CR9","doi-asserted-by":"crossref","unstructured":"Witt, C.: Upper bounds on the runtime of the Univariate Marginal Distribution Algorithm on OneMax. In: Proceedings of the Genetic and Evolutionary Computation Conference (GECCO\u00a0\u201917), pp. 1415\u20131422. ACM Press, New York (2017)","DOI":"10.1145\/3071178.3071216"},{"key":"1281_CR10","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: Proceedings of the Genetic and Evolutionary Computation Conference (GECCO\u00a0\u201917), pp. 1383\u20131390. ACM Press, New York (2017)","DOI":"10.1145\/3071178.3071317"},{"issue":"4","key":"1281_CR11","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"},{"issue":"6","key":"1281_CR12","doi-asserted-by":"publisher","first-page":"1140","DOI":"10.1109\/TEVC.2020.2987361","volume":"24","author":"B Doerr","year":"2020","unstructured":"Doerr, B., Zheng, W.: Sharp bounds for genetic drift in estimation of distribution algorithms. IEEE Trans. Evol. Comput. 24(6), 1140\u20131149 (2020)","journal-title":"IEEE Trans. Evol. Comput."},{"issue":"4","key":"1281_CR13","doi-asserted-by":"publisher","first-page":"1096","DOI":"10.1007\/s00453-020-00778-4","volume":"83","author":"J Lengler","year":"2021","unstructured":"Lengler, J., Sudholt, D., Witt, C.: The complex parameter landscape of the compact genetic algorithm. Algorithmica 83(4), 1096\u20131137 (2021)","journal-title":"Algorithmica"},{"key":"1281_CR14","doi-asserted-by":"crossref","unstructured":"Lengler, J., Sudholt, D., Witt, C.: Medium step sizes are harmful for the compact genetic algorithm. In: Proceedings of the Genetic and Evolutionary Computation Conference (GECCO\u00a0\u201918), pp. 1499\u20131506. ACM Press, New York (2018)","DOI":"10.1145\/3205455.3205576"},{"issue":"3","key":"1281_CR15","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. Evol. Comput. 21(3), 477\u2013490 (2017)","journal-title":"IEEE Trans. Evol. Comput."},{"key":"1281_CR16","doi-asserted-by":"publisher","first-page":"3059","DOI":"10.1007\/s00453-020-00780-w","volume":"83","author":"B Doerr","year":"2021","unstructured":"Doerr, B.: The runtime of the compact genetic algorithm on jump functions. Algorithmica 83, 3059\u20133107 (2021)","journal-title":"Algorithmica"},{"key":"1281_CR17","doi-asserted-by":"crossref","unstructured":"Witt, C.: How majority-vote crossover and estimation-of-distribution algorithms cope with fitness valleys. Theoretical Computer Science (2022). In press, https:\/\/doi.org\/10.1016\/j.tcs.2022.08.014; preliminary version in FOGA\u00a02021","DOI":"10.1016\/j.tcs.2022.08.014"},{"key":"1281_CR18","doi-asserted-by":"crossref","unstructured":"Hasen\u00f6hrl, V., Sutton, A.M.: On the runtime dynamics of the compact genetic algorithm on jump functions. In: Proceedings of the Genetic and Evolutionary Computation Conference, (GECCO 2018), pp. 967\u2013974. ACM, New York (2018)","DOI":"10.1145\/3205455.3205608"},{"key":"1281_CR19","doi-asserted-by":"crossref","unstructured":"J\u00e4gersk\u00fcpper, J., Storch, T.: When the plus strategy outperforms the comma strategy\u2014and when not. In: Proceedings of the IEEE Symposium on Foundations of Computational Intelligence (FOCI 2007), pp. 25\u201332 (2007)","DOI":"10.1109\/FOCI.2007.372143"},{"key":"1281_CR20","doi-asserted-by":"crossref","unstructured":"Hevia\u00a0Fajardo, M.A., Sudholt, D.: Self-adjusting offspring population sizes outperform fixed parameters on the cliff function. In: Proceedings of the 16th ACM\/SIGEVO Conference on Foundations of Genetic Algorithms (FOGA 2021), pp. 1\u201315. ACM Press, New York (2021)","DOI":"10.1145\/3450218.3477306"},{"key":"1281_CR21","doi-asserted-by":"crossref","unstructured":"Lissovoi, A., Oliveto, P.S., Warwicker, J.A.: On the time complexity of algorithm selection hyper-heuristics for multimodal optimisation. In: Proceedings of the AAAI Conference on Artificial Intelligence (AAAI 2019), vol. 33, pp. 2322\u20132329 (2019)","DOI":"10.1609\/aaai.v33i01.33012322"},{"key":"1281_CR22","doi-asserted-by":"publisher","first-page":"166","DOI":"10.1016\/j.tcs.2019.03.002","volume":"832","author":"D Corus","year":"2020","unstructured":"Corus, D., Oliveto, P.S., Yazdani, D.: When hypermutations and ageing enable artificial immune systems to outperform evolutionary algorithms. Theoret. Comput. Sci. 832, 166\u2013185 (2020)","journal-title":"Theoret. Comput. Sci."},{"key":"1281_CR23","doi-asserted-by":"crossref","unstructured":"Doerr, B., Zheng, W.: From understanding genetic drift to a smart-restart parameter-less compact genetic algorithm. In: Proceedings of the 2020 Genetic and Evolutionary Computation Conference. GECCO \u201920, pp. 805\u2013813. ACM Press, New York (2020)","DOI":"10.1145\/3377930.3390163"},{"key":"1281_CR24","doi-asserted-by":"crossref","unstructured":"Neumann, F., Sudholt, D., Witt, C.: The compact genetic algorithm struggles on cliff functions. In: Proceedings of the Genetic and Evolutionary Computation Conference (GECCO\u00a0\u201922), pp. 1426\u20131433. ACM, New York (2022)","DOI":"10.1145\/3512290.3528776"},{"key":"1281_CR25","doi-asserted-by":"publisher","first-page":"21","DOI":"10.1016\/j.tcs.2015.01.002","volume":"605","author":"PS Oliveto","year":"2015","unstructured":"Oliveto, P.S., Witt, C.: Improved time complexity analysis of the simple genetic algorithm. Theoret. Comput. Sci. 605, 21\u201341 (2015)","journal-title":"Theoret. Comput. Sci."},{"issue":"3","key":"1281_CR26","doi-asserted-by":"publisher","first-page":"713","DOI":"10.1214\/aoms\/1177728178","volume":"27","author":"W Hoeffding","year":"1956","unstructured":"Hoeffding, W.: On the distribution of the number of successes in independent trials. Ann. Math. Stat. 27(3), 713\u2013721 (1956)","journal-title":"Ann. Math. Stat."},{"key":"1281_CR27","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/978-3-030-29414-4","volume-title":"Theory of Evolutionary Computation: Recent Developments in Discrete Optimization","author":"B Doerr","year":"2020","unstructured":"Doerr, B.: Probabilistic tools for the analysis of randomized optimization heuristics. In: Doerr, B., Neumann, F. (eds.) Theory of Evolutionary Computation: Recent Developments in Discrete Optimization, pp. 1\u201387. Springer, Berlin, Heidelberg (2020)"},{"key":"1281_CR28","volume-title":"An Introduction to Probability Theory and Its Applications","author":"W Feller","year":"1971","unstructured":"Feller, W.: An Introduction to Probability Theory and Its Applications, vol. 2. Wiley, Hoboken, New Jersey (1971)"},{"key":"1281_CR29","unstructured":"Johnson, N.L., Kotz, S., Balakrishnan, N.: Continuous Univariate Distributions vol. 1, 2nd edn. Wiley, Hoboken, New Jersey (1994)"},{"issue":"1","key":"1281_CR30","doi-asserted-by":"publisher","first-page":"130","DOI":"10.1214\/aoms\/1177729093","volume":"24","author":"MR Sampford","year":"1953","unstructured":"Sampford, M.R.: Some inequalities on Mill\u2019s ratio and related functions. Ann. Math. Stat. 24(1), 130\u2013132 (1953)","journal-title":"Ann. Math. Stat."},{"key":"1281_CR31","unstructured":"Bambury, H., Bultel, A., Doerr, B.: An extended jump function benchmark for the analysis of randomized search heuristics. In: Proceedings of GECCO\u00a0\u201921, pp. 1124\u20131132. ACM Press, New York (2021)"},{"key":"1281_CR32","doi-asserted-by":"crossref","unstructured":"Rajabi, A., Witt, C.: Stagnation detection in highly multimodal fitness landscapes. In: Proceedings of GECCO\u00a0\u201921, pp. 1178\u20131186. ACM Press, New York (2021)","DOI":"10.1145\/3449639.3459336"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-024-01281-w.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00453-024-01281-w\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-024-01281-w.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,3,23]],"date-time":"2025-03-23T11:35:10Z","timestamp":1742729710000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00453-024-01281-w"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,11,17]]},"references-count":32,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2025,4]]}},"alternative-id":["1281"],"URL":"https:\/\/doi.org\/10.1007\/s00453-024-01281-w","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"type":"print","value":"0178-4617"},{"type":"electronic","value":"1432-0541"}],"subject":[],"published":{"date-parts":[[2024,11,17]]},"assertion":[{"value":"31 October 2022","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"28 October 2024","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"17 November 2024","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors declare not to have any Conflict of interest.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}]}}