Stochastic approximation driven particle swarm optimization with simultaneous perturbation - Who will guide the guide?

Abstract

The need for solving multi-modal optimization problems in high dimensions is pervasive in many practical applications. Particle swarm optimization (PSO) is attracting an ever-growing attention and more than ever it has found many application areas for many challenging optimization problems. It is, however, a known fact that PSO has a severe drawback in the update of its global best (gbest) particle, which has a crucial role of guiding the rest of the swarm. In this paper, we propose two efficient solutions to remedy this problem using a stochastic approximation (SA) technique. In the first approach, gbest is updated (moved) with respect to a global estimation of the gradient of the underlying (error) surface or function and hence can avoid getting trapped into a local optimum. The second approach is based on the formation of an alternative or artificial global best particle, the so-called aGB, which can replace the native gbest particle for a better guidance, the decision of which is held by a fair competition between the two. For this purpose we use simultaneous perturbation stochastic approximation (SPSA) for its low cost. Since SPSA is applied only to the gbest (not to the entire swarm), both approaches result thus in a negligible overhead cost for the entire PSO process. Both approaches are shown to significantly improve the performance of PSO over a wide range of non-linear functions, especially if SPSA parameters are well selected to fit the problem at hand. A major finding of the paper is that even if the SPSA parameters are not tuned well, results of SA-driven (SAD) PSO are still better than the best of PSO and SPSA. Since the problem of poor gbest update persists in the recently proposed extension of PSO, called multi-dimensional PSO (MD-PSO), both approaches are also integrated into MD-PSO and tested over a set of unsupervised data clustering applications. As in the basic PSO application, experimental results show that the proposed approaches significantly improved the quality of the MD-PSO clustering as measured by a validity index function. Furthermore, the proposed approaches are generic as they can be used with other PSO variants and applicable to a wide range of problems. (C) 2010 Elsevier B.V. All rights reserved.