Efficient Computation of Probabilistic Dominance in Multi-objective Optimization - Khosravi, Faramarz; Raß, Alexander; Teich, Jürgen (ACM Transactions on Evolutionary Learning and Optimization, 2021)

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

High Precision Particle Swarm Optimization Algorithm (HiPPSO) - Raß, Alexander (Journal of Open Research Software, 2020)
Particle Swarm Optimization (PSO) is a nature-inspired meta-heuristic adaptable to continuous optimization problems. To avoid numerical instabilities or artifacts it is necessary to evaluate floating point calculations with high precision. Our High Precision Particle Swarm Optimization (HiPPSO) software realizes this demand. Additionally our software provides an automatic procedure to adjust precision if it is necessary for accurate evaluations. This enables a fast execution time because the software always evaluates the calculations with suitable precision and does not use too much precision if it is not necessary. HiPPSO is implemented in C++ and has a very flexible class hierarchy to replace subroutines on purpose or extend functionality by simply implementing abstract classes. The software is available on a GitHub repository at https://github.com/alexander-rass/HiPPSO</a
Keywords: particle swarm optimization; arbitrary precision; convergence analysis

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

Runtime analysis of discrete particle swarm optimization algorithms: A survey - Mühlenthaler, Moritz; Raß, Alexander (it - Information Technology, 2019)
A discrete particle swarm optimization (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 bound
Keywords: randomized search heuristics; particle swarm optimization; runtime analysis

Runtime Analysis of Discrete Particle Swarm Optimization Applied to Shortest Paths Computation - Raß, Alexander; Schreiner, Jonas; Wanka, Rolf (Evolutionary Computation in Combinatorial Optimization, 2019)
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 ubiquitous 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.
Keywords: Discrete Particle Swarm Optimization; Runtime Analysis; Single-Source Shortest Paths; Markov Chains

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