Elsevier

Biosystems

Volume 78, Issues 1–3, December 2004, Pages 135-147
Biosystems

A particle swarm optimizer with passive congregation

https://doi.org/10.1016/j.biosystems.2004.08.003Get rights and content

Abstract

This paper presents a particle swarm optimizer (PSO) with passive congregation to improve the performance of standard PSO (SPSO). Passive congregation is an important biological force preserving swarm integrity. By introducing passive congregation to PSO, information can be transferred among individuals of the swarm. A particle swarm optimizer with passive congregation (PSOPC) is tested with a set of 10 benchmark functions with 30 dimensions and compared to a global version of SPSO (GSPSO), a local version of SPSO (LSPSO), and PSO with a constriction factor (CPSO), respectively. Experimental results indicate that the PSO with passive congregation improves the search performance on the benchmark functions significantly.

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 (Pi) in the swarm;

  • (2)

    The publicized knowledge, which is the best solution (Pg) found currently by the population.

Therefore, the sharing of information among conspecifics is achieved by employing the publicly available information Pg, shown in Fig. 1. There is no information sharing among individuals except that Pg 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 k has the following two attributes:

  • (1)

    A current position in an N-dimensional search space Xik=(x1k,,xnk,,xNk), where xnk[ln,un],1nN,ln and un is lower and upper bound for the nth dimension, respectively.

  • (2)

    A current velocity Vik, Vik=(v1k,,vnk,,vNk), which is bounded by a maximum velocity Vmaxk=(vmax,1k,,v

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:f1(x)=i=130xi2Schwefel’s Problem 1.2:f2(x)=i=130j=1ixj2Schwefel’s Problem 2.21:f3(x)=maxi{|xi|,1i30}Generalized Rosenbrock’s function:f4(x)=i=129(100(xi+1xi2)2+(xi1))2Generalized Schwefel’s Problem 2.26:f5(x)=i=130(xisin(|xi|))Generalized Rastrigin’s function:f6(x)=i=130(xi210cos(2πxi)+10)2Ackley’s function:f7(x)=20exp0.2130i=130xi2

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 byVik+1=ωVik+c1r1(PikXik)+c2r2(PgkXik)+r3where r3 is a random variable r3U(0,0.1R), 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 c3. A generic value of c3 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)

  • D.M. Gordon et al.

    What is the function of encounter pattern in ant colonies?

    Anim. Behav.

    (1993)
  • W.D. Hamilton

    Geometry for the selfish herd

    J. Theor. Biol.

    (1971)
  • R.D. Alexander

    The evolution of social behaviour

    Annu. Rev. Ecol. Syst.

    (1974)
  • P. Angeline

    Evolutionary optimization versus particle swarm optimization: philosophy and performance difference

  • E. Bonabeau et al.

    Swarm Intelligence: From Natural to Artificial Systems

    (1999)
  • K. Chellapilla

    Combining mutation operators in evolutionary programming

    IEEE Trans. Evolut. Comput.

    (September 1998)
  • M. Clerc et al.

    The particle swarm: explosion, stability, and convergence in a multi-dimensional complex space

    IEEE Trans. Evolut. Comput.

    (2002)
  • J.L. Deneubourg et al.

    The dynamics of collective sorting: robot-like ant and ant-like robot

  • R. Eberhart et al.

    Comparing inertia weights and constriction factors in particle swarm optimization

  • R.C. Eberhart et al.

    Particle swarm optimization: developments, applications and resources

  • J.E. Fieldsend et al.

    A multi-objective algorithm based upon particle swarm optimisation, an efficient data structure and turbulence

  • D.B. Fogel

    System Identification Through Simulated Evolution: A Machine Learning Approach to Modeling

    (1991)
  • R. Hilborn

    Modelling the stability of fish schools: exchange of individual fish between schools of skipjack tuna (Katsuwonus pelamis)

    Can. J. Fish. Aquat. Sci.

    (1991)
  • J. Kennedy

    Stereotyping: improving particle swarm performance with cluster analysis

  • Cited by (0)

    View full text