Runtime analysis of discrete particle swarm optimization applied to shortest paths computation. (English) Zbl 1525.68213
Liefooghe, Arnaud (ed.) et al., Evolutionary computation in combinatorial optimization. 19th European conference, EvoCOP 2019, held as part of EvoStar 2019, Leipzig, Germany, April 24–26, 2019. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 11452, 115-130 (2019).
Summary: We mathematically analyze a discrete particle swarm optimization (PSO) algorithm solving the single-source shortest path (SSSP) problem. Key features are an improved and extended study on Markov chains expanding the adaptability of this technique and its application on the well-known SSSP problem. The results are upper and lower bounds on the expected optimization time. For upper bounds, we combine return times within a Markov model with the well known fitness level method which is appropriate even for the non-elitist PSO algorithm. For lower bounds we prove that the recently introduced property of indistinguishability applies in this setting and we also combine it with a further Markov chain analysis. We prove a cubic upper and a quadratic lower bound and an exponential upper and lower bound on the expected runtime, respectively, depending on a PSO parameter.
For the entire collection see [Zbl 1408.68021].
For the entire collection see [Zbl 1408.68021].
MSC:
| 68W50 | Evolutionary algorithms, genetic algorithms (computational aspects) |
| 60J20 | Applications of Markov chains and discrete-time Markov processes on general state spaces (social mobility, learning theory, industrial processes, etc.) |
| 68W40 | Analysis of algorithms |
| 90C35 | Programming involving graphs or networks |
| 90C59 | Approximation methods and heuristics in mathematical programming |
Keywords:
discrete particle-swarm optimization; runtime analysis; single-source shortest paths; Markov chainsReferences:
| [1] | Scharnow, J.; Tinnefeld, K.; Wegener, I., The analysis of evolutionary algorithms on sorting and shortest paths problems, J. Math. Model. Algorithms, 3, 4, 349-366 (2004) · Zbl 1073.68080 · doi:10.1023/B:JMMA.0000049379.14872.f5 |
| [2] | Doerr, B.; Happ, E.; Klein, C., Tight analysis of the (1+1)-EA for the single source shortest path problem, Evol. Comput., 19, 4, 673-691 (2011) · doi:10.1162/EVCO\_a_00047 |
| [3] | Neumann, F.; Witt, C., Runtime analysis of a simple ant colony optimization algorithm, Algorithmica, 54, 2, 243-255 (2007) · Zbl 1190.68049 · doi:10.1007/s00453-007-9134-2 |
| [4] | Doerr, B., Neumann, F., Sudholt, D., Witt, C.: On the runtime analysis of the 1-ANT ACO algorithm. In: Proceedings of the 9th ACM Genetic and Evolutionary Computation Conference (GECCO), pp. 33-40 (2007). doi:10.1145/1276958.1276964 |
| [5] | Eberhart, R.C., Kennedy, J.: A new optimizer using particle swarm theory. In: Proceedings of the 6th International Symposium on Micro Machine and Human Science, pp. 39-43 (1995). doi:10.1109/MHS.1995.494215 |
| [6] | Kennedy, J., Eberhart, R.C.: Particle swarm optimization. In: Proceedings of the IEEE International Conference on Neural Networks, vol. 4, pp. 1942-1948 (1995). doi:10.1109/ICNN.1995.488968 |
| [7] | Schmitt, M.; Wanka, R., Particle swarm optimization almost surely finds local optima, Theoret. Comput. Sci., 561A, 57-72 (2015) · Zbl 1303.68125 · doi:10.1016/j.tcs.2014.05.017 |
| [8] | Sudholt, D.; Witt, C., Runtime analysis of a binary particle swarm optimizer, Theoret. Comput. Sci., 411, 21, 2084-2100 (2010) · Zbl 1190.90292 · doi:10.1016/j.tcs.2010.03.002 |
| [9] | Clerc, M.: Discrete particle swarm optimization, illustrated by the traveling salesman problem. In: New Optimization Techniques in Engineering, vol. 141, pp. 219-239. Springer, Heidelberg (2004). doi:10.1007/978-3-540-39930-8_8 · Zbl 1139.90415 |
| [10] | Hoffmann, M.; Mühlenthaler, M.; Helwig, S.; Wanka, R.; Bouchachia, A., Discrete particle swarm optimization for TSP: theoretical results and experimental evaluations, Adaptive and Intelligent Systems, 416-427 (2011), Heidelberg: Springer, Heidelberg · doi:10.1007/978-3-642-23857-4_40 |
| [11] | Mühlenthaler, M., Raß, A., Schmitt, M., Siegling, A., Wanka, R.: Runtime analysis of a discrete particle swarm optimization algorithm on sorting and OneMax. In: Proceedings of the 14th ACM/SIGEVO Workshop on Foundations of Genetic Algorithms (FOGA), pp. 13-24 (2017). doi:10.1145/3040718.3040721 · Zbl 1365.68394 |
| [12] | Sudholt, D.; Thyssen, C., Running time analysis of ant colony optimization for shortest path problems, J. Discrete Algorithms, 10, 165-180 (2012) · Zbl 1250.68238 · doi:10.1016/j.jda.2011.06.002 |
| [13] | Cormen, TH; Leiserson, CE; Rivest, RL, Introduction to Algorithms (1990), Cambridge: MIT Press, McGraw-Hill, Cambridge · Zbl 1158.68538 |
| [14] | Baswana, S., Biswas, S., Doerr, B., Friedrich, T., Kurur, P.P., Neumann, F.: Computing single source shortest paths using single-objective fitness. In: Proceedings of the 10th ACM/SIGEVO Workshop on Foundations of Genetic Algorithms (FOGA), pp. 59-66 (2009). doi:10.1145/1527125.1527134 · Zbl 1369.68296 |
| [15] | Wegener, I.; Sarker, R., Methods for the analysis of evolutionary algorithms on pseudo-Boolean functions, Evolutionary Optimization, 349-369 (2002), Boston: Springer, Boston · doi:10.1007/0-306-48041-7_14 |
| [16] | Droste, S., Jansen, T., Wegener, I.: Dynamic parameter control in simple evolutionary algorithms. In: Proceedings of the 6th ACM/SIGEVO Workshop on Foundations of Genetic Algorithms (FOGA), pp. 275-294 (2001). doi:10.1016/B978-155860734-7/50098-6 · Zbl 0987.68098 |
| [17] | Mühlenthaler, M., Raß, A., Schmitt, M., Wanka, R.: Exact Markov chain-based runtime analysis of a discrete particle swarm optimization algorithm on sorting and OneMax (2019). https://arxiv.org/abs/1902.01810, extended version of [11] · Zbl 1365.68394 |
| [18] | Gillespie, JH, Some properties of finite populations experiencing strong selection and weak mutation, Am. Nat., 121, 5, 691-708 (1983) · doi:10.1086/284095 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
