Particle swarm optimization: theoretical analysis, modifications, and applications to constrained optimization problems.

Abstract

This is a PhD thesis by publication. It includes five journal papers, three of them already published, and two submitted for publication in a very high quality international journal in the field of Evolutionary Computation (one of which – as an invited paper). Further, the thesis contains also four conference papers presented and published in the top peer reviewed conferences, as well as one peer reviewed chapter book. In this thesis we studied an optimization algorithm called Particle Swarm Optimization (PSO) from theoretical and application point of views. The main focus of the theoretical analysis of the algorithm was towards understanding and addressing its limitations that were related to transformations of the search space, convergence to quality solutions, and stability. Through analysis of the algorithm under transformations of the search space we proposed a modification to the original PSO so that a stable performance was guaranteed when the search space was transformed, i.e., rotated, scaled, and translated. We also studied the ability of the original PSO in locating optimum solutions (local and global optima). Our study showed that this algorithm cannot guarantee to find a local optimum. We introduced a general formulation of topology for the original PSO and identified conditions so that it did not only guarantee local convergence but also transformation invariance. Further, we proposed a specific formulation, extracted from the general formulation, and experimentally confirmed the theoretical findings. We investigated the most recent standard version of SPSO, called standard PSO 2011 (SPSO2011), from stability, convergence, and transformation sensitivity perspectives. Our investigations revealed essential differences between stability conditions for SPSO2011 with earlier PSO variants. We introduced stability conditions for SPSO2011 and analyzed the behavior of the algorithm before collapsing on its equilibrium. Also, we proved that this algorithm cannot guarantee to find a local optimum in the search space. We introduced sufficient condition for a general formulation that represents a large class of PSO variants so that convergence to a local optimum is guaranteed. We then modified SPSO2011 so that the mentioned sufficient condition was satisfied and convergence to local optimum was guaranteed. Apart from theoretical analysis, we also studied performance of the algorithm when it was applied to continuous space constrained optimization problems (COPs). We introduced a new aspect in dealing with constrained optimization problems namely locating disjoint feasible regions in a search space. We developed a variant of PSO that was able to locate disjoint feasible regions in a search space. This track of research can potentially be of interest of many other researchers in the field of optimization in future. As it has been emphasized in many articles, the boundaries of feasible and infeasible regions in a COP can lead optimization algorithms to high quality solutions. We introduced a new approach to concentrate the search on the boundaries of the feasible and infeasible space. As a case study we used a variant of PSO and we confirmed that the results of the new approach are competitive with that of existing approaches in dealing with constraints. We also proposed a coding scheme to map a discrete space constrained optimization problem, namely multi-dimensional knapsack problem, to a continuous space constrained optimization problem. Then, we investigated the ability of a variant of PSO to deal with the mapped version of this problem.