why standard particle swarm optimisers elude a theoretical runtime analysis
A recent trend in the theoretical analysis of randomised search heuristics deals with their optimisation time, also called runtime, for selected problems. Such results exist for several bio-inspired search heuristics including Evolutionary Algorithms and Ant Colony Optimisation but not for standard Particle Swarm Optimisers (PSO). This paper points out why a runtime analysis of standard PSO algorithms and many proposed variants does not make sense and why existing convergence analyses thereof do not contribute to our understanding of the success of PSO as observed in practice either. As one of the few PSO variants that allow for a rigorous runtime analysis, the Guaranteed Convergence PSO (GCPSO) by van den Bergh and Engelbrecht is studied in the case of a single particle, and a theorem showing theoretically optimal convergence speed on a test function is derived. In the course of our paper, it is elaborated why a runtime analysis of PSO, when possible, is seemingly closely related to the analysis of simple Evolutionary Algorithms.
particle swarm optimisation runtime analysis