This paper reviews recent studies on the Particle Swarm Optimization (PSO) algorithm. The review has been focused on high impact recent articles that have analyzed and/or modified PSO algorithms. This paper also presents some potential areas for future study.
In this paper, we investigate three important properties (stability, local convergence, and transformation invariance) of a variant of particle swarm optimization (PSO) called standard PSO 2011 (SPSO2011). Through some experiments, we identify boundaries of coefficients for this algorithm that ensure particles converge to their equilibrium. Our experiments show that these convergence boundaries for this algorithm are: 1) dependent on the number of dimensions of the problem; 2) different from that of some other PSO variants; and 3) not affected by the stagnation assumption. We also determine boundaries for coefficients associated with different behaviors, e.g., nonoscillatory and zigzagging, of particles before convergence through analysis of particle positions in the frequency domain. In addition, we investigate the local convergence property of this algorithm and we prove that it is not locally convergent. We provide a sufficient condition and related proofs for local convergence for a formulation that represents updating rules of a large class of PSO variants. We modify the SPSO2011 in such a way that it satisfies that sufficient condition; hence, the modified algorithm is locally convergent. Also, we prove that the original standard PSO algorithm is not sensitive to rotation, scaling, and translation of the search space.
There are some questions concerning the applicability of meta-heuristic methods for real-world problems; further, some researchers claim there is a growing gap between research and practice in this area. The reason is that the complexity of real-world problems is growing very fast (e.g. due to globalisation), while researchers experiment with benchmark problems that are fundamentally the same as those of 50 years ago. Thus there is a need for a new class of benchmark problems that reflect the characteristics of real-world problems. In this paper, two main characteristics of real-world problems are introduced: combination and interdependence. We argue that real-world problems usually consist of two or more sub-problems that are interdependent (to each other). This interdependence is responsible for the complexity of the real-world problems, while the type of complexity in current benchmark problems is missing. A new problem, called the travelling thief problem, is introduced; it is a combination of two well-known problems, the knapsack problem and the travelling salesman problem. Some parameters which are responsible for the interdependence of these two sub-problems are defined. Two sets of parameters are introduced that result in generating two instances of the travelling thief problem. The complexities that are raised by interdependences for these two instances are discussed in detail. Finally, a procedure for generating these two instances is given.
Real-world optimization problems often consist of several NP-hard optimization problems that interact with each other. The goal of this paper is to provide a benchmark suite that promotes a research of the interaction between problems and their mutual influence. We establish a comprehensive benchmark suite for the traveling thief problem (TTP) which combines the traveling salesman problem and the knapsack problem. Our benchmark suite builds on common benchmarks for the two sub-problems which grant a basis to examine the potential hardness imposed by combining the two classical problems. Furthermore, we present some simple heuristics for TTP and their results on our benchmark suite.
11 December 2015 in IEEE Transactions on Evolutionary Computation
In this letter, we study the first- and second-order stabilities of a stochastic recurrence relation that represents a class of particle swarm optimization (PSO) algorithms. We assume that the personal and global best vectors in that relation are random variables (with arbitrary means and variances) that are updated during the run so that our calculations do not require the stagnation assumption. We prove that the convergence of expectation and variance of the positions generated by that relation is independent of the mean and variance of the distribution of the personal and global best vectors. We also provide convergence boundaries for that relation and compare them with those of standard PSO algorithms (as a specific case of the stochastic recurrence relation) provided in earlier studies.