Experimental Study on Boundary Constraints Handling in Particle Swarm Optimization

1. Introduction

Particle Swarm Optimization (PSO) was introduced by Eberhart and Kennedy in 1995 (Eberhart & Kennedy, 1995; Kennedy & Eberhart, 1995). It is a population-based stochastic algorithm modeled on social behaviors observed in flocking birds. A particle flies through the search space with a velocity that is dynamically adjusted according to its own and its companion's historical behaviors. Each particle's position represents a solution to the problem. Particles tend to fly toward better and better search areas over the course of the search process (Eberhart & Shi, 2001).

Optimization, in general, is concerned with finding the “best available” solution(s) for a given problem. Optimization problems can be simply divided into unimodal problems and multimodal problems. As indicated by the name, a unimodal problem has only one optimum solution; on the contrary, a multimodal problem has several or numerous optimum solutions, of which many are local optimal solutions. Evolutionary optimization algorithms are generally difficult to find the global optimum solutions for multimodal problems due to the possible occurrence of premature convergence.

Most reported optimization methods are designed to avoid premature convergence in solving multimodal problems (Blackwell & Bentley, 2002). However, premature convergence also happens in solving unimodal problems when the algorithm has an improper boundary constraint handling method. For example, even for the simplest benchmark function—Sphere, or termed as a Parabolic problem, which has a convex curve in each dimension, particles may “stick in” the boundary and the applied PSO algorithm, therefore, cannot find the global optimum at the end of its search process. With regard to this, premature convergence needs to be addressed in both unimodal and multimodal problems. Avoiding premature convergence is important in problem optimization, i.e., an algorithm should have a balance between fast convergence speed and the ability of “jumping out” of local optima.

Particles fly in the search space. If particles can easily get clustered together in a short time, particles will lose their “search potential.” Premature convergence means particles have a low possibility to explore new search areas. Although many methods were reported to be designed to avoid premature convergence (Chen & Montgomery, 2011), these methods did not incorporate an effective way to measure the degree of premature convergence, in other words, the measurement of particles’ exploration/exploitation is still needed to be investigated. Shi and Eberhart gave several definitions of diversity measurement based on particles’ positions (Shi & Eberhart, 2008; Shi & Eberhart, 2009). Through diversity measurements, useful exploration and/or exploitation search information can be obtained.

PSO is simple in concept and easy in implementation, however, there are still many issues that need to be considered (Kennedy, 2007). Boundary constraint handling is one of them (Xu and Rahmat-Samii, 2007; Helwig, et al., 2013). In this chapter, different boundary constraints handling methods and their impacts are discussed. Position diversity will be measured and analyzed for PSO with different boundary constraints handle strategies and different topology structures.

This chapter is organized as follows. Section 2 reviews the basic PSO algorithm, four different topology structures, and definitions of population diversities. Section 3 describes several boundary constraints handling techniques, which include the classic strategy, deterministic strategy, and stochastic strategy. Experiments are conducted in Section 4 followed by analysis and discussion on the population diversity changing curves of PSOs with different boundary constraints handling methods and four kinds of topology structures. Finally, Section 6 concludes with some remarks and future research directions.