Analysis of the particle swarm optimization algorithm

Abstract

Increasing prominence is given to the role of optimization in engineering. The global optimization problem is in particular frequently studied, since this difficult optimization problem is in general intractable. As a result, many a solution technique have been proposed for the global optimization problem, e.g. random searches, evolutionary computation algorithms, taboo searches, fractional programming, etc. This study is concerned with the recently proposed zero-order evolutionary computation algorithm known as the particle swarm optimization algorithm (PSOA). The following issues are addressed: 1. It is remarked that implementation subtleties due to ambiguous notation have resulted in two distinctly different implementations of the PSOA. While the behavior of the respective implementations is markedly different, they only differ in the formulation of the velocity updating rule. In this thesis, these two implementations are denoted by PSOAF1 and PSOAF2 respectively. 2. It is shown that PSOAF1 is observer independent, but the particle search trajectories collapse to line searches in n-dimensional space. In turn, for PSOAF2 it is shown that the particle trajectories are space filling in n-dimensional space, but this implementation suffers from observer dependence. It is also shown that some popular heuristics are possibly of less importance than originally thought; their greatest contribution is to prevent the collapse of particle trajectories to line searches. 3. A novel PSOA formulation, denoted PSOAF1* is then introduced, in which the particle trajectories do not collapse to line searches, while observer independence is preserved. However, the observer independence is only satisfied in a stochastic sense, i.e. the mean objective function value over a large number of runs is independent of the reference frame. Objectivity and effectiveness of the three different formulations are quantified using a popular unimodal and multimodal test set, of which some of the multimodal functions are decomposable. However, the objective functions are evaluated in both the unrotated, decomposable reference frame, and an arbitrary rotated reference frame. 4. Finally, a practical engineering optimization problem is studied. The PSOA is used to find the optimal shape of a cantilever beam. The objective is to find the minimum vertical displacement at the edge point of the cantilever beam. In order to calculate the objective function the finite element method is used. The meshes needed for the linear elastic finite element analysis are generated using an unstructured remeshing strategy. The remeshing strategy is based on a truss structure analogy.