Convergence Analysis and Numerical Simulation of Particle Swarm Optimization

Abstract

Nature, including mankind, loves to optimize and the world is far from being deterministic. Thus, stochastic optimization is an important and active area of research in applied mathematics. Inspired by the social behavior of bird flocking or fish schooling, particle swarm optimization (PSO) is a population based stochastic optimization method developed by Eberhart and Kennedy in 1995. It has been used across a wide range of applications. Uniform random numbers are used to initialize the particles in the PSO algorithm. In literature, Faure, Halton and Van der Corput sequences have been used for initializing the swarm in PSO. Quasi-random (or low-discrepancy) sequences such as Faure, Halton, Van der Corput, etc, are deterministic and suffer from correlations between radical inverse functions with different bases used for different dimensions. These correlations results in poorly distributed 2D projections. A standard solution to these is to use randomized versions of the quasi-random sequences. In this dissertation, we investigate the effect of initializing the swarm with the optimal Halton sequence, which is a randomized quasi-random sequence. This ensures that we still have the uniformity properties of quasi-random sequences while preserving the stochastic behavior for particles in the swarm.

The central part of this dissertation is the convergence analysis of PSO. Though there have been several studies on the convergence of PSO, the convergence proofs in these studies are either imprecise or based on unrealistic assumptions and, to the best of our knowledge, incomplete. Here, we present almost surely convergence analysis of PSO, based on the properties of the objective function.

The last part of this dissertation is about numerical experiments based on quasi Monte Carlo sampling algorithms. Numerical experiments are conducted with benchmark objective functions in high dimensions (starting from two dimensions and then in 10, 20, 30, 50, 70 and 100 dimensions) to verify the convergence and effectiveness of the proposed initialization of PSO.