Project topics and materials
Get Complete Project Material File(s) Now! »
Introduction
In the eld of computational intelligence there exists an incredibly vast number of optimization algorithms. Many optimization algorithms are designed based on analogies, often inspired by nature, but the resulting algorithmic behavior is often ignored in favor of a simple empirical performance analysis. As a result, most computational intelligence based optimization algorithms are not truly understood from a theoretical perspective.
This leaves two important questions open: Firstly, does the algorithm actually exhibit behavior in line with its initial intent? Secondly, is the algorithm’s behavior predictable, and if so what kind of guarantees can be made about the algorithm? This thesis focuses on answering the second question in the context of particle swarm optimization (PSO).
There are numerous aspects of an optimization technique that can be investigated, ranging from an algorithm’s computational complexity, to the more specic property of rotational invariance. This thesis focuses on the stability of PSO and its variants’ particles. While there exists a number of theoretical results about PSO, most of PSO’s variants have undergone little or no analysis. The reason for this is two fold: Firstly, PSO variants are introduced at such a rapid rate that it is very dicult for the theory to catch up, given the complexity involved in modeling the algorithm. The second reason is that some PSO variants contain internal mechanisms that are fundamentally hard to model in practice, for example, dependencies between multiple particles or even sub-swarms, possible dependencies between previous time steps, the in uence of the underlying objective function on the algorithm behavior, to name but a few. The task of constructing a model of an algorithm, that is both re ective enough of the actual algorithm and simple enough to allow for meaningful conclusions to be derived from that model, is far from straightforward. It is for this reason that an rapid empirical approach for investigating stability criteria for PSO variants is needed. This thesis provides such an approach.
The empirical approach should have an additional use, namely the verication of theoretically derived stability criteria. All stability analysis performed on PSOs rely on a variant of the stagnation assumption, where by the updating of the personal and neighborhood best positions is heavily restricted. In the most extreme case, the personal and neighborhood best positions are held constant. While restriction of the personal and neighborhood best positions’ ability to update can allow for eective modeling of the PSO’s behavior, all derived results should still be empirically veried against a complete, and unsimplied PSO. It is for this reason that a simple method for verifying the criteria for stability is needed.
The use of a stagnation assumption is common place in theoretical analysis of PSOs. An immediate question is how weak of a stagntion assumption can be made, while still allowing for stability criteria to be derived. This thesis investigates this important question for a wide class of PSO variants.
1 Introduction
1.1 Motivation .
1.2 Objectives
1.3 Publication Derived from the Thesis
1.4 Thesis Outline
2 Particle Swarm Optimization
2.1 The Particle Swarm Optimization Algorithm
2.1.1 Algorithmic Description and Origin of PSO
2.1.2 Social Network Structure
2.2 Popular Particle Swarm Optimization Variants
2.2.1 Fully Informed PSO
2.2.2 Unied PSO
2.2.3 Bare Bones PSO
2.2.4 Standard PSO 2011
2.3 Summary
3 Review of Existing Theoretical Stability Analysis of Particle Swarm optimization
3.1 Common Assumptions
3.2 Convergence and Stability
3.3 Theoretical Results for PSO
3.4 Theoretical Analysis of the Fully Informed Particle Swarm Optimizer
3.5 Theoretical Analysis of the Bare Bones Particle Swarm Optimizer
3.6 Theoretical Analysis of the Unied Particle Swarm Optimizer 2011
3.7 Theoretical Analysis of the Standard Particle Swarm Optimizer 2011
3.8 Summary
4 Finding the True Convergence Region for PSO
4.1 Experimental Setup
4.2 Experimental Results and Discussion
4.3 Summary
5 Empirical Stability Analysis Approach
6 Fully Informed Particle Swarm Optimization: Stability Analysis
7 Unied Particle Swarm Optimization: Stability Analysis
8 In uence of Particle Stability on Performance
9 Extension of the Theoretical Particle Swarm Model
10 Conclusion
