Experimental Study on Boundary Constraints Handling in Particle Swarm Optimization

Experimental Study on Boundary Constraints Handling in Particle Swarm Optimization

Shi Cheng (Shaanxi Normal University, China) and Yuhui Shi (Southern University of Science and Technology, China)
DOI: 10.4018/978-1-7998-3222-5.ch011

Abstract

With an improper boundary constraints handling method, particles may get “stuck in” the boundary. Premature convergence means that an algorithm has lost its ability of exploration. Population diversity (PD) is an effective way to monitor an algorithm's ability for exploration and exploitation. Through the PD measurement, useful search information can be obtained. PSO with a different topology structure and different boundary constraints handling strategy will have a different impact on particles' exploration and exploitation ability. In this chapter, the phenomenon of particles gets “stuck in” the boundary in PSO and is experimentally studied and reported. The authors observe the position diversity time-changing curves of PSOs with different topologies and different boundary constraints handling techniques and analyze the impact of these strategies on the algorithm's ability of exploration and exploitation.
Chapter Preview
Top

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.

Key Terms in this Chapter

Position Diversity: Position diversity measures distribution of particles' current positions, therefore, can reflect particles' dynamics. Position diversity gives the current position distribution information of particles, whether the particles are going to diverge or converge could be reflected from this measurement.

Particle Swarm Optimizer/Optimization: Particle Swarm Optimizer/Optimization, which is one of the evolutionary computation techniques, was invented by Eberhart and Kennedy in 1995. It is a population-based stochastic algorithm modeled on the social behaviors observed in flocking birds. Each particle, which represents a solution, flies through the search space with a velocity that is dynamically adjusted according to its own and its companion's historical behaviors.

Exploration: The exploration ability means that an algorithm can explore more search place to increase the possibility that the algorithm can find good enough solutions.

Premature Convergence: Premature convergence is a phenomenon that occurs in population-based algorithms. Premature convergence occurs when all individuals in population-based algorithms are trapped in local optima.

Population Diversity: Population diversity is a measure of individuals' search information in population-based algorithms. From the distribution of individuals and change of this distribution information, the algorithm's status of exploration or exploitation can be obtained.

Boundary Constraints Handling: In particle swarm optimization algorithm, particles may “stick in” the boundary. The boundary constraints handling strategies are some methods to handle the particles (or individuals) cross the search boundary, i.e., to handle the phenomenon that solutions out of the predefined search space.

Exploitation: The exploitation ability means that an algorithm focuses on the refinement of found promising areas.

Complete Chapter List

Search this Book:
Reset