{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,15]],"date-time":"2026-04-15T19:46:21Z","timestamp":1776282381474,"version":"3.50.1"},"reference-count":40,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2021,6,13]],"date-time":"2021-06-13T00:00:00Z","timestamp":1623542400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2021,6,13]],"date-time":"2021-06-13T00:00:00Z","timestamp":1623542400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100001652","name":"Friedrich-Alexander-Universit\u00e4t Erlangen-N\u00fcrnberg","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100001652","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Nat Comput"],"published-print":{"date-parts":[[2022,12]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Meta-heuristics are powerful tools for solving optimization problems whose structural properties are unknown or cannot be exploited algorithmically. We propose such a meta-heuristic for a large class of optimization problems over discrete domains based on the <jats:italic>particle swarm optimization<\/jats:italic> (PSO) paradigm. We provide a comprehensive formal analysis of the performance of this algorithm on certain \u201ceasy\u201d reference problems in a black-box setting, namely the sorting problem and the problem O<jats:sc>ne<\/jats:sc>M<jats:sc>ax<\/jats:sc>. In our analysis we use a Markov model of the proposed algorithm to obtain upper and lower bounds on its expected optimization time. Our bounds are essentially tight with respect to the Markov model. We show that for a suitable choice of algorithm parameters the expected optimization time is comparable to that of known algorithms and, furthermore, for other parameter regimes, the algorithm behaves less greedy and more explorative, which can be desirable in practice in order to escape local optima. Our analysis provides a precise insight on the tradeoff between optimization time and exploration. To obtain our results we introduce the notion of <jats:italic>indistinguishability<\/jats:italic> of states of a Markov chain and provide bounds on the solution of a recurrence equation with non-constant coefficients by integration.<\/jats:p>","DOI":"10.1007\/s11047-021-09856-0","type":"journal-article","created":{"date-parts":[[2021,6,13]],"date-time":"2021-06-13T05:02:37Z","timestamp":1623560557000},"page":"651-677","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":7,"title":["Exact Markov chain-based runtime analysis of a discrete particle swarm optimization algorithm on sorting and OneMax"],"prefix":"10.1007","volume":"21","author":[{"given":"Moritz","family":"M\u00fchlenthaler","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-1274-6398","authenticated-orcid":false,"given":"Alexander","family":"Ra\u00df","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Manuel","family":"Schmitt","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-5729-3727","authenticated-orcid":false,"given":"Rolf","family":"Wanka","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2021,6,13]]},"reference":[{"key":"9856_CR1","doi-asserted-by":"publisher","unstructured":"Antipov D, Doerr B, Fang J, Hetet T (2018) A tight runtime analysis for the ($$\\mu $$ + $$\\lambda $$) EA. In: Proc of the genetic and evolutionary computation conference (GECCO), pp 1459\u20131466. https:\/\/doi.org\/10.1145\/3205455.3205627","DOI":"10.1145\/3205455.3205627"},{"key":"9856_CR2","doi-asserted-by":"publisher","unstructured":"Antipov D, Doerr B, Yang Q (2019) The efficiency threshold for the offspring population size of the ($$\\mu $$, $$\\lambda $$) EA. In: Proc. of the genetic and evolutionary computation conference (GECCO), pp 1461\u20131469. https:\/\/doi.org\/10.1145\/3321707.3321838","DOI":"10.1145\/3321707.3321838"},{"issue":"2","key":"9856_CR3","doi-asserted-by":"publisher","first-page":"224","DOI":"10.1137\/S089548019528280X","volume":"11","author":"V Bafna","year":"1998","unstructured":"Bafna V, Pevzner PA (1998) Sorting by transpositions. SIAM J Discrete Math 11(2):224\u2013240. https:\/\/doi.org\/10.1137\/S089548019528280X","journal-title":"SIAM J Discrete Math"},{"key":"9856_CR4","doi-asserted-by":"publisher","unstructured":"Doerr B, Neumann F (2020) Theory of evolutionary computation\u2014recent developments in discrete optimization. Springer. https:\/\/doi.org\/10.1007\/978-3-030-29414-4","DOI":"10.1007\/978-3-030-29414-4"},{"key":"9856_CR5","doi-asserted-by":"publisher","unstructured":"Doerr B, Neumann F, Sudholt D, Witt C (2007) On the runtime analysis of the 1-ANT ACO algorithm. In: Proc. 9th ACM genetic and evolutionary computation conference (GECCO), pp 33\u201340. https:\/\/doi.org\/10.1145\/1276958.1276964","DOI":"10.1145\/1276958.1276964"},{"key":"9856_CR6","doi-asserted-by":"publisher","unstructured":"Droste S, Jansen T, Wegener I (2001) Dynamic parameter control in simple evolutionary algorithms. In: Proc. 6th workshop on foundations of genetic algorithms (FOGA), pp 275\u2013294. https:\/\/doi.org\/10.1016\/B978-155860734-7\/50098-6","DOI":"10.1016\/B978-155860734-7\/50098-6"},{"issue":"1","key":"9856_CR7","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 (2002) On the analysis of the (1+1) evolutionary algorithm. Theor Comput Sci 276(1):51\u201381. https:\/\/doi.org\/10.1016\/S0304-3975(01)00182-7","journal-title":"Theor Comput Sci"},{"key":"9856_CR8","doi-asserted-by":"publisher","unstructured":"Durrett R (2010) Probability: theory and examples. Cambridge Series in Statistical and Probabilistic Mathematics, Cambridge University Press. https:\/\/doi.org\/10.1017\/9781108591034","DOI":"10.1017\/9781108591034"},{"key":"9856_CR9","doi-asserted-by":"publisher","unstructured":"Eberhart RC, Kennedy J (1995) A new optimizer using particle swarm theory. In: Proc. 6th international symposium on micro machine and human science, pp 39\u201343. https:\/\/doi.org\/10.1109\/MHS.1995.494215","DOI":"10.1109\/MHS.1995.494215"},{"issue":"2","key":"9856_CR10","doi-asserted-by":"publisher","first-page":"173","DOI":"10.1162\/evco.1999.7.2.173","volume":"7","author":"J Garnier","year":"1999","unstructured":"Garnier J, Kallel L, Schoenauer M (1999) Rigorous hitting times for binary mutations. Evol Comput 7(2):173\u2013203. https:\/\/doi.org\/10.1162\/evco.1999.7.2.173","journal-title":"Evol Comput"},{"key":"9856_CR11","doi-asserted-by":"publisher","unstructured":"Giel O, Wegener I (2003) Evolutionary algorithms and the maximum matching problem. In: Proc. 20th symp. on theoretical aspects of computer science (STACS), pp 415\u2013426. https:\/\/doi.org\/10.1007\/3-540-36494-3_37","DOI":"10.1007\/3-540-36494-3_37"},{"issue":"5","key":"9856_CR12","doi-asserted-by":"publisher","first-page":"691","DOI":"10.1086\/284095","volume":"121","author":"JH Gillespie","year":"1983","unstructured":"Gillespie JH (1983) Some properties of finite populations experiencing strong selection and weak mutation. Am Nat 121(5):691\u2013708. https:\/\/doi.org\/10.1086\/284095","journal-title":"Am Nat"},{"key":"9856_CR13","unstructured":"Graham RL, Knuth DE, Patashnik O (1994) Concrete mathematics: a foundation for computer science, 2nd edn. Addison-Wesley Longman"},{"issue":"7","key":"9856_CR14","doi-asserted-by":"publisher","first-page":"689","DOI":"10.4169\/amer.math.monthly.122.7.689","volume":"122","author":"MD Hirschhorn","year":"2015","unstructured":"Hirschhorn MD (2015) Wallis\u2019s product and the central binomial coefficient. Am Math Mon 122(7):689. https:\/\/doi.org\/10.4169\/amer.math.monthly.122.7.689","journal-title":"Am Math Mon"},{"key":"9856_CR15","doi-asserted-by":"publisher","unstructured":"Hoffmann M, M\u00fchlenthaler M, Helwig S, Wanka R (2011) Discrete particle swarm optimization for TSP: theoretical results and experimental evaluations. In: Proc. 2nd int. conf. on adaptive and intelligent systems (ICAIS), pp 416\u2013427. https:\/\/doi.org\/10.1007\/978-3-642-23857-4_40","DOI":"10.1007\/978-3-642-23857-4_40"},{"key":"9856_CR16","doi-asserted-by":"publisher","unstructured":"Kennedy J, Eberhart RC (1995) Particle swarm optimization. In: Proc. IEEE international conference on neural networks, vol\u00a04, pp 1942\u20131948. https:\/\/doi.org\/10.1109\/ICNN.1995.488968","DOI":"10.1109\/ICNN.1995.488968"},{"key":"9856_CR17","doi-asserted-by":"publisher","unstructured":"Kennedy J, Eberhart RC (1997) A discrete binary version of the particle swarm algorithm. In: Proc. IEEE int. conf. on systems, man, and cybernetics, vol\u00a05, pp 4104\u20134108. https:\/\/doi.org\/10.1109\/ICSMC.1997.637339","DOI":"10.1109\/ICSMC.1997.637339"},{"key":"9856_CR18","doi-asserted-by":"publisher","unstructured":"K\u00f6tzing T, Krejca MS (2018) First-hitting times for finite state spaces. In: Auger A, Fonseca CM, Louren\u00e7o N, Machado P, Paquete L, Whitley D (eds) Parallel problem solving from nature\u2014PPSN XV. Springer International Publishing, Cham, pp 79\u201391. https:\/\/doi.org\/10.1007\/978-3-319-99259-4_7","DOI":"10.1007\/978-3-319-99259-4_7"},{"issue":"6","key":"9856_CR19","doi-asserted-by":"publisher","first-page":"1087","DOI":"10.1063\/1.1699114","volume":"21","author":"N Metropolis","year":"1953","unstructured":"Metropolis N, Rosenbluth AW, Rosenbluth MN, Teller AH, Teller E (1953) Equation of state calculations by fast computing machines. J Chem Phys 21(6):1087\u20131092. https:\/\/doi.org\/10.1063\/1.1699114","journal-title":"J Chem Phys"},{"key":"9856_CR20","doi-asserted-by":"publisher","unstructured":"Mitzenmacher M, Upfal E (2005) Probability and computing. Cambridge University Press. https:\/\/doi.org\/10.1017\/CBO9780511813603","DOI":"10.1017\/CBO9780511813603"},{"key":"9856_CR21","doi-asserted-by":"publisher","unstructured":"M\u00fchlenthaler M, Ra\u00df A, Schmitt M, Siegling A, Wanka R (2017) Runtime analysis of a discrete particle swarm optimization algorithm on sorting and OneMax. In: Proc. 14th ACM\/sigevo workshop on foundations of genetic algorithms (FOGA), pp 13\u201324. https:\/\/doi.org\/10.1145\/3040718.3040721","DOI":"10.1145\/3040718.3040721"},{"issue":"2","key":"9856_CR22","doi-asserted-by":"publisher","first-page":"243","DOI":"10.1007\/s00453-007-9134-2","volume":"54","author":"F Neumann","year":"2007","unstructured":"Neumann F, Witt C (2007) Runtime analysis of a simple ant colony optimization algorithm. Algorithmica 54(2):243\u2013255. https:\/\/doi.org\/10.1007\/s00453-007-9134-2","journal-title":"Algorithmica"},{"key":"9856_CR23","doi-asserted-by":"publisher","first-page":"183","DOI":"10.1007\/s10596-009-9142-1","volume":"14","author":"JE Onwunalu","year":"2010","unstructured":"Onwunalu JE, Durlofsky LJ (2010) Application of a particle swarm optimization algorithm for determining optimum well location and type. Comput Geosci 14:183\u2013198. https:\/\/doi.org\/10.1007\/s10596-009-9142-1","journal-title":"Comput Geosci"},{"key":"9856_CR24","doi-asserted-by":"publisher","unstructured":"Papadimitriou CH (1991) On selecting a satisfying truth assignment. In: Proc. 32nd IEEE symp. on foundations of computer science (FOCS), pp 163\u2013169. https:\/\/doi.org\/10.1109\/SFCS.1991.185365","DOI":"10.1109\/SFCS.1991.185365"},{"key":"9856_CR25","doi-asserted-by":"publisher","unstructured":"Papadimitriou CH, Sch\u00e4ffer AA, Yannakakis M (1990) On the complexity of local search. In: Proc. 22nd ACM symposium on theory of computing (STOC), pp 438\u2013445. https:\/\/doi.org\/10.1145\/100216.100274","DOI":"10.1145\/100216.100274"},{"issue":"2","key":"9856_CR26","doi-asserted-by":"publisher","first-page":"243","DOI":"10.1016\/0747-7171(92)90038-6","volume":"14","author":"M Petkov\u0161ek","year":"1992","unstructured":"Petkov\u0161ek M (1992) Hypergeometric solutions of linear recurrences with polynomial coefficients. J Symb Comput 14(2):243\u2013264. https:\/\/doi.org\/10.1016\/0747-7171(92)90038-6","journal-title":"J Symb Comput"},{"key":"9856_CR27","first-page":"232","volume":"1","author":"K Ramanathan","year":"2009","unstructured":"Ramanathan K, Periasamy VM, Pushpavanam M, Natarajan U (2009) Particle swarm optimisation of hardness in nickel diamond electro composites. Arch Comput Mater Sci Surf Eng 1:232\u2013236","journal-title":"Arch Comput Mater Sci Surf Eng"},{"key":"9856_CR28","doi-asserted-by":"publisher","unstructured":"Ra\u00df A, Schreiner J, Wanka R (2019) Runtime analysis of discrete particle swarm optimization applied to shortest paths computation. Evol Comput Comb Optim (EvoCOP), pp 115\u2013130. https:\/\/doi.org\/10.1007\/978-3-030-16711-0_8","DOI":"10.1007\/978-3-030-16711-0_8"},{"issue":"4","key":"9856_CR29","doi-asserted-by":"publisher","first-page":"349","DOI":"10.1023\/B:JMMA.0000049379.14872.f5","volume":"3","author":"J Scharnow","year":"2004","unstructured":"Scharnow J, Tinnefeld K, Wegener I (2004) The analysis of evolutionary algorithms on sorting and shortest paths problems. J Math Model Algorithms 3(4):349\u2013366. https:\/\/doi.org\/10.1023\/B:JMMA.0000049379.14872.f5","journal-title":"J Math Model Algorithms"},{"key":"9856_CR30","doi-asserted-by":"publisher","unstructured":"Schmitt M, Wanka R (2015) Particle swarm optimization almost surely finds local optima. Theor Comput Sci 561, Part A:57 \u2013 72. https:\/\/doi.org\/10.1016\/j.tcs.2014.05.017","DOI":"10.1016\/j.tcs.2014.05.017"},{"key":"9856_CR31","doi-asserted-by":"publisher","unstructured":"Sch\u00f6ning U (1999) A probabilistic algorithm for $$k$$-SAT and constraint satisfaction problems. In: Proc. 40th IEEE symp. on foundations of computer science (FOCS), pp 410\u2013414. https:\/\/doi.org\/10.1109\/SFFCS.1999.814612","DOI":"10.1109\/SFFCS.1999.814612"},{"key":"9856_CR32","doi-asserted-by":"publisher","unstructured":"Schwab L, Schmitt M, Wanka R (2015) Multimodal medical image registration using particle swarm optimization with influence of the data\u2019s initial orientation. In: Proc. 12th IEEE conf. on computational intelligence in bioinformatics and computational biology (CIBCB), pp 403\u2013410. https:\/\/doi.org\/10.1109\/CIBCB.2015.7300314","DOI":"10.1109\/CIBCB.2015.7300314"},{"issue":"3","key":"9856_CR33","doi-asserted-by":"publisher","first-page":"418","DOI":"10.1109\/TEVC.2012.2202241","volume":"17","author":"D Sudholt","year":"2013","unstructured":"Sudholt D (2013) A new method for lower bounds on the running time of evolutionary algorithms. IEEE Trans Evol Comput 17(3):418\u2013435. https:\/\/doi.org\/10.1109\/TEVC.2012.2202241","journal-title":"IEEE Trans Evol Comput"},{"key":"9856_CR34","doi-asserted-by":"publisher","first-page":"165","DOI":"10.1016\/j.jda.2011.06.002","volume":"10","author":"D Sudholt","year":"2012","unstructured":"Sudholt D, Thyssen C (2012) Running time analysis of ant colony optimization for shortest path problems. J Discrete Algorithms 10:165\u2013180. https:\/\/doi.org\/10.1016\/j.jda.2011.06.002","journal-title":"J Discrete Algorithms"},{"key":"9856_CR35","doi-asserted-by":"publisher","unstructured":"Sudholt D, Witt C (2008) Runtime analysis of binary PSO. In: Proc. 10th ACM genetic and evolutionary computation conf. (GECCO), pp 135\u2013142. https:\/\/doi.org\/10.1145\/1389095.1389114","DOI":"10.1145\/1389095.1389114"},{"issue":"21","key":"9856_CR36","doi-asserted-by":"publisher","first-page":"2084","DOI":"10.1016\/j.tcs.2010.03.002","volume":"411","author":"D Sudholt","year":"2010","unstructured":"Sudholt D, Witt C (2010) Runtime analysis of a binary particle swarm optimizer. Theor Comput Sci 411(21):2084\u20132100. https:\/\/doi.org\/10.1016\/j.tcs.2010.03.002","journal-title":"Theor Comput Sci"},{"key":"9856_CR37","doi-asserted-by":"publisher","unstructured":"Veeramachaneni K, Osadciw L, Kamath G (2007) Probabilistically driven particle swarms for optimization of multi valued discrete problems: design and analysis. In: Proc. IEEE swarm intelligence symposium (SIS), pp 141\u2013149. https:\/\/doi.org\/10.1109\/SIS.2007.368038","DOI":"10.1109\/SIS.2007.368038"},{"key":"9856_CR38","doi-asserted-by":"publisher","first-page":"289","DOI":"10.1109\/TEVC.2004.826068","volume":"8","author":"MP Wachowiak","year":"2004","unstructured":"Wachowiak MP, Smol\u00edkov\u00e1 R, Zheng Y, Zurada JM, Elmaghraby AS (2004) An approach to multimodal biomedical image registration utilizing particle swarm optimization. IEEE Trans Evol Comput 8:289\u2013301. https:\/\/doi.org\/10.1109\/TEVC.2004.826068","journal-title":"IEEE Trans Evol Comput"},{"key":"9856_CR39","doi-asserted-by":"publisher","unstructured":"Wegener I (2002) Methods for the analysis of evolutionary algorithms on pseudo-boolean functions. In: Sarker R, Mohammadian M, Yao X (eds) Evolutionary optimization. Springer, Chap\u00a014, pp 349\u2013369. https:\/\/doi.org\/10.1007\/0-306-48041-7_14","DOI":"10.1007\/0-306-48041-7_14"},{"key":"9856_CR40","doi-asserted-by":"publisher","first-page":"606","DOI":"10.1016\/j.agrformet.2016.10.019","volume":"232","author":"Q Yang","year":"2017","unstructured":"Yang Q, Wu J, Li Y, Li W, Wang L, Yang Y (2017) Using the particle swarm optimization algorithm to calibrate the parameters relating to the turbulent flux in the surface layer in the source region of the Yellow River. Agric For Meteorol 232:606\u2013622. https:\/\/doi.org\/10.1016\/j.agrformet.2016.10.019","journal-title":"Agric For Meteorol"}],"container-title":["Natural Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s11047-021-09856-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s11047-021-09856-0\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s11047-021-09856-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,11,28]],"date-time":"2022-11-28T04:48:17Z","timestamp":1669610897000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s11047-021-09856-0"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,6,13]]},"references-count":40,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2022,12]]}},"alternative-id":["9856"],"URL":"https:\/\/doi.org\/10.1007\/s11047-021-09856-0","relation":{},"ISSN":["1567-7818","1572-9796"],"issn-type":[{"value":"1567-7818","type":"print"},{"value":"1572-9796","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,6,13]]},"assertion":[{"value":"4 May 2021","order":1,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"13 June 2021","order":2,"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 that they have no conflict of interest.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}]}}