{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,21]],"date-time":"2025-09-21T17:09:02Z","timestamp":1758474542070,"version":"3.37.3"},"reference-count":22,"publisher":"Springer Science and Business Media LLC","issue":"9","license":[{"start":{"date-parts":[[2024,7,2]],"date-time":"2024-07-02T00:00:00Z","timestamp":1719878400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2024,7,2]],"date-time":"2024-07-02T00:00:00Z","timestamp":1719878400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"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":[[2024,9]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Stagnation detection has been proposed as a mechanism for randomized search heuristics to escape from local optima by automatically increasing the size of the neighborhood to find the so-called gap size, i.\u00a0e., the distance to the next improvement. Its usefulness has mostly been considered in simple multimodal landscapes with few local optima that could be crossed one after another. In multimodal landscapes with a more complex location of optima of similar gap size, stagnation detection suffers from the fact that the neighborhood size is frequently reset to \u00a01 without using gap sizes that were promising in the past. In this paper, we investigate a new mechanism called <jats:italic>radius memory<\/jats:italic> which can be added to stagnation detection to control the search radius more carefully by giving preference to values that were successful in the past. We implement this idea in an algorithm called SD-RLS<jats:inline-formula><jats:alternatives><jats:tex-math>$$^{\\text {m}}$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mmultiscripts>\n                    <mml:mrow\/>\n                    <mml:mrow\/>\n                    <mml:mtext>m<\/mml:mtext>\n                  <\/mml:mmultiscripts>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula> and show compared to previous variants of stagnation detection that it yields speed-ups for linear functions under uniform constraints and the minimum spanning tree problem. Moreover, its running time does not significantly deteriorate on unimodal functions and a generalization of the <jats:sc>Jump<\/jats:sc> benchmark. Finally, we present experimental results carried out to study SD-RLS<jats:inline-formula><jats:alternatives><jats:tex-math>$$^{\\text {m}}$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mmultiscripts>\n                    <mml:mrow\/>\n                    <mml:mrow\/>\n                    <mml:mtext>m<\/mml:mtext>\n                  <\/mml:mmultiscripts>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula> and compare it with other algorithms.<\/jats:p>","DOI":"10.1007\/s00453-024-01249-w","type":"journal-article","created":{"date-parts":[[2024,7,2]],"date-time":"2024-07-02T07:02:33Z","timestamp":1719903753000},"page":"2929-2958","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Stagnation Detection in Highly Multimodal Fitness Landscapes"],"prefix":"10.1007","volume":"86","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-0898-5003","authenticated-orcid":false,"given":"Amirhossein","family":"Rajabi","sequence":"first","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,7,2]]},"reference":[{"doi-asserted-by":"crossref","unstructured":"Rajabi, A., Witt, C.: Self-adjusting evolutionary algorithms for multimodal optimization. In: Proceedings of GECCO\u00a0\u201920 (2020), pp. 1314\u20131322","key":"1249_CR1","DOI":"10.1145\/3377930.3389833"},{"key":"1249_CR2","doi-asserted-by":"publisher","first-page":"271","DOI":"10.1007\/978-3-030-29414-4_6","volume-title":"Theory of Evolutionary Computation\u2014Recent Developments in Discrete Optimization","author":"B Doerr","year":"2020","unstructured":"Doerr, B., Doerr, C.: Theory of parameter control for discrete black-box optimization: provable performance gains through dynamic parameter choices. In: Doerr, B., Neumann, F. (eds.) Theory of Evolutionary Computation\u2014Recent Developments in Discrete Optimization, pp. 271\u2013321. Springer, Cham (2020)"},{"key":"1249_CR3","doi-asserted-by":"publisher","first-page":"87","DOI":"10.1016\/j.tcs.2014.11.028","volume":"567","author":"B Doerr","year":"2015","unstructured":"Doerr, B., Doerr, C., Ebel, F.: From black-box complexity to designing new genetic algorithms. Theor. Comput. Sci. 567, 87\u2013104 (2015)","journal-title":"Theor. Comput. Sci."},{"issue":"5","key":"1249_CR4","doi-asserted-by":"publisher","first-page":"1658","DOI":"10.1007\/s00453-017-0354-9","volume":"80","author":"B Doerr","year":"2018","unstructured":"Doerr, B., Doerr, C.: Optimal static and self-adjusting parameter choices for the (1+($$\\lambda $$, $$\\lambda $$)) genetic algorithm. Algorithmica 80(5), 1658\u20131709 (2018)","journal-title":"Algorithmica"},{"issue":"6","key":"1249_CR5","doi-asserted-by":"publisher","first-page":"1694","DOI":"10.1007\/s00453-022-00933-z","volume":"84","author":"A Rajabi","year":"2022","unstructured":"Rajabi, A., Witt, C.: Self-adjusting evolutionary algorithms for multimodal optimization. Algorithmica 84(6), 1694\u20131723 (2022). https:\/\/doi.org\/10.1007\/s00453-022-00933-z","journal-title":"Algorithmica"},{"doi-asserted-by":"crossref","unstructured":"Doerr, B., Le, H.P., Makhmara, R., Nguyen, T.D.: Fast genetic algorithms. In: Proceedings of GECCO \u201917 (2017), pp. 777\u2013784","key":"1249_CR6","DOI":"10.1145\/3071178.3071301"},{"key":"1249_CR7","doi-asserted-by":"publisher","DOI":"10.1162\/evco_a_00313","author":"A Rajabi","year":"2022","unstructured":"Rajabi, A., Witt, C.: Stagnation detection with randomized local search. Evol. Comput. (2022). https:\/\/doi.org\/10.1162\/evco_a_00313","journal-title":"Evol. Comput."},{"key":"1249_CR8","doi-asserted-by":"publisher","first-page":"759","DOI":"10.1007\/978-3-319-07124-4_19","volume-title":"Handbook of Heuristics","author":"P Hansen","year":"2018","unstructured":"Hansen, P., Mladenovic, N.: Variable neighborhood search. In: Mart\u00ed, R., Pardalos, P.M., Resende, M.G.C. (eds.) Handbook of Heuristics, pp. 759\u2013787. Springer, Boston (2018)"},{"doi-asserted-by":"crossref","unstructured":"Doerr, B., Fouz, M., Witt, C.: Quasirandom evolutionary algorithms. In: Proceedings of GECCO \u201910 (2010), pp. 1457\u20131464","key":"1249_CR9","DOI":"10.1145\/1830483.1830749"},{"key":"1249_CR10","doi-asserted-by":"publisher","first-page":"32","DOI":"10.1016\/j.tcs.2006.11.002","volume":"378","author":"F Neumann","year":"2007","unstructured":"Neumann, F., Wegener, I.: Randomized local search, evolutionary algorithms, and the minimum spanning tree problem. Theor. Comput. Sci. 378, 32\u201340 (2007)","journal-title":"Theor. Comput. Sci."},{"doi-asserted-by":"publisher","unstructured":"Reichel, J., Skutella, M.: On the size of weights in randomized search heuristics. In: Proceedings of FOGA\u00a02009 (2009), pp. 21\u201328. https:\/\/doi.org\/10.1145\/1527125.1527130","key":"1249_CR11","DOI":"10.1145\/1527125.1527130"},{"doi-asserted-by":"crossref","unstructured":"Doerr, B., Zheng, W.: Theoretical analyses of multi-objective evolutionary algorithms on multi-modal objectives. In: Proceedings of AAAI\u00a02021 (2021)","key":"1249_CR12","DOI":"10.1145\/3449726.3462719"},{"issue":"3","key":"1249_CR13","doi-asserted-by":"publisher","first-page":"529","DOI":"10.1007\/s00453-015-0019-5","volume":"75","author":"B Doerr","year":"2016","unstructured":"Doerr, B., Doerr, C.: The impact of random initialization on the runtime of randomized search heuristics. Algorithmica 75(3), 529\u2013553 (2016)","journal-title":"Algorithmica"},{"key":"1249_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. Theoretical Computer Science 276, 51\u201381 (2002)","journal-title":"Theoretical Computer Science"},{"key":"1249_CR15","volume-title":"Evolutionary Optimization","author":"I Wegener","year":"2001","unstructured":"Wegener, I.: Methods for the analysis of evolutionary algorithms on pseudo-Boolean functions. In: Sarker, R., Mohammadian, M., Yao, X. (eds.) Evolutionary Optimization. Springer, Boston (2001)"},{"doi-asserted-by":"crossref","unstructured":"Bambury, H., Bultel, A., Doerr, B.: Generalized jump functions. In: Proceedings of GECCO\u00a02021 (2021), pp. 1124\u20131132","key":"1249_CR16","DOI":"10.1145\/3449639.3459367"},{"doi-asserted-by":"crossref","unstructured":"Witt, C.: On crossing fitness valleys with majority-vote crossover and estimation-of-distribution algorithms. In: Proceedings of FOGA\u00a02021 (2021), pp. 1\u201315","key":"1249_CR17","DOI":"10.1145\/3450218.3477303"},{"issue":"10","key":"1249_CR18","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). https:\/\/doi.org\/10.1007\/s00453-020-00779-3","journal-title":"Algorithmica"},{"key":"1249_CR19","doi-asserted-by":"publisher","first-page":"89","DOI":"10.1007\/978-3-030-29414-4_2","volume-title":"Theory of Evolutionary Computation\u2014Cent Developments in Discrete Optimization","author":"J Lengler","year":"2020","unstructured":"Lengler, J.: Drift analysis. In: Doerr, B., Neumann, F. (eds.) Theory of Evolutionary Computation\u2014Cent Developments in Discrete Optimization, pp. 89\u2013131. Springer, Cham (2020)"},{"issue":"2","key":"1249_CR20","doi-asserted-by":"publisher","first-page":"145","DOI":"10.1109\/TEVC.2006.871251","volume":"10","author":"GR Raidl","year":"2006","unstructured":"Raidl, G.R., Koller, G., Julstrom, B.A.: Biased mutation operators for subgraph-selection problems. IEEE Trans. Evol. Comput. 10(2), 145\u2013156 (2006)","journal-title":"IEEE Trans. Evol. Comput."},{"key":"1249_CR21","doi-asserted-by":"publisher","first-page":"673","DOI":"10.1007\/s00453-012-9622-x","volume":"64","author":"B Doerr","year":"2012","unstructured":"Doerr, B., Johannsen, D., Winzen, C.: Multiplicative drift analysis. Algorithmica 64, 673\u2013697 (2012)","journal-title":"Algorithmica"},{"doi-asserted-by":"crossref","unstructured":"Witt, C.: Population size vs. runtime of a simple EA. In: Proceedings of the Congress on Evolutionary Computation (CEC\u00a02003), vol. 3 (2003), pp. 1996\u20132003","key":"1249_CR22","DOI":"10.1109\/CEC.2003.1299918"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-024-01249-w.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00453-024-01249-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-01249-w.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,9,4]],"date-time":"2024-09-04T07:05:43Z","timestamp":1725433543000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00453-024-01249-w"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,7,2]]},"references-count":22,"journal-issue":{"issue":"9","published-print":{"date-parts":[[2024,9]]}},"alternative-id":["1249"],"URL":"https:\/\/doi.org\/10.1007\/s00453-024-01249-w","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"type":"print","value":"0178-4617"},{"type":"electronic","value":"1432-0541"}],"subject":[],"published":{"date-parts":[[2024,7,2]]},"assertion":[{"value":"25 October 2021","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"22 June 2024","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"2 July 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":"We have no Conflict of interest.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}},{"value":"Not applicable.","order":3,"name":"Ethics","group":{"name":"EthicsHeading","label":"Research Involving Human Participants and\/or Animals"}},{"value":"Not applicable.","order":4,"name":"Ethics","group":{"name":"EthicsHeading","label":"Informed Consent"}}]}}