{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,18]],"date-time":"2026-03-18T01:51:25Z","timestamp":1773798685749,"version":"3.50.1"},"publisher-location":"Cham","reference-count":37,"publisher":"Springer Nature Switzerland","isbn-type":[{"value":"9783031700705","type":"print"},{"value":"9783031700712","type":"electronic"}],"license":[{"start":{"date-parts":[[2024,1,1]],"date-time":"2024-01-01T00:00:00Z","timestamp":1704067200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2024,1,1]],"date-time":"2024-01-01T00:00:00Z","timestamp":1704067200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2024]]},"DOI":"10.1007\/978-3-031-70071-2_4","type":"book-chapter","created":{"date-parts":[[2024,9,6]],"date-time":"2024-09-06T23:02:54Z","timestamp":1725663774000},"page":"53-69","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":5,"title":["Runtime Analysis of\u00a0a\u00a0Multi-valued Compact Genetic Algorithm on\u00a0Generalized OneMax"],"prefix":"10.1007","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-1814-7612","authenticated-orcid":false,"given":"Sumit","family":"Adak","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-6105-7700","authenticated-orcid":false,"given":"Carsten","family":"Witt","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2024,9,7]]},"reference":[{"key":"4_CR1","unstructured":"Adak, S., Witt, C.: Runtime analysis of a multi-valued compact genetic algorithm on generalized OneMax (2024). https:\/\/arxiv.org\/abs\/2404.11239"},{"key":"4_CR2","doi-asserted-by":"publisher","first-page":"88","DOI":"10.1007\/3-540-58484-6_253","volume-title":"Parallel Problem Solving from Nature \u2014 PPSN III","author":"H Asoh","year":"1994","unstructured":"Asoh, H., M\u00fchlenbein, H.: On the mean convergence time of evolutionary algorithms without selection and mutation. In: Davidor, Y., Schwefel, H.-P., M\u00e4nner, R. (eds.) Parallel Problem Solving from Nature \u2014 PPSN III, pp. 88\u201397. Springer, Berlin, Heidelberg (1994). https:\/\/doi.org\/10.1007\/3-540-58484-6_253"},{"key":"4_CR3","unstructured":"Baluja, S.: Population-based incremental learning: a method for integrating genetic search based function optimization and competitive learning. Carnegie Mellon University Pittsburgh, PA, School of Computer Science (1994)"},{"key":"4_CR4","doi-asserted-by":"crossref","unstructured":"Ben\u00a0Jedidia, F., Doerr, B., Krejca, M.S.: Estimation-of-distribution algorithms for multi-valued decision variables. In: Proceedings of the Genetic and Evolutionary Computation Conference, pp. 230\u2013238 (2023)","DOI":"10.1145\/3583131.3590523"},{"key":"4_CR5","doi-asserted-by":"crossref","unstructured":"Benbaki, R., Benomar, Z., Doerr, B.: A rigorous runtime analysis of the 2-MMASIB on jump functions: ant colony optimizers can cope well with local optima. In: Proceedings of the Genetic and Evolutionary Computation Conference, pp. 4\u201313 (2021)","DOI":"10.1145\/3449639.3459350"},{"key":"4_CR6","doi-asserted-by":"crossref","unstructured":"Dang, D.C., Lehre, P.K.: Simplified runtime analysis of estimation of distribution algorithms. In: Proceedings of the 2015 Annual Conference on Genetic and Evolutionary Computation, pp. 513\u2013518 (2015)","DOI":"10.1145\/2739480.2754814"},{"key":"4_CR7","unstructured":"De\u00a0Bonet, J., Isbell, C., Viola, P.: MIMIC: finding optima by estimating probability densities. In: Advances in Neural Information Processing Systems 9 (1996)"},{"key":"4_CR8","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"},{"issue":"10","key":"4_CR9","doi-asserted-by":"publisher","first-page":"3017","DOI":"10.1007\/s00453-020-00775-7","volume":"83","author":"B Doerr","year":"2021","unstructured":"Doerr, B., K\u00f6tzing, T.: Multiplicative up-drift. Algorithmica 83(10), 3017\u20133058 (2021)","journal-title":"Algorithmica"},{"key":"4_CR10","doi-asserted-by":"crossref","unstructured":"Doerr, B., Krejca, M.S.: The univariate marginal distribution algorithm copes well with deception and epistasis. In: Proceedings of the 2020 Genetic and Evolutionary Computation Conference, pp. 17\u201318 (2020)","DOI":"10.1145\/3377929.3397487"},{"issue":"6","key":"4_CR11","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."},{"key":"4_CR12","doi-asserted-by":"crossref","unstructured":"Droste, S.: Not all linear functions are equally difficult for the compact genetic algorithm. In: Proceedings of the 7th Annual Conference on Genetic and Evolutionary Computation, pp. 679\u2013686 (2005)","DOI":"10.1145\/1068009.1068124"},{"key":"4_CR13","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, 257\u2013283 (2006)","journal-title":"Nat. Comput."},{"issue":"1","key":"4_CR14","doi-asserted-by":"publisher","first-page":"51","DOI":"10.1016\/S0304-3975(01)00182-7","volume":"276","author":"S Droste","year":"2002","unstructured":"Droste, S., Jansen, T., Wegener, I.: On the analysis of the (1+1) evolutionary algorithm. Theoret. Comput. Sci. 276(1), 51\u201381 (2002)","journal-title":"Theoret. Comput. Sci."},{"key":"4_CR15","doi-asserted-by":"crossref","unstructured":"Friedrich, T., K\u00f6tzing, T., Krejca, M.S.: EDAs cannot be balanced and stable. In: Proceedings of the Genetic and Evolutionary Computation Conference, pp. 1139\u20131146 (2016)","DOI":"10.1145\/2908812.2908895"},{"issue":"4","key":"4_CR16","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. Evol. Comput. 3(4), 287\u2013297 (1999)","journal-title":"IEEE Trans. Evol. Comput."},{"key":"4_CR17","doi-asserted-by":"publisher","unstructured":"Harik, G.R., Lobo, F.G., Sastry, K.: Linkage learning via probabilistic modeling in the extended compact genetic algorithm (eCGA). In: Scalable Optimization via Probabilistic Modeling, pp. 39\u201361. Springer (2006). https:\/\/doi.org\/10.1007\/978-3-540-34954-9_3","DOI":"10.1007\/978-3-540-34954-9_3"},{"key":"4_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, pp. 967\u2013974 (2018)","DOI":"10.1145\/3205455.3205608"},{"issue":"2","key":"4_CR19","doi-asserted-by":"publisher","first-page":"177","DOI":"10.2307\/3211856","volume":"1","author":"M Kimura","year":"1964","unstructured":"Kimura, M.: Diffusion models in population genetics. J. Appl. Probab. 1(2), 177\u2013232 (1964)","journal-title":"J. Appl. Probab."},{"key":"4_CR20","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: Proceedings of the 14th ACM\/SIGEVO Conference on Foundations of Genetic Algorithms, pp. 65\u201379 (2017)","DOI":"10.1145\/3040718.3040724"},{"key":"4_CR21","doi-asserted-by":"publisher","first-page":"405","DOI":"10.1007\/978-3-030-29414-4_9","volume-title":"Theory of Evolutionary Computation: Recent Developments in Discrete Optimization","author":"MS Krejca","year":"2020","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. 405\u2013442. Springer International Publishing, Cham (2020). https:\/\/doi.org\/10.1007\/978-3-030-29414-4_9"},{"key":"4_CR22","doi-asserted-by":"publisher","unstructured":"Larra\u00f1aga, P., Lozano, J.A. (eds.): Estimation of Distribution Algorithms: A New Tool for Evolutionary Computation, vol.\u00a02. Springer Science & Business Media (2001). https:\/\/doi.org\/10.1007\/978-1-4615-1539-5","DOI":"10.1007\/978-1-4615-1539-5"},{"key":"4_CR23","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, pp. 1499\u20131506 (2018)","DOI":"10.1145\/3205455.3205576"},{"key":"4_CR24","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, 1096\u20131137 (2021)","journal-title":"Algorithmica"},{"key":"4_CR25","doi-asserted-by":"publisher","first-page":"195","DOI":"10.1007\/978-3-662-12788-9_6","volume-title":"Probabilistic Methods for Algorithmic Discrete Mathematics","author":"C McDiarmid","year":"1998","unstructured":"McDiarmid, C.: Concentration. In: Habib, M., McDiarmid, C., Ramirez-Alfonsin, J., Reed, B. (eds.) Probabilistic Methods for Algorithmic Discrete Mathematics, pp. 195\u2013248. Springer, Berlin, Heidelberg (1998). https:\/\/doi.org\/10.1007\/978-3-662-12788-9_6"},{"key":"4_CR26","doi-asserted-by":"publisher","first-page":"178","DOI":"10.1007\/3-540-61723-X_982","volume-title":"Parallel Problem Solving from Nature \u2014 PPSN IV","author":"H M\u00fchlenbein","year":"1996","unstructured":"M\u00fchlenbein, H., Paa\u00df, G.: From recombination of genes to the estimation of distributions I. Binary parameters. In: Voigt, H.-M., Ebeling, W., Rechenberg, I., Schwefel, H.-P. (eds.) Parallel Problem Solving from Nature \u2014 PPSN IV, pp. 178\u2013187. Springer, Berlin, Heidelberg (1996). https:\/\/doi.org\/10.1007\/3-540-61723-X_982"},{"key":"4_CR27","doi-asserted-by":"crossref","unstructured":"Neumann, F., Sudholt, D., Witt, C.: A few ants are enough: ACO with iteration-best update. In: Proceedings of the 12th Annual Conference on Genetic and Evolutionary Computation, pp. 63\u201370 (2010)","DOI":"10.1145\/1830483.1830493"},{"key":"4_CR28","doi-asserted-by":"publisher","first-page":"899","DOI":"10.1007\/978-3-662-43505-2_45","volume-title":"Springer Handbook of Computational Intelligence","author":"M Pelikan","year":"2015","unstructured":"Pelikan, M., Hauschild, M.W., Lobo, F.G.: Estimation of Distribution Algorithms. In: Kacprzyk, J., Pedrycz, W. (eds.) Springer Handbook of Computational Intelligence, pp. 899\u2013928. Springer, Berlin, Heidelberg (2015). https:\/\/doi.org\/10.1007\/978-3-662-43505-2_45"},{"key":"4_CR29","doi-asserted-by":"publisher","first-page":"521","DOI":"10.1007\/978-1-4471-0819-1_39","volume-title":"Advances in Soft Computing","author":"M Pelikan","year":"1999","unstructured":"Pelikan, M., Muehlenbein, H.: The bivariate marginal distribution algorithm. In: Roy, R., Furuhashi, T., Chawdhry, P.K. (eds.) Advances in Soft Computing, pp. 521\u2013535. Springer, London (1999). https:\/\/doi.org\/10.1007\/978-1-4471-0819-1_39"},{"issue":"4","key":"4_CR30","doi-asserted-by":"publisher","first-page":"418","DOI":"10.1109\/TEVC.2007.906095","volume":"12","author":"R Santana","year":"2008","unstructured":"Santana, R., Larranaga, P., Lozano, J.A.: Protein folding in simplified models with estimation of distribution algorithms. IEEE Trans. Evol. Comput. 12(4), 418\u2013438 (2008). https:\/\/doi.org\/10.1109\/TEVC.2007.906095","journal-title":"IEEE Trans. Evol. Comput."},{"key":"4_CR31","unstructured":"Shapiro, J.L.: The sensitivity of PBIL to its learning rate, and how detailed balance can remove it. In: FOGA, pp. 115\u2013132 (2002)"},{"issue":"1","key":"4_CR32","doi-asserted-by":"publisher","first-page":"99","DOI":"10.1162\/1063656053583414","volume":"13","author":"JL Shapiro","year":"2005","unstructured":"Shapiro, J.L.: Drift and scaling in estimation of distribution algorithms. Evol. Comput. 13(1), 99\u2013123 (2005)","journal-title":"Evol. Comput."},{"key":"4_CR33","doi-asserted-by":"publisher","first-page":"92","DOI":"10.1007\/11844297_10","volume-title":"Parallel Problem Solving from Nature - PPSN IX: 9th International Conference, Reykjavik, Iceland, September 9-13, 2006, Proceedings","author":"JL Shapiro","year":"2006","unstructured":"Shapiro, J.L.: Diversity loss in general estimation of distribution algorithms. In: Runarsson, T.P., Beyer, H.-G., Burke, E., Merelo-Guerv\u00f3s, J.J., Whitley, L.D., Yao, X. (eds.) Parallel Problem Solving from Nature - PPSN IX: 9th International Conference, Reykjavik, Iceland, September 9-13, 2006, Proceedings, pp. 92\u2013101. Springer, Berlin, Heidelberg (2006). https:\/\/doi.org\/10.1007\/11844297_10"},{"key":"4_CR34","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, 1450\u20131489 (2019)","journal-title":"Algorithmica"},{"key":"4_CR35","doi-asserted-by":"crossref","unstructured":"Witt, C.: Domino convergence: why one should hill-climb on linear functions. In: Proceedings of the Genetic and Evolutionary Computation Conference, pp. 1539\u20131546 (2018)","DOI":"10.1145\/3205455.3205581"},{"key":"4_CR36","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"},{"key":"4_CR37","doi-asserted-by":"publisher","first-page":"18","DOI":"10.1016\/j.tcs.2022.08.014","volume":"940","author":"C Witt","year":"2023","unstructured":"Witt, C.: How majority-vote crossover and estimation-of-distribution algorithms cope with fitness valleys. Theoret. Comput. Sci. 940, 18\u201342 (2023)","journal-title":"Theoret. Comput. Sci."}],"container-title":["Lecture Notes in Computer Science","Parallel Problem Solving from Nature \u2013 PPSN XVIII"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-031-70071-2_4","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,11,27]],"date-time":"2024-11-27T21:39:36Z","timestamp":1732743576000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-031-70071-2_4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024]]},"ISBN":["9783031700705","9783031700712"],"references-count":37,"URL":"https:\/\/doi.org\/10.1007\/978-3-031-70071-2_4","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024]]},"assertion":[{"value":"7 September 2024","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"PPSN","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Conference on Parallel Problem Solving from Nature","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Hagenberg","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Austria","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2024","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"14 September 2024","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"18 September 2024","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"18","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"ppsn2024","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/ppsn2024.fh-ooe.at\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}