A particle swarm optimizer with passive congregation
Introduction
The particle swarm optimizer (PSO) is a population-based algorithm that was invented by Kennedy and Eberhart (1995), which was inspired by the social behavior of animals such as fish schooling and bird flocking. Similar to other population-based algorithms, such as evolutionary algorithms, PSO can solve a variety of difficult optimization problems but has shown a faster convergence rate than other evolutionary algorithms on some problems (Kennedy and Eberhart, 2001). Another advantage of PSO is that it has very few parameters to adjust, which makes it particularly easy to implement.
Angeline (1998) pointed out that although PSO may outperform other evolutionary algorithms in the early iterations, its performance may not be competitive as the number of generations is increased. Recently, several investigations have been undertaken to improve the performance of standard PSO (SPSO). Lbjerg et al. (2001) presented a hybrid PSO model with breeding and subpopulations. Kennedy and Mendes (2002) investigated the the impacts of population structures to the search performance of SPSO. Other investigations on improving PSO’s performance were undertaken using cluster analysis (Kennedy, 2000) and fuzzy adaptive inertia weight (Shi and Eberhart, 2001).
The foundation of PSO is based on the hypothesis that social sharing of information among conspecifics offers an evolutionary advantage (Kennedy and Eberhart, 1995). The SPSO model is based on the following two factors (Kennedy and Eberhart, 1995):
- (1)
The autobiographical memory, which remembers the best previous position of each individual () in the swarm;
- (2)
The publicized knowledge, which is the best solution () found currently by the population.
Therefore, the sharing of information among conspecifics is achieved by employing the publicly available information , shown in Fig. 1. There is no information sharing among individuals except that broadcasts the information to the other individuals. Therefore, the population may lose diversity and is more likely to confine the search around local minima if committed too early in the search to the global best found so far.
Biologists have proposed four types of biological mechanisms that allow animals to aggregate into groups: passive aggregation, active aggregation, passive congregation, and social congregation (Parrish and Hamner, 1997). There are different information sharing mechanisms inside these forces. We found that the passive congregation model is suitable to be incorporated in the SPSO model. Inspired by this research, we propose a hybrid model of PSO with passive congregation.
Section 2 introduces the SPSO. A PSO algorithm with passive congregation is presented in Section 3. In Section 4, we describe the test functions, experimental settings, and the experimental results. The discussions are given in Section 5. The paper is concluded in Section 6.
Section snippets
Standard particle swarm optimizer
PSO is a population-based optimization algorithm. The population of PSO is called a swarm and each individual in the population of PSO is called a particle. The ith particle at iteration has the following two attributes:
- (1)
A current position in an N-dimensional search space , where and is lower and upper bound for the nth dimension, respectively.
- (2)
A current velocity , , which is bounded by a maximum velocity
Particle swarm optimizer with passive congregation
The PSO algorithm is inspired by social behaviors such as spatial order, more specially, aggregation such as bird flocking, fish schooling, or swarming of insects. Each of these cases has stable spatio-temporal integrities of the group of organisms: the group moves persistently as a whole without losing the shape and density.
For each of these groups, different biological forces are essential for preserving the group’s integrity. Parrish and Hamner (1997) proposed mathematical models of the
Test functions
In our experimental studies, a set of 10 benchmark functions was employed to evaluate the PSOPC algorithm in comparison with others.
Sphere model:Schwefel’s Problem 1.2:Schwefel’s Problem 2.21:Generalized Rosenbrock’s function:Generalized Schwefel’s Problem 2.26:Generalized Rastrigin’s function:Ackley’s function:
Discussion
Arithmetically, this passive congregation operator can be regarded as a stochastic variable that introduces perturbations to the search process. Fieldsend and Singh (2002) also introduced a stochastic variable into the standard PSO, which is referred to as turbulence in their paper. The velocity-updating equation is given bywhere is a random variable , and R is the absolute range of the model parameter.
From our experience, a large R will
Summary
In this paper, a new PSO with passive congregation (PSOPC) has been presented based on the standard PSO. By introducing passive congregation, information can be transferred among individuals that will help individuals to avoid misjudging information and becoming trapped by poor local minima. The only coefficient introduced into the standard PSO is the passive congregation coefficient . A generic value of was selected by experiments.
A set of 10 benchmark functions has been used to test
Acknowledgements
We wish to dedicate this paper to the memory of Dr. Ray C. Paton, who passed away on July 29, 2004. He is greatly missed by us all. Thanks to three anonymous referees for the comments on an earlier version of this paper and Dr. David Fogel for his comments to improve the quality of this paper.
References (28)
- et al.
What is the function of encounter pattern in ant colonies?
Anim. Behav.
(1993) Geometry for the selfish herd
J. Theor. Biol.
(1971)The evolution of social behaviour
Annu. Rev. Ecol. Syst.
(1974)Evolutionary optimization versus particle swarm optimization: philosophy and performance difference
- et al.
Swarm Intelligence: From Natural to Artificial Systems
(1999) Combining mutation operators in evolutionary programming
IEEE Trans. Evolut. Comput.
(September 1998)- et al.
The particle swarm: explosion, stability, and convergence in a multi-dimensional complex space
IEEE Trans. Evolut. Comput.
(2002) - et al.
The dynamics of collective sorting: robot-like ant and ant-like robot
- et al.
Comparing inertia weights and constriction factors in particle swarm optimization
- et al.
Particle swarm optimization: developments, applications and resources