A Serendipity-Based Approach to Enhance Particle Swarm Optimization Using Scout Particles
Fábio Paiva, José Alfredo Ferreira Costa, C.R.M. Silva · IEEE Latin America Transactions · 2017
In metaheuristic algorithms, such as Particle Swarm Optimization (PSO) and Genetic Algorithm (GA), it is common to deal with a problem known as premature convergence. It happens when a swarm loses diversity and starts converging too early towards a suboptimal solution for an optimization problem. There have been many approaches to this problem along to the latest two decades, but it is a understanding that the problem is still open. This work proposes a new approach based on a concept normally applied in the Recommender Systems context (serendipity-based approach). The paper presents a formalization for the concepts of serendipity and premature convergence, as well a Serendipity-Based PSO (SBPSO) algorithm prototype which implements the concept of serendipity by means of two dimensions: chance and sagacity. The algorithm was compared with the traditional PSO and some PSO variants. The results were successful and showed that SBPSO outperformed the traditional PSO. The experiments also compared SBPSO with some studies in the literature, considering a set of hard functions (such as Rosenbrock, HappyCat, etc) and a fixed number of particles and varying the problem dimensionality and the number of iterations. In all experiments, SBPSO also showed a better convergence behavior, outperforming the traditional PSO and some variants available in the literature regarding the solution quality, the ability to find global optimum, the solutions stability and the ability to restart the movement of the swarm in case of stagnation has been detected.