An Analysis of particle swarm optimizers

by Van den Bergh, Frans.

Many scientific, engineering and economic problems involve the optimisation of a set of parameters. These problems include examples like minimising the losses in a power grid by finding the optimal configuration of the components, or training a neural network to recognise images of people’s faces. Numerous optimisation algorithms have been proposed to solve these problems, with varying degrees of success. The Particle Swarm Optimiser (PSO) is a relatively new technique that has been empirically shown to perform well on many of these optimisation problems. This thesis presents a theoretical model that can be used to describe the long-term behaviour of the algorithm. An enhanced version of the Particle Swarm Optimiser is constructed and shown to have guaranteed convergence on local minima. This algorithm is extended further, resulting in an algorithm with guaranteed convergence on global minima. A model for constructing cooperative PSO algorithms is developed, resulting in the introduction of two new PSO-based algorithms. Empirical results are presented to support the theoretical properties predicted by the various models, using synthetic benchmark functions to investigate specific properties. The various PSO-based algorithms are then applied to the task of training neural networks, corroborating the results obtained on the synthetic benchmark functions. Thesis supervisor: Prof. A. P. Engelbrecht Department of Computer Science Degree: Philosophiae Doctor University of Pretoria etd – Van den Bergh, F (2006) An Analysis of Particle Swarm Optimizers deur Frans van den Bergh Opsomming Talle wetenskaplike, ingenieurs en ekonomiese probleme behels die optimering van ’n aantal parameters. Hierdie probleme sluit byvoorbeeld in die minimering van verliese in ’n kragnetwerk deur die optimale konfigurasie van die komponente te bepaal, of om neurale netwerke af te rig om mense se gesigte te herken. ’n Menigte optimeringsalgoritmes is al voorgestel om hierdie probleme op te los, soms met gemengde resultate. Die Partikel Swerm Optimeerder (PSO) is ’n relatief nuwe tegniek wat verskeie van hierdie optimeringsprobleme suksesvol opgelos het, met empiriese resultate ter ondersteuning. Hierdie tesis stel bekend ’n teoretiese model wat gebruik kan word om die langtermyn gedrag van die PSO algoritme te beskryf. ’n Verbeterde PSO algoritme, met gewaarborgde konvergensie na lokale minima, word aangebied met die hulp van dié teoretiese model. Hierdie algoritme word dan verder uitgebrei om globale minima te kan opspoor, weereens met ’n teoreties-bewysbare waarborg. ’n Model word voorgestel waarmee koöperatiewe PSO algoritmes ontwikkel kan word, wat gevolglik gebruik word om twee nuwe PSO-gebaseerde algoritmes mee te ontwerp. Empiriese resultate word aangebied om die teoretiese kenmerke, soos voorspel deur die teoretiese model, toe te lig. Kunsmatige toetsfunksies word gebruik om spesifieke eienskappe van die verskeie algoritmes te ondersoek. Die verskeie PSO-gebaseerde algoritmes word dan gebruik om neurale netwerke mee af te rig, as ’n kontrole vir die empiriese resultate wat met die kunsmatige funksies bekom is. Tesis studieleier: Prof. A. P. Engelbrecht Departement Rekenaarwetenskap Graad: Philosophiae Doctor University of Pretoria etd – Van den Bergh, F (2006)