{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,11]],"date-time":"2026-07-11T05:55:21Z","timestamp":1783749321608,"version":"3.55.0"},"reference-count":42,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2021,4,26]],"date-time":"2021-04-26T00:00:00Z","timestamp":1619395200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100000266","name":"EPSRC","doi-asserted-by":"crossref","award":["EP\/M004252\/1"],"award-info":[{"award-number":["EP\/M004252\/1"]}],"id":[{"id":"10.13039\/501100000266","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Evol. Learn. Optim."],"published-print":{"date-parts":[[2021,6,28]]},"abstract":"<jats:p>\n            We analyse the impact of the selective pressure for the global optimisation capabilities of steady-state evolutionary algorithms (EAs). For the standard bimodal benchmark function\n            <jats:sc>TwoMax<\/jats:sc>\n            , we rigorously prove that using uniform parent selection leads to exponential runtimes with high probability to locate both optima for the standard (\n            <jats:inline-formula>\n              <jats:alternatives>\n                <jats:tex-math>\n                  \n                <\/jats:tex-math>\n              <\/jats:alternatives>\n            <\/jats:inline-formula>\n            +1)\u00a0EA and (\n            <jats:inline-formula>\n              <jats:alternatives>\n                <jats:tex-math>\n                  \n                <\/jats:tex-math>\n              <\/jats:alternatives>\n            <\/jats:inline-formula>\n            +1)\u00a0RLS with any polynomial population sizes. However, we prove that selecting the worst individual as parent leads to efficient global optimisation with overwhelming probability for reasonable population sizes. Since always selecting the worst individual may have detrimental effects for escaping from local optima, we consider the performance of stochastic parent selection operators with low selective pressure for a function class called\n            <jats:sc>TruncatedTwoMax,<\/jats:sc>\n            where one slope is shorter than the other. An experimental analysis shows that the EAs equipped with inverse tournament selection, where the loser is selected for reproduction and small tournament sizes, globally optimise\n            <jats:sc>TwoMax<\/jats:sc>\n            efficiently and effectively escape from local optima of\n            <jats:sc>TruncatedTwoMax<\/jats:sc>\n            with high probability. Thus, they identify both optima efficiently while uniform (or stronger) selection fails in theory and in practice. We then show the power of inverse selection on function classes from the literature where populations are essential by providing rigorous proofs or experimental evidence that it outperforms uniform selection equipped with or without a restart strategy. We conclude the article by confirming our theoretical insights with an empirical analysis of the different selective pressures on standard benchmarks of the classical MaxSat and multidimensional knapsack problems.\n          <\/jats:p>","DOI":"10.1145\/3427474","type":"journal-article","created":{"date-parts":[[2021,4,26]],"date-time":"2021-04-26T15:45:41Z","timestamp":1619451941000},"page":"1-38","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":18,"title":["On Steady-State Evolutionary Algorithms and Selective Pressure: Why Inverse Rank-Based Allocation of Reproductive Trials Is Best"],"prefix":"10.1145","volume":"1","author":[{"given":"Dogan","family":"Corus","sequence":"first","affiliation":[{"name":"The University of Sheffield"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Andrei","family":"Lissovoi","sequence":"additional","affiliation":[{"name":"The University of Sheffield"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Pietro S.","family":"Oliveto","sequence":"additional","affiliation":[{"name":"The University of Sheffield"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Carsten","family":"Witt","sequence":"additional","affiliation":[{"name":"Technical University of Denmark"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2021,4,26]]},"reference":[{"key":"e_1_2_1_1_1","volume-title":"Proceedings of the 4th International Conference on Genetic Algorithms, R. K Belew and L. B. Booker (Eds.). Morgan Kaufmann, 92\u201399","author":"B\u00e4ck T.","unstructured":"T. B\u00e4ck and F. Hoffmeister. 1991. A survey of evolution strategies. In Proceedings of the 4th International Conference on Genetic Algorithms, R. K Belew and L. B. Booker (Eds.). Morgan Kaufmann, 92\u201399."},{"key":"e_1_2_1_2_1","volume-title":"Proceedings of the 4th International Conference on Genetic Algorithms. Morgan Kaufmann, 2--9.","author":"B\u00e4ck T.","unstructured":"T. B\u00e4ck, F. Hoffmeister, and H. P. Schwefel. 1991. A survey of evolution strategies. In Proceedings of the 4th International Conference on Genetic Algorithms. Morgan Kaufmann, 2--9."},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1057\/jors.1990.166"},{"key":"e_1_2_1_4_1","volume-title":"Random Graphs","author":"Bollobas B.","unstructured":"B. Bollobas. 1985. Random Graphs. Academic Press, London, UK."},{"key":"e_1_2_1_5_1","volume-title":"Proceedings of the Genetic and Evolutionary Computation Conference (GECCO\u201999)","author":"Branke J\u00fcrgen","year":"1999","unstructured":"J\u00fcrgen Branke, Massimo Cutaia, and Heinrich Dold. 1999. Reducing genetic drift in steady state evolutionary algorithms. In Proceedings of the Genetic and Evolutionary Computation Conference (GECCO\u201999). 68--74."},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1009642405419"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1109\/TEVC.2017.2753538"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1109\/TEVC.2017.2745715"},{"key":"e_1_2_1_9_1","doi-asserted-by":"crossref","unstructured":"D. Corus and P. S. Oliveto. 2020. On the benefits of populations for the exploitation speed of standard steady-state genetic algorithms. arXiv:1903.10976","DOI":"10.1145\/3321707.3321783"},{"key":"e_1_2_1_10_1","volume-title":"Lecture Notes in Computer Science","volume":"11102","author":"Corus D.","unstructured":"D. Corus, P. S. Oliveto, and D. Yazdani. 2018b. Fast artificial immune systems. In Parallel Problem Solving from Nature. Lecture Notes in Computer Science, Vol. 11102. Springer, 67--78."},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.artint.2019.03.001"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1109\/TEVC.2017.2724201"},{"key":"e_1_2_1_13_1","unstructured":"C. Darwin. 1859. On the Origin of the Species. John Murray."},{"key":"e_1_2_1_14_1","doi-asserted-by":"crossref","unstructured":"C. Darwin. 1868. The Variation of Animals and Plants Under Domestication. John Murray.","DOI":"10.5962\/bhl.title.37659"},{"key":"e_1_2_1_15_1","volume-title":"Proceedings of Foundations of Genetic Algorithms II (FOGA\u201993)","author":"De Jong K.","unstructured":"K. De Jong and J. Sarma. 1993. Generation gaps revisited. In Proceedings of Foundations of Genetic Algorithms II (FOGA\u201993). 19--28."},{"key":"e_1_2_1_16_1","volume-title":"Proceedings of the Genetic and Evolutionary Computation Conference (GECCO\u201915)","author":"Perthuis de Laillevault A.","unstructured":"A. de Perthuis de Laillevault, B. Doerr, and C. Doerr. 2015. Money for nothing: Speeding up evolutionary algorithms through better initialization. In Proceedings of the Genetic and Evolutionary Computation Conference (GECCO\u201915). ACM, New York, NY, 815--822."},{"key":"e_1_2_1_17_1","volume-title":"Theory of Randomized Search Heuristics: Foundations and Recent Developments","author":"Doerr B.","unstructured":"B. Doerr. 2011. Analyzing randomized search heuristics: Tools from probability theory. In Theory of Randomized Search Heuristics: Foundations and Recent Developments, B. Doerr and A. Auger (Eds.). World Scientific, 1--20."},{"key":"e_1_2_1_18_1","volume-title":"Proceedings of the Genetic and Evolutionary Computation Conference (GECCO\u201917)","author":"Doerr B.","unstructured":"B. Doerr, H. Ph. Le, R. Makhmara, and T. D. Nguyen. 2017. Fast genetic algorithms. In Proceedings of the Genetic and Evolutionary Computation Conference (GECCO\u201917). 777--784."},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1162\/evco.2009.17.4.17401"},{"key":"e_1_2_1_20_1","volume-title":"Genetic Algorithms in Search, Optimization and Machine Learning","author":"Goldberg D. E.","unstructured":"D. E. Goldberg. 1989. Genetic Algorithms in Search, Optimization and Machine Learning. Addison Wesley Longman."},{"key":"e_1_2_1_21_1","volume-title":"Proceedings of Foundations of Genetic Algorithms I (FOGA\u201991)","author":"Goldberg D. E.","unstructured":"D. E. Goldberg and K. Deb. 1991. A comparative analysis of selection schemes used in genetic algorithms. In Proceedings of Foundations of Genetic Algorithms I (FOGA\u201991). 69--93."},{"key":"e_1_2_1_22_1","volume-title":"Adaptation in Natural and Artificial Systems: An Introductory Analysis with Applications to Biology, Control, and Artificial Intelligence","author":"Holland J. H.","unstructured":"J. H. Holland. 1992. Adaptation in Natural and Artificial Systems: An Introductory Analysis with Applications to Biology, Control, and Artificial Intelligence. MIT Press, Cambridge, MA."},{"key":"e_1_2_1_23_1","first-page":"65","article-title":"A simple sequentially rejective multiple test procedure","volume":"6","author":"Holm S.","year":"1979","unstructured":"S. Holm. 1979. A simple sequentially rejective multiple test procedure. Scandinavian Journal of Statistics 6, 2 (1979), 65--70.","journal-title":"Scandinavian Journal of Statistics"},{"key":"e_1_2_1_24_1","volume-title":"SAT 2000","author":"Hoos H. H.","year":"2000","unstructured":"H. H. Hoos and T. St\u00fctzle. 2000. SATLIB: An online resource for research on SAT. SAT 2000 (2000), 283--292."},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1162\/106365605774666921"},{"key":"e_1_2_1_26_1","volume-title":"Proceedings of the 13th International Joint Conference on Artificial Intelligence (IJCAI\u201993)","author":"Kautz H.","unstructured":"H. Kautz and B. Selman. 1993. Domain-independent extension to GSAT: Solving large structured satisfiability problems. In Proceedings of the 13th International Joint Conference on Artificial Intelligence (IJCAI\u201993). 290--295."},{"key":"e_1_2_1_27_1","volume-title":"Proceedings of the 13th National Conference on Artificial Intelligence (AAAI\u201996)","author":"Kautz H.","unstructured":"H. Kautz and B. Selman. 1996. Pushing the envelope: Planning, propositional logic, and stochastic search. In Proceedings of the 13th National Conference on Artificial Intelligence (AAAI\u201996). 1194--1201."},{"key":"e_1_2_1_28_1","series-title":"Lecture Notes in Computer Science","volume-title":"Parallel Problem Solving from Nature","author":"Lehre P. K.","unstructured":"P. K. Lehre. 2010. Negative drift in populations. In Parallel Problem Solving from Nature. Lecture Notes in Computer Science, Vol. 6328. Springer, 244--253."},{"key":"e_1_2_1_29_1","series-title":"Lecture Notes in Computer Science","volume-title":"Parallel Problem Solving from Nature","author":"Lengler J.","unstructured":"J. Lengler. 2018. A general dichotomy of evolutionary algorithms on monotone functions. In Parallel Problem Solving from Nature. Lecture Notes in Computer Science, Vol. 11101. Springer, 3--15."},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2018.07.007"},{"key":"e_1_2_1_31_1","volume-title":"Proceedings of Foundations of Genetic Algorithms (FOGA\u201917)","author":"Covantes Osuna E.","unstructured":"E. Covantes Osuna and D. Sudholt. 2017. Analysis of the clearing diversity-preserving mechanism. In Proceedings of Foundations of Genetic Algorithms (FOGA\u201917). ACM, New York, NY, 55--63."},{"key":"e_1_2_1_32_1","volume-title":"Multimodal Optimization by Means of Evolutionary Algorithms","author":"Preuss M.","unstructured":"M. Preuss. 2015. Multimodal Optimization by Means of Evolutionary Algorithms. Springer."},{"key":"e_1_2_1_33_1","volume-title":"On replacement strategies in steady state evolutionary algorithms. Evolutionary Computation","author":"Smith J.","year":"2007","unstructured":"J. Smith. 2007. On replacement strategies in steady state evolutionary algorithms. Evolutionary Computation (2007), 29--59."},{"key":"e_1_2_1_34_1","unstructured":"H. Spencer. 1864. The Principles of Biology. Williams and Norgate."},{"key":"e_1_2_1_35_1","volume-title":"Theory of Randomized Search Heuristics in Discrete Search Spaces","author":"Sudholt D.","unstructured":"D. Sudholt. 2019. The benefits of population diversity in evolutionary algorithms: A survey of rigorous runtime analyses. In Theory of Randomized Search Heuristics in Discrete Search Spaces, B. Doerr and F. Neumann (Eds.). Springer, 359--404."},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/3205455.3205598"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.5555\/645512.657265"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1016\/B978-0-08-050684-5.50009-4"},{"key":"e_1_2_1_39_1","volume-title":"Proceedings of the 3rd International Conference on Genetic Algorithms. 116--121","author":"Whitley D.","year":"1989","unstructured":"D. Whitley. 1989. The Genitor algorithm and selection pressure: Why rank-based allocation of reproductive trials is best. In Proceedings of the 3rd International Conference on Genetic Algorithms. 116--121."},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.2307\/3001968"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1162\/106365606776022751"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2013.09.013"}],"container-title":["ACM Transactions on Evolutionary Learning and Optimization"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3427474","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3427474","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T21:24:40Z","timestamp":1750195480000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3427474"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,4,26]]},"references-count":42,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2021,6,28]]}},"alternative-id":["10.1145\/3427474"],"URL":"https:\/\/doi.org\/10.1145\/3427474","relation":{},"ISSN":["2688-299X","2688-3007"],"issn-type":[{"value":"2688-299X","type":"print"},{"value":"2688-3007","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,4,26]]},"assertion":[{"value":"2019-12-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2020-09-01","order":2,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2021-04-26","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}