Quotient Space-Based Boundary Condition for Particle Swarm Optimization Algorithm

Introduction

Particle swarm optimization (PSO) (Bratton & Kennedy, 2007) proposed by Kennedy and Eberhart (1995) is an evolutionary algorithm, based on social behaviors of organisms of fish schooling and bird flocking. In PSO, particles are free to fly inside the defined D-dimensional space dictated by optimization problems, where it is assumed that global optimum is inside, so that particles moving outside search space can’t find global optimum. So that it is necessary to control particles moving inside the limited search space by some way which is called boundary condition.

Though in the canonical PSO method is confessedly that nothing can prevent particles from going outside search space at anytime, and it is usually thought that it is just the behavior of few particles (Kennedy, 2005, 2008), Helwig and Wanka (2008) derived some surprised conclusions and proved that all particles leave search space in the first iteration with overwhelming probability when using uniform velocity initialization and if velocities are initialized to zero, all particles which have a better neighbor than themselves leave search space in the first iteration with overwhelming probability. More details can be found in Helwig and Wanka (2008). Various boundary conditions are proposed to enforce particles to move inside search space, among them, such as velocity-clipping and position-clipping (Eberhart & Shi, 2001) are simple and common boundary conditions widely used in PSO literatures, but velocity-clipping can’t prevent particles from flying outside search space. To solve this problem, three kinds of boundary condition walls, namely, Absorbing, Reflecting, and Invisible, are imposed by Robinson and Yahya (2004), and Damping reported to provide robust performance by Huang and Mohan (2005) is a hybrid boundary condition that combines the characteristics offered by the Absorbing and Reflection. As cited in Xu and Yahya (2007), four kinds of walls are summarized and tested, among which the only difference is the way of treating errant particle’s velocity. To address the invariant maximum velocity in above methods, the Random Velocity method is introduced by Li, Ren, and Wang (2007), where the upper and lower velocity boundaries keep on altering during the whole evolution. Different with other boundary conditions which keeping particles lying inside search space, the Periodic mode (Zhang, Xie, & Bi, 2004) provides an infinite search space for the flying of particles. Because all of boundary conditions strongly influence particle behavior, which means that they actually strongly influence the swarm performance, in a word, they are important for PSO, and significant performance differences when varying boundary conditions.

The purpose of this paper is to report an efficient and simple quotient space-based boundary condition for PSO, named QsaBC, by using the advantages of quotient space and homeomorphism, and where the swarm is not bounded by the end points. By analyzing the dynamic behavior and stability of particles, Search space-zoomed factor and Attractor are introduced in QsaBC which deal with the problem of errant particles, at the same time avoid premature convergence and improve search speed of convergence.