Convergence Analysis for Particle Swarm Optimization - Schmitt, Manuel (Friedrich-Alexander-Universität Erlangen-Nürnberg, 2015)

Exact Markov chain-based runtime analysis of a discrete particle swarm optimization algorithm on sorting and OneMax - Mühlenthaler, Moritz; Raß, Alexander; Schmitt, Manuel; Wanka, Rolf (Natural Computing, 2021)
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 particle swarm optimization (PSO) paradigm. We provide a comprehensive formal analysis of the performance of this algorithm on certain “easy” reference problems in a black-box setting, namely the sorting problem and the problem OneMax. 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 indistinguishability of states of a Markov chain and provide bounds on the solution of a recurrence equation with non-constant coefficients by integration. <br

Explanation of Stagnation at Points that are not Local Optima in Particle Swarm Optimization by Potential Analysis - Raß, Alexander; Schmitt, Manuel; Wanka, Rolf (Companion of Proc. 17th Genetic and Evolutionary Computation Conference (GECCO), 2015)
This paper investigates the frequently observed phenomenon of stagnation which appears on particle swarm optimization (PSO). We introduce a measure of significance of single dimensions and provide experimental and theoretical evidence that the classical PSO, even with swarm parameters known (from the literature) to be good, almost surely does not converge to a local optimum (stagnation) if too few particles are used. Stagnation is an undesirable property of PSO.
Keywords: Particle swarm optimization; stagnation; potential

Explanation of Stagnation at Points that are not Local Optima in Particle Swarm Optimization by Potential Analysis [Extended Version] - Raß, Alexander; Schmitt, Manuel; Wanka, Rolf (2015)
Particle Swarm Optimization (PSO) is a nature-inspired meta-heuristic for solving continuous optimization problems. In the literature, the potential of the particles of swarm has been used to show that slightly modified PSO guarantees convergence to local optima. Here we show that under specific circumstances the unmodified PSO, even with swarm parameters known (from the literature) to be good, almost surely does not yield convergence to a local optimum is provided. This undesirable phenomenon is called stagnation. For this purpose, the particles' potential in each dimension is analyzed mathematically. Additionally, some reasonable assumptions on the behavior if the particles' potential are made. Depending on the objective function and, interestingly, the number of particles, the potential in some dimensions may decrease much faster than in other dimensions. Therefore, these dimensions lose relevance, i.e., the contribution of their entries to the decisions about attractor updates becomes insignificant and, with positive probability, they never regain relevance. If Brownian Motion is assumed to be an approximation of the time-dependent drop of potential, practical, i.e., large values for this probability are calculated. Finally, on chosen multidimensional polynomials of degree two, experiments are provided showing that the required circumstances occur quite frequently. Furthermore, experiments are provided showing that even when the very simple sphere function is processed the described stagnation phenomenon occurs. Consequently, unmodified PSO does not converge to any local optimum of the chosen functions for tested parameter settings.
Keywords: Particle swarm optimization; stagnation; potential

Exploiting Independent Subformulas: A Faster Approximation Scheme for #k-SAT - Schmitt, Manuel; Wanka, Rolf (Information Processing Letters, 2013)
We present an improvement on Thurley's recent randomized approximation scheme for #k-SAT where the task is to count the number of satisfying truth assignments of a Boolean function Φ given as an n-variable k-CNF. We introduce a novel way to identify independent substructures of Φ and can therefore reduce the size of the search space considerably. Our randomized algorithm works for any k. For #3-SAT, it runs in time O(ε- 2×1.51426n), for #4-SAT, it runs in time O(ε-2×1.60816n), with error bound ε. © 2013 Elsevier B.V. All rights reserved.
UnivIS-Import:2015-03-09:Pub.2013.tech.IMMD.infalg._explo_5
Keywords: #k-SAT; Algorithms; Analysis of algorithms; Randomized algorithms; Satisfiability

How Much Forcing is Necessary to Let the Results of Particle Swarms Converge? - Bassimir, Bernd; Schmitt, Manuel; Wanka, Rolf (Proc. Int. Conf. on Swarm Intelligence Based Optimization (ICSIBO), 2014)
In order to improve the behavior of Particle Swarm Optimization (PSO), the classical method is often extended by additional operations. Here, we are interested in how much ``PSO" remains in this case, and how often the extension takes over the computation. We study the variant of PSO that applies random velocities (then called forced moves) as soon as the so-called potential of the swarm falls below a certain bound. We show experimentally that the number of iterations the swarm actually deviates from the classical PSO behavior is small as long as the particles are sufficiently far away from any local optimum. As soon as the swarm comes close to a local optimum, the number of forced moves increases significantly and approaches a value that depends on the swarm size and the problem dimension, but not on the actual fitness function, an observation that can be used as a stopping criterion. Additionally, we provide an explanation for the observed phenomenon in terms of the swarms potential.

Multimodal Medical Image Registration Using Particle Swarm Optimization with Influence of the Data's Initial Orientation - Schmitt, Manuel; Wanka, Rolf; Schwab, Lydia (Proc. 12th IEEE Conf. on Computational Intelligence in Bioinformatics and Computational Biology (CIBCB), 2015)
UnivIS-Import:2015-10-26:Pub.2015.tech.IMMD.infalg._multi

Particles Prefer Walking Along the Axes: Experimental Insights into the Behavior of a Particle Swarm - Schmitt, Manuel; Wanka, Rolf (Companion of Proc. 15th Genetic and Evolutionary Computation Conference, 2013)
We study the frequently observed phenomenon of stagna- tion in the context of particle swarm optimization (PSO). We show that in certain situations the particle swarm is likely to move almost parallel to one of the axes, which may cause stagnation. We provide an experimentally supported explanation in terms of a potential of the swarm and are therefore able to adapt the PSO algorithm slightly such that this weakness can be avoided.
UnivIS-Import:2015-04-16:Pub.2013.tech.IMMD.infalg._parti_9
Keywords: Particle swarm optimization; Potential; Stagnation

Particle Swarm Optimization Almost Surely Finds Local Optima - Schmitt, Manuel; Wanka, Rolf (Proc. 15th Genetic and Evolutionary Computation Conference, 2013)
Particle swarm optimization (PSO) is a popular nature-inspired meta-heuristic for solving continuous optimization problems. Although this technique is widely used, up to now only some partial aspects of the method have been formally investigated. In particular, while it is well-studied how to let the swarm converge to a single point in the search space, no general theoretical statements about this point or on the best position any particle has found have been known. For a very general class of objective functions, we provide for the first time results about the quality of the solution found. We show that a slightly adapted PSO almost surely finds a local optimum. To do so, we investigate the newly defined . potential of the swarm. The potential drops when the swarm approaches the point of convergence, but increases if the swarm remains close to a point that is not a local optimum, meaning that the swarm charges potential and continues its movement.
UnivIS-Import:2015-04-16:Pub.2013.tech.IMMD.infalg._parti
Keywords: Fitness landscapes; Particle swarm optimization; Quality of solution

Particle Swarm Optimization Almost Surely Finds Local Optima - Schmitt, Manuel; Wanka, Rolf (Theoretical Computer Science, 2015)
UnivIS-Import:2015-03-11:Pub.2015.tech.IMMD.infalg._parti

Runtime Analysis of a Discrete Particle Swarm Optimization Algorithm on Sorting and OneMax - Mühlenthaler, Moritz; Raß, Alexander; Schmitt, Manuel; Siegling, Andreas; Wanka, Rolf (Proceedings of the 14th ACM/SIGEVO Conference on Foundations of Genetic Algorithms, 2017)
We present the analysis of a discrete particle swarm optimization (PSO) algorithm that works on a significantly large class of discrete optimization problems. Assuming a black-box setting, we prove upper and lower bounds on the expected number of function evaluations required by the proposed algorithm to solve the sorting problem and the problem of maximizing the number of ones in a bitstring, i.e., the function OneMax. We show that depending on the probability of moving towards the attractor, the expected optimization time may be polynomial or exponential. The cornerstone of our analysis are Theta-bounds on the expected time it takes until the PSO returns to the attractor. We obtain these bounds by solving linear recurrence equations with constant and non-constant coefficients. We also introduce a useful indistinguishability property of states of a Markov chain in order to obtain lower bounds on the expected optimization time of our proposed PSO algorithm.
Keywords: Particle Swarm Optimization; Discrete Optimization; Run-time Analysis; Markov Chains

Self-adaptive potential-based stopping criteria for Particle Swarm Optimization with forced moves - Bassimir, Bernd; Schmitt, Manuel; Wanka, Rolf (Swarm Intelligence, 2020)
We study the variant of Particle Swarm Optimization that applies random velocities in a dimension instead of the regular velocity update equations as soon as the so-called potential of the swarm falls below a certain small bound in this dimension, arbitrarily set by the user. In this case, the swarm performs a forced move. In this paper, we are interested in how, by counting the forced moves, the swarm can decide for itself to stop its movement because it is improbable to find better candidate solutions than the already-found best solution. We formally prove that when the swarm is close to a (local) optimum, it behaves like a blind-searching cloud and that the frequency of forced moves exceeds a certain, objective function-independent value. Based on this observation, we define stopping criteria and evaluate them experimentally showing that good candidate solutions can be found much faster than setting upper bounds on the iterations and better solutions compared to applying other solutions from the literature.<br
Keywords: Particle Swarm Optimization; Stopping criterion; Heuristics

Theory of particle swarm optimization: A survey of the power of the swarm’s potential - Bassimir, Bernd; Raß, Alexander; Schmitt, Manuel (it - Information Technology, 2019)
This paper presents a survey on different showcases for potential measures on particle swarm optimization (PSO). First, a potential is analyzed to prove convergence to non-optimal points. Second, one can apply a minor modification to PSO to prevent convergence to non-optimal points by using an easy potential measure. Finally, analyzing this potential measure yields a reliable stopping criterion for the modified PS
Keywords: Particle swarm optimization; potential; meta-heuristics

Towards a Better Understanding of the Local Attractor in Particle Swarm Optimization: Speed and Solution Quality - Lange, Vanessa; Schmitt, Manuel; Wanka, Rolf (Proc. International Conference on Adaptive and Intelligent Systems (ICAIS), 2014)
Particle Swarm Optimization (PSO) is a popular nature-inspired meta-heuristic for solving continuous optimization problems. Although this technique is widely used, the understanding of the mechanisms that make swarms so successful is still limited. We present the first substantial experimental investigation of the influence of the local attractor on the quality of exploration and exploitation. We compare in detail classical PSO with the social-only variant where local attractors are ignored. To measure the exploration capabilities, we determine how frequently both variants return results in the neighborhood of the global optimum. We measure the quality of exploitation by considering only function values from runs that reached a search point sufficiently close to the global optimum and then comparing in how many digits such values still deviate from the global minimum value. It turns out that the local attractor significantly improves the exploration, but sometimes reduces the quality of the exploitation. The effects mentioned can also be observed by measuring the potential of the swarm. © 2014 Springer International Publishing Switzerland.
UnivIS-Import:2015-04-16:Pub.2014.tech.IMMD.infalg._towar