Heterogeneous Particle Swarm Optimizers

by Marco A. Montes de Oca, Jorge Peña, Thomas Stützle, Carlo Pinciroli, and Marco Dorigo
November 2008

To appear in the Proceedings of the IEEE Congress on Evolutionary Computation (CEC-2009).

This page contains all supplementary information that, for the sake of conciseness, was not included in the paper.

A preprint version of the paper is available here

Table of Contents
  1. Paper Abstract
  2. Benchmark functions
  3. Different update rules: velocity-based & bare-bones swarm
    1. Results with 10 particles
    2. Results with 100 particles
    3. Results with 1000 particles
  4. Different models of influence: best-of-neighborhood & fully-informed swarm
    1. Results with 10 particles
    2. Results with 100 particles
    3. Results with 1000 particles

Paper Abstract

Particle swarm optimization (PSO) is a swarm intelligence technique originally inspired by models of flocking and of social influence that assumed homogeneous individuals. During its evolution to become a practical optimization tool, some heterogeneous variants have been proposed. However, heterogeneity in PSO algorithms has never been explicitly studied and some of its potential effects have therefore been overlooked. In this paper, we identify some of the most relevant types of heterogeneity that can be ascribed to particle swarms. A number of particle swarms are classified according to the type of heterogeneity they exhibit, which allows us to identify some gaps in current knowledge about heterogeneity in PSO algorithms. Motivated by these observations, we carry out an experimental study of two heterogeneous particle swarms each of which is composed of two kinds of particles. Directions for future developments on heterogeneous particle swarms are outlined.

Keywords: Heterogeneous Particle Swarms, Particle Swarm Optimization, Swarm Intelligence, Heterogeneity.



Benchmark functions

The following table shows the mathematical definition of the benchmark functions used in this study

Table 1: Benchmark optimization problems
Name Definition Range
Ackley $ -20e^{-0.2\sqrt{\frac{1}{n}\sum_{i=1}^{n}x^2_i}}-e^{\frac{1}{n}\sum_{i=1}^{n}\cos(2\pi x_i)}+20+e$ $ [-32,32]^n$
Griewank $ \frac{1}{4000}\sum^{n}_{i=1}x^2_i -\prod^{n}_{i=1}\cos\left(\frac{x_i}{\sqrt{i}}\right) + 1$ $ [-600,600]^n$
Expanded Schaffer $ ES(\mathbf{x}) = \sum^{n-1}_{i=1}S(x_i,x_{i+1}) + S(x_n,x_1),$   where$    S(x,y) = 0.5 +\frac{\sin^2{(\sqrt{x^2 + y^2})} - 0.5 }{(1+0.001(x^2 + y^2))^2}$ $ [-100,100]^n$
Rastrigin $ 10n+\sum^{n}_{i=1}{(x^2_i-10\cos(2\pi x_i))} $ $ [-5.12,5.12]^n$
Rosenbrock $ \sum^{n-1}_{i=1}{[100(x_{i+1}-x^2_i)^2+(x_i-1)^2]} $ $ [-30,30]^n$
Salomon $ 1 - \cos\left( 2\pi \sqrt{\sum^{n}_{i=1}x^2_i}\right) +0.1\sqrt{\sum^{n}_{i=1}x^2_i} $ $ [-100,100]^n$
Schwefel $ 418.9829n+\sum^{n}_{i=1}{-x_i\sin\left(\sqrt{\vert x_i\vert}\right)}$ $ [-500,500]^n$
Sphere $ \sum^{n}_{i=1}{x^2_i}$ $ [-100,100]^n$
Step $ 6n + \sum^{n}_{i=1}\lfloor x_i \rfloor$ $ [-5.12,5.12]^n$
Weierstrass $ \sum^{n}_{i=1}\left(\sum^{k_{max}}_{k=1}a^k\cos\left(2\pi b^k(x_i+0.5)\right)\right) - n \sum^{k_{max}}_{k=1}\left[ a^k\cos\left(\pi b^k\right)\right],$   where$    a=0.5$, $ b=3$, $ k_{max}=20$ $ [-0.5,0.5]^n$


Different update rules: velocity-based & bare-bones swarm

The following figures show the mean of the contribution of velocity-based particles to the improvement of the best-so-far solution and the development of the solution quality over time onsolution quality improvement over time.

Results with 10 particles

Ackley function - 100 dimensions
Fully-connected topologyRing topology
Ackley - FC Ackley - Ring
Ackley - FC Ackley - Ring
Griewank function - 100 dimensions
Fully-connected topologyRing topology
Ackley - FC Ackley - Ring
Ackley - FC Ackley - Ring
Expanded Schaffer function - 100 dimensions
Fully-connected topologyRing topology
Ackley - FC Ackley - Ring
Ackley - FC Ackley - Ring
Rastrigin function - 100 dimensions
Fully-connected topologyRing topology
Ackley - FC Ackley - Ring
Ackley - FC Ackley - Ring
Rosenbrock function - 100 dimensions
Fully-connected topologyRing topology
Ackley - FC Ackley - Ring
Ackley - FC Ackley - Ring
Salomon function - 100 dimensions
Fully-connected topologyRing topology
Ackley - FC Ackley - Ring
Ackley - FC Ackley - Ring
Schwefel function - 100 dimensions
Fully-connected topologyRing topology
Ackley - FC Ackley - Ring
Ackley - FC Ackley - Ring
Sphere function - 100 dimensions
Fully-connected topologyRing topology
Ackley - FC Ackley - Ring
Ackley - FC Ackley - Ring
Step function - 100 dimensions
Fully-connected topologyRing topology
Ackley - FC Ackley - Ring
Ackley - FC Ackley - Ring
Weierstrass function - 100 dimensions
Fully-connected topologyRing topology
Ackley - FC Ackley - Ring
Ackley - FC Ackley - Ring

Results with 100 particles

Ackley function - 100 dimensions
Fully-connected topologyRing topology
Ackley - FC Ackley - Ring
Ackley - FC Ackley - Ring
Griewank function - 100 dimensions
Fully-connected topologyRing topology
Ackley - FC Ackley - Ring
Ackley - FC Ackley - Ring
Expanded Schaffer function - 100 dimensions
Fully-connected topologyRing topology
Ackley - FC Ackley - Ring
Ackley - FC Ackley - Ring
Rastrigin function - 100 dimensions
Fully-connected topologyRing topology
Ackley - FC Ackley - Ring
Ackley - FC Ackley - Ring
Rosenbrock function - 100 dimensions
Fully-connected topologyRing topology
Ackley - FC Ackley - Ring
Ackley - FC Ackley - Ring
Salomon function - 100 dimensions
Fully-connected topologyRing topology
Ackley - FC Ackley - Ring
Ackley - FC Ackley - Ring
Schwefel function - 100 dimensions
Fully-connected topologyRing topology
Ackley - FC Ackley - Ring
Ackley - FC Ackley - Ring
Sphere function - 100 dimensions
Fully-connected topologyRing topology
Ackley - FC Ackley - Ring
Ackley - FC Ackley - Ring
Step function - 100 dimensions
Fully-connected topologyRing topology
Ackley - FC Ackley - Ring
Ackley - FC Ackley - Ring
Weierstrass function - 100 dimensions
Fully-connected topologyRing topology
Ackley - FC Ackley - Ring
Ackley - FC Ackley - Ring

Results with 1000 particles

Ackley function - 100 dimensions
Fully-connected topologyRing topology
Ackley - FC Ackley - Ring
Ackley - FC Ackley - Ring
Griewank function - 100 dimensions
Fully-connected topologyRing topology
Ackley - FC Ackley - Ring
Ackley - FC Ackley - Ring
Expanded Schaffer function - 100 dimensions
Fully-connected topologyRing topology
Ackley - FC Ackley - Ring
Ackley - FC Ackley - Ring
Rastrigin function - 100 dimensions
Fully-connected topologyRing topology
Ackley - FC Ackley - Ring
Ackley - FC Ackley - Ring
Rosenbrock function - 100 dimensions
Fully-connected topologyRing topology
Ackley - FC Ackley - Ring
Ackley - FC Ackley - Ring
Salomon function - 100 dimensions
Fully-connected topologyRing topology
Ackley - FC Ackley - Ring
Ackley - FC Ackley - Ring
Schwefel function - 100 dimensions
Fully-connected topologyRing topology
Ackley - FC Ackley - Ring
Ackley - FC Ackley - Ring
Sphere function - 100 dimensions
Fully-connected topologyRing topology
Ackley - FC Ackley - Ring
Ackley - FC Ackley - Ring
Step function - 100 dimensions
Fully-connected topologyRing topology
Ackley - FC Ackley - Ring
Ackley - FC Ackley - Ring
Weierstrass function - 100 dimensions
Fully-connected topologyRing topology
Ackley - FC Ackley - Ring
Ackley - FC Ackley - Ring

Different models of influence: best-of-neighborhood & fully-informed swarm

The following figures show the mean of the contribution of particles using the best-of-neighborhood model of influence to the improvement of the best-so-far solution and the development of the solution quality over time.

Results with 10 particles

Ackley function - 100 dimensions
Fully-connected topologyRing topology
Ackley - FC Ackley - Ring
Ackley - FC Ackley - Ring
Griewank function - 100 dimensions
Fully-connected topologyRing topology
Ackley - FC Ackley - Ring
Ackley - FC Ackley - Ring
Expanded Schaffer function - 100 dimensions
Fully-connected topologyRing topology
Ackley - FC Ackley - Ring
Ackley - FC Ackley - Ring
Rastrigin function - 100 dimensions
Fully-connected topologyRing topology
Ackley - FC Ackley - Ring
Ackley - FC Ackley - Ring
Rosenbrock function - 100 dimensions
Fully-connected topologyRing topology
Ackley - FC Ackley - Ring
Ackley - FC Ackley - Ring
Salomon function - 100 dimensions
Fully-connected topologyRing topology
Ackley - FC Ackley - Ring
Ackley - FC Ackley - Ring
Schwefel function - 100 dimensions
Fully-connected topologyRing topology
Ackley - FC Ackley - Ring
Ackley - FC Ackley - Ring
Sphere function - 100 dimensions
Fully-connected topologyRing topology
Ackley - FC Ackley - Ring
Ackley - FC Ackley - Ring
Step function - 100 dimensions
Fully-connected topologyRing topology
Ackley - FC Ackley - Ring
Ackley - FC Ackley - Ring
Weierstrass function - 100 dimensions
Fully-connected topologyRing topology
Ackley - FC Ackley - Ring
Ackley - FC Ackley - Ring

Results with 100 particles

Ackley function - 100 dimensions
Fully-connected topologyRing topology
Ackley - FC Ackley - Ring
Ackley - FC Ackley - Ring
Griewank function - 100 dimensions
Fully-connected topologyRing topology
Ackley - FC Ackley - Ring
Ackley - FC Ackley - Ring
Expanded Schaffer function - 100 dimensions
Fully-connected topologyRing topology
Ackley - FC Ackley - Ring
Ackley - FC Ackley - Ring
Rastrigin function - 100 dimensions
Fully-connected topologyRing topology
Ackley - FC Ackley - Ring
Ackley - FC Ackley - Ring
Rosenbrock function - 100 dimensions
Fully-connected topologyRing topology
Ackley - FC Ackley - Ring
Ackley - FC Ackley - Ring
Salomon function - 100 dimensions
Fully-connected topologyRing topology
Ackley - FC Ackley - Ring
Ackley - FC Ackley - Ring
Schwefel function - 100 dimensions
Fully-connected topologyRing topology
Ackley - FC Ackley - Ring
Ackley - FC Ackley - Ring
Sphere function - 100 dimensions
Fully-connected topologyRing topology
Ackley - FC Ackley - Ring
Ackley - FC Ackley - Ring
Step function - 100 dimensions
Fully-connected topologyRing topology
Ackley - FC Ackley - Ring
Ackley - FC Ackley - Ring
Weierstrass function - 100 dimensions
Fully-connected topologyRing topology
Ackley - FC Ackley - Ring
Ackley - FC Ackley - Ring

Results with 1000 particles

Ackley function - 100 dimensions
Fully-connected topologyRing topology
Ackley - FC Ackley - Ring
Ackley - FC Ackley - Ring
Griewank function - 100 dimensions
Fully-connected topologyRing topology
Ackley - FC Ackley - Ring
Ackley - FC Ackley - Ring
Expanded Schaffer function - 100 dimensions
Fully-connected topologyRing topology
Ackley - FC Ackley - Ring
Ackley - FC Ackley - Ring
Rastrigin function - 100 dimensions
Fully-connected topologyRing topology
Ackley - FC Ackley - Ring
Ackley - FC Ackley - Ring
Rosenbrock function - 100 dimensions
Fully-connected topologyRing topology
Ackley - FC Ackley - Ring
Ackley - FC Ackley - Ring
Salomon function - 100 dimensions
Fully-connected topologyRing topology
Ackley - FC Ackley - Ring
Ackley - FC Ackley - Ring
Schwefel function - 100 dimensions
Fully-connected topologyRing topology
Ackley - FC Ackley - Ring
Ackley - FC Ackley - Ring
Sphere function - 100 dimensions
Fully-connected topologyRing topology
Ackley - FC Ackley - Ring
Ackley - FC Ackley - Ring
Step function - 100 dimensions
Fully-connected topologyRing topology
Ackley - FC Ackley - Ring
Ackley - FC Ackley - Ring
Weierstrass function - 100 dimensions
Fully-connected topologyRing topology
Ackley - FC Ackley - Ring
Ackley - FC Ackley - Ring