{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,11]],"date-time":"2026-07-11T05:54:37Z","timestamp":1783749277653,"version":"3.55.0"},"reference-count":33,"publisher":"Springer Science and Business Media LLC","issue":"5","license":[{"start":{"date-parts":[[2025,2,19]],"date-time":"2025-02-19T00:00:00Z","timestamp":1739923200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2025,2,19]],"date-time":"2025-02-19T00:00:00Z","timestamp":1739923200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100001659","name":"Deutsche Forschungsgemeinschaft","doi-asserted-by":"publisher","award":["FR 2988\/17-1"],"award-info":[{"award-number":["FR 2988\/17-1"]}],"id":[{"id":"10.13039\/501100001659","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001659","name":"Deutsche Forschungsgemeinschaft","doi-asserted-by":"publisher","award":["FR 2988\/17-1"],"award-info":[{"award-number":["FR 2988\/17-1"]}],"id":[{"id":"10.13039\/501100001659","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001659","name":"Deutsche Forschungsgemeinschaft","doi-asserted-by":"publisher","award":["FR 2988\/17-1"],"award-info":[{"award-number":["FR 2988\/17-1"]}],"id":[{"id":"10.13039\/501100001659","id-type":"DOI","asserted-by":"publisher"}]},{"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\/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"}]},{"name":"Hasso-Plattner-Institut f\u00fcr Digital Engineering gGmbH"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2025,5]]},"abstract":"<jats:title>Abstract<\/jats:title>\n          <jats:p>Understanding how evolutionary algorithms perform on constrained problems has gained increasing attention in recent years. In this paper, we study how evolutionary algorithms optimize constrained versions of the classical LeadingOnes problem. We first provide a run time analysis for the classical (1+1) EA on the LeadingOnes problem with a deterministic cardinality constraint, giving <jats:inline-formula>\n              <jats:alternatives>\n                <jats:tex-math>$$\\Theta (n (n-B)\\log (B) + nB)$$<\/jats:tex-math>\n                <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\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:mi>n<\/mml:mi>\n                    <mml:mo>-<\/mml:mo>\n                    <mml:mi>B<\/mml:mi>\n                    <mml:mo>)<\/mml:mo>\n                    <mml:mo>log<\/mml:mo>\n                    <mml:mo>(<\/mml:mo>\n                    <mml:mi>B<\/mml:mi>\n                    <mml:mo>)<\/mml:mo>\n                    <mml:mo>+<\/mml:mo>\n                    <mml:mi>n<\/mml:mi>\n                    <mml:mi>B<\/mml:mi>\n                    <mml:mo>)<\/mml:mo>\n                  <\/mml:mrow>\n                <\/mml:math>\n              <\/jats:alternatives>\n            <\/jats:inline-formula> as the tight bound. Our results show that the behaviour of the algorithm is highly dependent on the constraint bound of the uniform constraint. Afterwards, we consider the problem in the context of stochastic constraints and provide insights using theoretical and experimental studies on how the (<jats:inline-formula>\n              <jats:alternatives>\n                <jats:tex-math>$$\\mu $$<\/jats:tex-math>\n                <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mi>\u03bc<\/mml:mi>\n                <\/mml:math>\n              <\/jats:alternatives>\n            <\/jats:inline-formula>+1) EA is able to deal with these constraints in a sampling-based setting.<\/jats:p>","DOI":"10.1007\/s00453-025-01298-9","type":"journal-article","created":{"date-parts":[[2025,2,19]],"date-time":"2025-02-19T09:52:06Z","timestamp":1739958726000},"page":"661-689","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Analysis of the (1+1) EA on LeadingOnes with Constraints"],"prefix":"10.1007","volume":"87","author":[{"given":"Tobias","family":"Friedrich","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Timo","family":"K\u00f6tzing","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Aneta","family":"Neumann","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Frank","family":"Neumann","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Aishwarya","family":"Radhakrishnan","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2025,2,19]]},"reference":[{"key":"1298_CR1","doi-asserted-by":"crossref","unstructured":"Eiben, A.E., Smith, J.E.: Introduction to Evolutionary Computing, Natural Computing Series. 2nd edn. Springer (2015)","DOI":"10.1007\/978-3-662-44874-8"},{"key":"1298_CR2","doi-asserted-by":"publisher","unstructured":"Jansen, T.: Analyzing Evolutionary Algorithms: The Computer Science Perspective. Natural Computing Series. Springer (2013). https:\/\/doi.org\/10.1007\/978-3-642-17339-4","DOI":"10.1007\/978-3-642-17339-4"},{"key":"1298_CR3","doi-asserted-by":"publisher","unstructured":"Neumann, F., Witt, C.: Bioinspired Computation in Combinatorial Optimization. Natural Computing Series. Springer (2010). https:\/\/doi.org\/10.1007\/978-3-642-16544-3","DOI":"10.1007\/978-3-642-16544-3"},{"key":"1298_CR4","doi-asserted-by":"publisher","unstructured":"Doerr, B., Neumann, F. (eds.): Theory of Evolutionary Computation - Recent Developments in Discrete Optimization. Natural Computing Series. Springer, (2020). https:\/\/doi.org\/10.1007\/978-3-030-29414-4 . https:\/\/doi.org\/10.1007\/978-3-030-29414-4","DOI":"10.1007\/978-3-030-29414-4 10.1007\/978-3-030-29414-4"},{"issue":"1\u20132","key":"1298_CR5","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. Theor. Comput. Sci. 276(1\u20132), 51\u201381 (2002)","journal-title":"Theor. Comput. Sci."},{"key":"1298_CR6","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1016\/j.tcs.2018.04.051","volume":"832","author":"T Friedrich","year":"2020","unstructured":"Friedrich, T., K\u00f6tzing, T., Lagodzinski, J.A.G., Neumann, F., Schirneck, M.: Analysis of the (1+1) EA on subclasses of linear functions under uniform and linear constraints. Theor. Comput. Sci. 832, 3\u201319 (2020)","journal-title":"Theor. Comput. Sci."},{"issue":"10","key":"1298_CR7","doi-asserted-by":"publisher","first-page":"3209","DOI":"10.1007\/s00453-020-00779-3","volume":"83","author":"F Neumann","year":"2021","unstructured":"Neumann, F., Pourhassan, M., Witt, C.: Improved runtime results for simple randomised search heuristics on linear functions with a uniform constraint. Algorithmica 83(10), 3209\u20133237 (2021)","journal-title":"Algorithmica"},{"key":"1298_CR8","unstructured":"Qian, C., Yu, Y., Zhou, Z.: Subset selection by pareto optimization. In: Advances in Neural Information Processing Systems 28: Annual Conference on Neural Information Processing Systems 2015, pp. 1774\u20131782 (2015)"},{"key":"1298_CR9","doi-asserted-by":"publisher","unstructured":"Qian, C., Shi, J., Yu, Y., Tang, K.: On subset selection with general cost constraints. In: Proceedings of the Twenty-Sixth International Joint Conference on Artificial Intelligence, IJCAI 2017, pp. 2613\u20132619. ijcai.org, (2017). https:\/\/doi.org\/10.24963\/ijcai.2017\/364","DOI":"10.24963\/ijcai.2017\/364"},{"key":"1298_CR10","doi-asserted-by":"publisher","first-page":"129","DOI":"10.1016\/j.tcs.2022.05.008","volume":"924","author":"V Roostapour","year":"2022","unstructured":"Roostapour, V., Neumann, A., Neumann, F.: Single- and multi-objective evolutionary algorithms for the knapsack problem with dynamically changing constraints. Theor. Comput. Sci. 924, 129\u2013147 (2022). https:\/\/doi.org\/10.1016\/j.tcs.2022.05.008","journal-title":"Theor. Comput. Sci."},{"key":"1298_CR11","doi-asserted-by":"publisher","DOI":"10.1016\/j.artint.2021.103597","volume":"302","author":"V Roostapour","year":"2022","unstructured":"Roostapour, V., Neumann, A., Neumann, F., Friedrich, T.: Pareto optimization for subset selection with dynamic cost constraints. Artif. Intell. 302, 103597 (2022). https:\/\/doi.org\/10.1016\/j.artint.2021.103597","journal-title":"Artif. Intell."},{"key":"1298_CR12","doi-asserted-by":"publisher","first-page":"259","DOI":"10.1162\/evco_a_00320","volume":"31","author":"RJ Aishwaryaprajna","year":"2023","unstructured":"Aishwaryaprajna, R.J.: Evolutionary and estimation of distribution algorithms for unconstrained, constrained and multi-objective noisy combinatorial optimisation problems. Evolut. Comput. 31, 259\u2013285 (2023). https:\/\/doi.org\/10.1162\/evco_a_00320","journal-title":"Evolut. Comput."},{"issue":"1","key":"1298_CR13","doi-asserted-by":"publisher","first-page":"73","DOI":"10.1287\/mnsc.6.1.73","volume":"6","author":"A Charnes","year":"1959","unstructured":"Charnes, A., Cooper, W.W.: Chance-constrained programming. Manage. Sci. 6(1), 73\u201379 (1959)","journal-title":"Manage. Sci."},{"issue":"6","key":"1298_CR14","doi-asserted-by":"publisher","first-page":"930","DOI":"10.1287\/opre.13.6.930","volume":"13","author":"BL Miller","year":"1965","unstructured":"Miller, B.L., Wagner, H.M.: Chance constrained programming with joint constraints. Oper. Res. 13(6), 930\u2013945 (1965)","journal-title":"Oper. Res."},{"issue":"33\u201334","key":"1298_CR15","doi-asserted-by":"publisher","first-page":"3190","DOI":"10.1016\/j.cma.2007.03.003","volume":"196","author":"H-G Beyer","year":"2007","unstructured":"Beyer, H.-G., Sendhoff, B.: Robust optimization-a comprehensive survey. Comput. Methods Appl. Mech. Eng. 196(33\u201334), 3190\u20133218 (2007)","journal-title":"Comput. Methods Appl. Mech. Eng."},{"issue":"1\u20132","key":"1298_CR16","doi-asserted-by":"publisher","first-page":"25","DOI":"10.1016\/j.compchemeng.2007.05.009","volume":"32","author":"P Li","year":"2008","unstructured":"Li, P., Arellano-Garcia, H., Wozny, G.: Chance constrained programming approach to process optimization under uncertainty. Comput. Chem. Eng. 32(1\u20132), 25\u201345 (2008)","journal-title":"Comput. Chem. Eng."},{"issue":"4","key":"1298_CR17","doi-asserted-by":"publisher","first-page":"2417","DOI":"10.1109\/TPWRS.2011.2154367","volume":"26","author":"H Zhang","year":"2011","unstructured":"Zhang, H., Li, P.: Chance constrained programming for optimal power flow under uncertainty. IEEE Trans. Power Syst. 26(4), 2417\u20132424 (2011)","journal-title":"IEEE Trans. Power Syst."},{"issue":"4","key":"1298_CR18","doi-asserted-by":"publisher","first-page":"524","DOI":"10.1287\/trsc.1100.0347","volume":"45","author":"R Nair","year":"2011","unstructured":"Nair, R., Miller-Hooks, E.: Fleet management for vehicle sharing operations. Transp. Sci. 45(4), 524\u2013540 (2011)","journal-title":"Transp. Sci."},{"key":"1298_CR19","doi-asserted-by":"publisher","first-page":"35","DOI":"10.1007\/s10107-015-0896-z","volume":"151","author":"GA Hanasusanto","year":"2015","unstructured":"Hanasusanto, G.A., Roitch, V., Kuhn, D., Wiesemann, W.: A distributionally robust perspective on uncertainty quantification and chance constrained programming. Math. Program. 151, 35\u201362 (2015)","journal-title":"Math. Program."},{"key":"1298_CR20","doi-asserted-by":"crossref","unstructured":"Neumann, A., Neumann, F.: Optimising monotone chance-constrained submodular functions using evolutionary multi-objective algorithms. In: PPSN (1). Lecture Notes in Computer Science, vol. 12269, pp. 404\u2013417. Springer (2020)","DOI":"10.1007\/978-3-030-58112-1_28"},{"key":"1298_CR21","doi-asserted-by":"crossref","unstructured":"Shi, F., Yan, X., Neumann, F.: Runtime analysis of simple evolutionary algorithms for the chance-constrained makespan scheduling problem. In: PPSN (2). Lecture Notes in Computer Science, vol. 13399, pp. 526\u2013541. Springer (2022)","DOI":"10.1007\/978-3-031-14721-0_37"},{"key":"1298_CR22","doi-asserted-by":"publisher","unstructured":"Neumann, F., Sutton, A.M.: Runtime analysis of the (1 + 1) evolutionary algorithm for the chance-constrained knapsack problem. In: Proceedings of the 15th ACM\/SIGEVO Conference on Foundations of Genetic Algorithms, FOGA 2019, pp. 147\u2013153. ACM, (2019)https:\/\/doi.org\/10.1145\/3299904.3340315","DOI":"10.1145\/3299904.3340315"},{"key":"1298_CR23","doi-asserted-by":"crossref","unstructured":"Xie, Y., Neumann, A., Neumann, F., Sutton, A.M.: Runtime analysis of RLS and the (1+1) EA for the chance-constrained knapsack problem with correlated uniform weights. In: Proceedings of the Genetic and Evolutionary Computation Conference, (GECCO 2021), pp. 1187\u20131194. ACM, (2021)","DOI":"10.1145\/3449639.3459381"},{"key":"1298_CR24","doi-asserted-by":"publisher","unstructured":"Xie, Y., Harper, O., Assimi, H., Neumann, A., Neumann, F.: Evolutionary algorithms for the chance-constrained knapsack problem. In: Proceedings of the Genetic and Evolutionary Computation Conference, (GECCO 2019), pp. 338\u2013346. ACM, (2019). https:\/\/doi.org\/10.1145\/3321707.3321869","DOI":"10.1145\/3321707.3321869"},{"key":"1298_CR25","doi-asserted-by":"publisher","unstructured":"Xie, Y., Neumann, A., Neumann, F.: Specific single- and multi-objective evolutionary algorithms for the chance-constrained knapsack problem. In: Proceedings of the Genetic and Evolutionary Computation Conference, (GECCO 2020), pp. 271\u2013279. ACM, (2020). https:\/\/doi.org\/10.1145\/3377930.3390162","DOI":"10.1145\/3377930.3390162"},{"key":"1298_CR26","doi-asserted-by":"publisher","unstructured":"Neumann, A., Xie, Y., Neumann, F.: Evolutionary algorithms for limiting the effect of uncertainty for the knapsack problem with stochastic profits. In: Parallel Problem Solving from Nature - PPSN XVII - 17th International Conference, PPSN 2022, Proceedings, Part I. Lecture Notes in Computer Science, vol. 13398, pp. 294\u2013307. Springer, (2022). https:\/\/doi.org\/10.1007\/978-3-031-14714-2_21","DOI":"10.1007\/978-3-031-14714-2_21"},{"key":"1298_CR27","doi-asserted-by":"crossref","unstructured":"Friedrich, T., K\u00f6tzing, T., Neumann, A., Neumann, F., Radhakrishnan, A.: Analysis of (1+1) EA on leadingones with constraints. In: GECCO, pp. 1584\u20131592. ACM (2023)","DOI":"10.1145\/3583131.3590453"},{"key":"1298_CR28","doi-asserted-by":"crossref","unstructured":"Friedrich, T., K\u00f6tzing, T., Lagodzinski, J.A.G., Neumann, F., Schirneck, M.: Analysis of the (1+1) EA on subclasses of linear functions under uniform and linear constraints. In: Foundations of Genetic Algorithms (FOGA), pp. 45\u201354. ACM Press (2017)","DOI":"10.1145\/3040718.3040728"},{"key":"1298_CR29","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, 21\u201335 (2004)","journal-title":"Nat. Comput."},{"key":"1298_CR30","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, 3017\u20133058 (2021). https:\/\/doi.org\/10.1007\/s00453-020-00775-7","journal-title":"Algorithmica"},{"key":"1298_CR31","doi-asserted-by":"publisher","first-page":"367","DOI":"10.1007\/s00453-022-00952-w","volume":"86","author":"B Doerr","year":"2022","unstructured":"Doerr, B., K\u00f6tzing, T.: Lower bounds from fitness levels made easy. Algorithmica 86, 367\u2013395 (2022)","journal-title":"Algorithmica"},{"issue":"1","key":"1298_CR32","doi-asserted-by":"publisher","first-page":"65","DOI":"10.1162\/106365606776022751","volume":"14","author":"C Witt","year":"2006","unstructured":"Witt, C.: Runtime analysis of the $$(\\mu + 1)$$ ea on simple pseudo-boolean functions. Evol. Comput. 14(1), 65\u201386 (2006). https:\/\/doi.org\/10.1162\/106365606776022751","journal-title":"Evol. Comput."},{"key":"1298_CR33","unstructured":"Weisstein, E.W.: Complementary Error Function. https:\/\/mathworld.wolfram.com\/Erfc.html. Accessed 2023-02-01"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-025-01298-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00453-025-01298-9\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-025-01298-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,5,8]],"date-time":"2025-05-08T11:01:17Z","timestamp":1746702077000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00453-025-01298-9"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,2,19]]},"references-count":33,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2025,5]]}},"alternative-id":["1298"],"URL":"https:\/\/doi.org\/10.1007\/s00453-025-01298-9","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,2,19]]},"assertion":[{"value":"29 September 2023","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"3 February 2025","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"19 February 2025","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 no competing interests.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Competing interests"}}]}}