CISC-499 Project

On Resolving the Premature Convergence Problem of PSO

Supervisors: Hazem R. Ahmed and Janice Glasgow

Particle Swarm Optimization (PSO) is inspired by the intelligent, experience-sharing, social behaviour of birds flocking. It is a population-based search strategy first introduced by Russell Eberhart, an electrical engineer, and James Kennedy, a social psychologist, in 1995 to find optimal/near-optimal solutions using a set of flying particles. Each particle represents a potential solution, which is a point in a multidimensional search space. The particle has a fitness value and a velocity to adjust its flying direction in accordance to the best experience of the swarm and itself in order to search for a global optimum.

PSO has become popular in the research field of optimization over the last decade for its simplicity of concept and implementation, few parameters and high convergence rate. However the standard versions of PSO tend to suffer from premature convergence by easily getting trapped into a local optimum (one of the most common problems of optimization techniques), especially when solving complex multimodal problems. This is due to a decrease of diversity in search space, which is often irreversible in the standard versions of PSO, and eventually leads to fitness stagnation of the swarm.

Several attempts have been made in literature to recover the swarm from stagnation situation using different strategies. For example, as G. Evers and M. Ghalia summarized in their paper [1], once the swarm has prematurely converged, one or more of the following options could be applied: (i) Allow the search to continue and hope that the swarm will slowly refine the quality of the proposed solution, though it is likely only an approximation of a local optima rather than the desired global optima. (ii) Restart the swarm from new locations (i.e. start from scratch) and search again to see if a better solution can be found. (iii) Somehow flag regions of the space to which particles have prematurely converged as already explored and restart the algorithm so that each successive search is more likely to encounter the global optima. (iv) Reinvigorate the swarm by introducing diversity so the search can continue more or less from the current location without having to restart and re-search low quality regions of the search space.

The project objective is to review the aforementioned options, and show what the best option (or combination of options) would be on resolving the premature convergence/stagnation problem of the standard PSO.

[1] G.I. Evers and M.B. Ghalia, "Regrouping Particle Swarm Optimization: A New Global Optimization Algorithm with Improved Performance Consistency Across Benchmarks", in International Conference on Systems, Man, and Cybernetics 2009, San Antonio, TX, USA, 2009, pp.3901-3908.