{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,5,14]],"date-time":"2025-05-14T04:50:14Z","timestamp":1747198214291,"version":"3.40.5"},"reference-count":26,"publisher":"Walter de Gruyter GmbH","issue":"4","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2019,8,27]]},"abstract":"<jats:title>Abstract<\/jats:title>\n               <jats:p>A discrete <jats:italic>particle swarm optimization<\/jats:italic> (PSO) algorithm is a randomized search heuristic for discrete optimization problems. A fundamental question about randomized search heuristics is how long it takes, in expectation, until an optimal solution is found. We give an overview of recent developments related to this question for discrete PSO algorithms. In particular, we give a comparison of known upper and lower bounds of expected runtimes and briefly discuss the techniques used to obtain these bounds.<\/jats:p>","DOI":"10.1515\/itit-2019-0009","type":"journal-article","created":{"date-parts":[[2019,10,24]],"date-time":"2019-10-24T15:14:06Z","timestamp":1571930046000},"page":"177-185","source":"Crossref","is-referenced-by-count":0,"title":["Runtime analysis of discrete particle swarm optimization algorithms: A survey"],"prefix":"10.1515","volume":"61","author":[{"given":"Moritz","family":"M\u00fchlenthaler","sequence":"first","affiliation":[{"name":"Fakult\u00e4t f\u00fcr Mathematik , TU Dortmund , Dortmund , Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-1274-6398","authenticated-orcid":false,"given":"Alexander","family":"Ra\u00df","sequence":"additional","affiliation":[{"name":"9171 Friedrich-Alexander-Universit\u00e4t Erlangen-N\u00fcrnberg , Erlangen , Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"374","published-online":{"date-parts":[[2019,10,24]]},"reference":[{"doi-asserted-by":"crossref","unstructured":"S. Baswana, S. Biswas, B. Doerr, T. Friedrich, P.\u2009P. Kurur, and F. Neumann. Computing single source shortest paths using single-objective fitness. In Proc. of the 10th ACM\/SIGEVO Workshop on Foundations of Genetic Algorithms (FOGA), pages 59\u201366, 2009.","key":"2023033119481082869_j_itit-2019-0009_ref_001_w2aab3b7d346b1b6b1ab2ab1Aa","DOI":"10.1145\/1527125.1527134"},{"doi-asserted-by":"crossref","unstructured":"R. Bellman. Dynamic programming treatment of the travelling salesman problem. J. ACM, 9(1):61\u201363, Jan. 1962.","key":"2023033119481082869_j_itit-2019-0009_ref_002_w2aab3b7d346b1b6b1ab2ab2Aa","DOI":"10.1145\/321105.321111"},{"doi-asserted-by":"crossref","unstructured":"M.\u2009R. Bonyadi and Z. Michalewicz. Particle swarm optimization for single objective continuous space problems: A review. Evolutionary Computation, 25(1):1\u201354, 2017.","key":"2023033119481082869_j_itit-2019-0009_ref_003_w2aab3b7d346b1b6b1ab2ab3Aa","DOI":"10.1162\/EVCO_r_00180"},{"doi-asserted-by":"crossref","unstructured":"M. Clerc. Discrete particle swarm optimization, illustrated by the Traveling Salesman Problem. In New Optimization Techniques in Engineering, chapter 8, pages 219\u2013239, 2004.","key":"2023033119481082869_j_itit-2019-0009_ref_004_w2aab3b7d346b1b6b1ab2ab4Aa","DOI":"10.1007\/978-3-540-39930-8_8"},{"unstructured":"T.\u2009H. Cormen, C.\u2009E. Leiserson, and R.\u2009L. Rivest. Introduction to Algorithms. MIT Press, McGraw-Hill, 1990.","key":"2023033119481082869_j_itit-2019-0009_ref_005_w2aab3b7d346b1b6b1ab2ab5Aa"},{"doi-asserted-by":"crossref","unstructured":"B. Doerr and C. Winzen. Ranking-based black-box complexity. Algorithmica, 68(3):571\u2013609, 2014.","key":"2023033119481082869_j_itit-2019-0009_ref_006_w2aab3b7d346b1b6b1ab2ab6Aa","DOI":"10.1007\/s00453-012-9684-9"},{"doi-asserted-by":"crossref","unstructured":"S. Droste, T. Jansen, and I. Wegener. Upper and lower bounds for randomized search heuristics in black-box optimization. Theory of Computing Systems, 39(4):525\u2013544, 2006.","key":"2023033119481082869_j_itit-2019-0009_ref_007_w2aab3b7d346b1b6b1ab2ab7Aa","DOI":"10.1007\/s00224-004-1177-z"},{"doi-asserted-by":"crossref","unstructured":"E.\u2009F.\u2009G. Goldbarg, G.\u2009R. de Souza, and M.\u2009C. Goldbarg. Particle swarm for the traveling salesman problem. In European Conference on Evolutionary Computation in Combinatorial Optimization, pages 99\u2013110, Springer, 2006.","key":"2023033119481082869_j_itit-2019-0009_ref_008_w2aab3b7d346b1b6b1ab2ab8Aa","DOI":"10.1007\/11730095_9"},{"doi-asserted-by":"crossref","unstructured":"W.\u2009J. Gutjahr. Ant Colony Optimization: Recent Developments in Theoretical Analysis, pages 225\u2013254, 2011.","key":"2023033119481082869_j_itit-2019-0009_ref_009_w2aab3b7d346b1b6b1ab2ab9Aa","DOI":"10.1142\/9789814282673_0008"},{"unstructured":"C.\u2009H. Papadimitriou and K. Steiglitz. Combinatorial Optimization: Algorithms and Complexity. Englewood Cliffs, N.\u2009J.: Prentice Hall, 1982.","key":"2023033119481082869_j_itit-2019-0009_ref_010_w2aab3b7d346b1b6b1ab2ac10Aa"},{"doi-asserted-by":"crossref","unstructured":"M. Held and R.\u2009M. Karp. A dynamic programming approach to sequencing problems. Journal of the Society for Industrial and Applied Mathematics, 10(1):196\u2013210, 1962.","key":"2023033119481082869_j_itit-2019-0009_ref_011_w2aab3b7d346b1b6b1ab2ac11Aa","DOI":"10.1137\/0110015"},{"doi-asserted-by":"crossref","unstructured":"S. Helwig and R. Wanka. Theoretical analysis of initial particle swarm behavior. In Proc. 10th Int. Conf. on Parallel Problem Solving from Nature (PPSN), pages 889\u2013898, 2008.","key":"2023033119481082869_j_itit-2019-0009_ref_012_w2aab3b7d346b1b6b1ab2ac12Aa","DOI":"10.1007\/978-3-540-87700-4_88"},{"doi-asserted-by":"crossref","unstructured":"M. Hoffmann, M. M\u00fchlenthaler, S. Helwig, and R. Wanka. Discrete particle swarm optimization for TSP: Theoretical results and experimental evaluations. In Proc. 2nd Int. Conf. on Adaptive and Intelligent Systems (ICAIS), pages 416\u2013427, 2011.","key":"2023033119481082869_j_itit-2019-0009_ref_013_w2aab3b7d346b1b6b1ab2ac13Aa","DOI":"10.1007\/978-3-642-23857-4_40"},{"unstructured":"J. Kennedy and R.\u2009C. Eberhart. Particle swarm optimization. In Proc. IEEE International Conference on Neural Networks, volume 4, pages 1942\u20131948, 1995.","key":"2023033119481082869_j_itit-2019-0009_ref_014_w2aab3b7d346b1b6b1ab2ac14Aa"},{"unstructured":"J. Kennedy and R.\u2009C. Eberhart. A discrete binary version of the particle swarm algorithm. In Proc. IEEE Int. Conf. on Systems, Man, and Cybernetics, volume 5, pages 4104\u20134108, 1997.","key":"2023033119481082869_j_itit-2019-0009_ref_015_w2aab3b7d346b1b6b1ab2ac15Aa"},{"doi-asserted-by":"crossref","unstructured":"P.\u2009K. Lehre and C. Witt. Black-box search by unbiased variation. Algorithmica, 64(4):623\u2013642, 2012.","key":"2023033119481082869_j_itit-2019-0009_ref_016_w2aab3b7d346b1b6b1ab2ac16Aa","DOI":"10.1007\/s00453-012-9616-8"},{"doi-asserted-by":"crossref","unstructured":"M. M\u00fchlenthaler, A. Ra\u00df, M. Schmitt, A. Siegling, and R. Wanka. 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), pages 13\u201324, 2017.","key":"2023033119481082869_j_itit-2019-0009_ref_017_w2aab3b7d346b1b6b1ab2ac17Aa","DOI":"10.1145\/3040718.3040721"},{"unstructured":"M. M\u00fchlenthaler, A. Ra\u00df, M. Schmitt, and R. Wanka. Exact Markov chain-based runtime analysis of a discrete particle swarm optimization algorithm on Sorting and OneMax. arXiv:1902.01810, 2019. Extended version of [17].","key":"2023033119481082869_j_itit-2019-0009_ref_018_w2aab3b7d346b1b6b1ab2ac18Aa"},{"doi-asserted-by":"crossref","unstructured":"A. Ra\u00df, J. Schreiner, and R. Wanka. Runtime analysis of discrete particle swarm optimization applied to shortest paths computation. In Proc. 19th Evolutionary Computation in Combinatorial Optimization (EvoCOP), Springer International Publishing, 2019.","key":"2023033119481082869_j_itit-2019-0009_ref_019_w2aab3b7d346b1b6b1ab2ac19Aa","DOI":"10.1007\/978-3-030-16711-0_8"},{"doi-asserted-by":"crossref","unstructured":"A. Rezaee Jordehi and J. Jasni. Particle swarm optimisation for discrete optimisation problems: a review. Artificial Intelligence Review, 43(2):243\u2013258, Feb. 2015.","key":"2023033119481082869_j_itit-2019-0009_ref_020_w2aab3b7d346b1b6b1ab2ac20Aa","DOI":"10.1007\/s10462-012-9373-8"},{"doi-asserted-by":"crossref","unstructured":"J. Scharnow, K. Tinnefeld, and I. Wegener. The analysis of evolutionary algorithms on sorting and shortest paths problems. Journal of Mathematical Modelling and Algorithms, 3(4):349\u2013366, 2004.","key":"2023033119481082869_j_itit-2019-0009_ref_021_w2aab3b7d346b1b6b1ab2ac21Aa","DOI":"10.1023\/B:JMMA.0000049379.14872.f5"},{"doi-asserted-by":"crossref","unstructured":"M. Schmitt and R. Wanka. Particle swarm optimization almost surely finds local optima. Theor. Comput. Sci., 561(PA):57\u201372, 2015.","key":"2023033119481082869_j_itit-2019-0009_ref_022_w2aab3b7d346b1b6b1ab2ac22Aa","DOI":"10.1016\/j.tcs.2014.05.017"},{"doi-asserted-by":"crossref","unstructured":"X.\u2009H. Shi, Y.\u2009C. Liang, H.\u2009P. Leeb, C. Lu, and Q.\u2009X. Wang. Particle swarm optimization-based algorithms for TSP and generalized TSP. Information Processing Letters, (103):169\u2013176, 2007.","key":"2023033119481082869_j_itit-2019-0009_ref_023_w2aab3b7d346b1b6b1ab2ac23Aa","DOI":"10.1016\/j.ipl.2007.03.010"},{"doi-asserted-by":"crossref","unstructured":"D. Sudholt and C. Witt. Runtime analysis of a binary particle swarm optimizer. Theoretical Computer Science, 411(21):2084\u20132100, 2010.","key":"2023033119481082869_j_itit-2019-0009_ref_024_w2aab3b7d346b1b6b1ab2ac24Aa","DOI":"10.1016\/j.tcs.2010.03.002"},{"unstructured":"K.-P. Wang, L. Huang, C.-G. Zhou, and W. Pang. Particle swarm optimization for traveling salesman problem. In Machine Learning and Cybernetics, 2003 International Conference on, volume 3, pages 1583\u20131585, IEEE, 2003.","key":"2023033119481082869_j_itit-2019-0009_ref_025_w2aab3b7d346b1b6b1ab2ac25Aa"},{"doi-asserted-by":"crossref","unstructured":"I. Wegener. Methods for the analysis of evolutionary algorithms on pseudo-boolean functions. In R. Sarker, M. Mohammadian, and X. Yao, editors, Evolutionary Optimization, chapter 14, pages 349\u2013369, Springer, 2002.","key":"2023033119481082869_j_itit-2019-0009_ref_026_w2aab3b7d346b1b6b1ab2ac26Aa","DOI":"10.1007\/0-306-48041-7_14"}],"container-title":["it - Information Technology"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/www.degruyter.com\/view\/j\/itit.2019.61.issue-4\/itit-2019-0009\/itit-2019-0009.xml","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/www.degruyter.com\/document\/doi\/10.1515\/itit-2019-0009\/xml","content-type":"application\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/www.degruyter.com\/document\/doi\/10.1515\/itit-2019-0009\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,4,1]],"date-time":"2023-04-01T07:45:51Z","timestamp":1680335151000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.degruyter.com\/document\/doi\/10.1515\/itit-2019-0009\/html"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,8,1]]},"references-count":26,"journal-issue":{"issue":"4","published-online":{"date-parts":[[2019,10,30]]},"published-print":{"date-parts":[[2019,8,27]]}},"alternative-id":["10.1515\/itit-2019-0009"],"URL":"https:\/\/doi.org\/10.1515\/itit-2019-0009","relation":{},"ISSN":["2196-7032","1611-2776"],"issn-type":[{"type":"electronic","value":"2196-7032"},{"type":"print","value":"1611-2776"}],"subject":[],"published":{"date-parts":[[2019,8,1]]}}}