Supporting material for the paper:

A Comparison of Particle Swarm Optimization Algorithms Based on Run-Length Distributions

Marco Montes de Oca, Thomas Stützle, Mauro Birattari, and Marco Dorigo


Accepted for publication in the Proceedings of the 5th international Workshop on
Ant Colony Optimization and Swarm Intelligence, ANTS 2006

Abstract:

In this paper we report a comparison of some of the most influential Particle Swarm Optimization algorithms based on run-length distributions (RLDs). The advantage of our approach over the usual report pattern (average iterations to reach a predefined goal, success rates, and standard deviations) found in the current PSO literature is that it is possible to evaluate the performance of an algorithm on different application scenarios at the same time. The RLDs reported in this paper show some of the strengths and weaknesses of the studied algorithms and suggest ways of improving their performance.

Keywords: particle swarm optimization, run-length distributions

 

Experimental Controls:

To ensure the correctness of our implementations, we tested them on the same problems with the same parameters as reported in the literature. These are the results:

Average solution value and standard deviation
(our implementation vs results reported in the literature)
Function Algorithm Literature Our implementation Settings Reference
Sphere Canonical-PSO 6.86e-24
(--)
4.73991e-09
(2.87181e-09)
Dimensions: 30
Topology: Square
Initialization: asymmetrical
No. of particles: 20
No. of runs: 50
No. of iterations: 3000
(Kennedy, 2004)
Time-Increasing Inertia Weight PSO 1.3128e-9
(--)
1.05764e-06
(3.0892e-06)
Dimensions: 30
Topology: Fully connected
Initialization: asymmetrical
No. of particles: 20
No. of runs: 20
No. of iterations: 2000
(Zheng et al., 2003)
Time-Decreasing Inertia Weight PSO 0.0000
(--)
6.21681e-08
( 1.15432e-07)
Dimensions: 30
Topology: Fully connected
Initialization: asymmetrical
No. of particles: 20
No. of runs: 50
No. of iterations: 2000
(Kennedy et al., 2001)
Stochastic Inertia Weight PSO 0.01
(--)
5.48384e-09
( 2.79073e-09)
Dimensions: 30
Topology: Fully connected
Initialization: asymmetrical
No. of particles: 40
No. of runs: 50
No. of iterations: 3000
(Ratnaweera et al., 2004)
Fully Informed Particle Swarm 3.13e-39
(8.25e-39)
5.23306e-09
(3.28642e-09)
Dimensions: 30
Topology: Square
Initialization: asymmetrical
No. of particles: 20
No. of runs: 50
No. of iterations: 3000
(Kennedy,2003)
Self-Organizing Hierarchical Particle
Swarm Optimizer with Time-varying
Acceleration Coefficients
0.01
(-)
5.73233e-09
(2.74801e-09)
Dimensions: 30
Topology: Fully connected
Initialization: asymmetrical
No. of particles: 40
No. of runs: 50
No. of iterations: 3000
(Ratnaweera et al., 2004)
Adaptive Hierarchical Particle Swarm
Optimizer
1e-48 (aprox)*
(--)
5.89199e-09
(2.8147e-09)
Dimensions: 30
Topology: --
Initialization: symmetrical
No. of particles: 40
No. of runs: 100
No. of iterations: 3000
(Janson and Middendorf, 2005)
Rosenbrock Canonical-PSO 39.5256
(--)
96.04
(101.04)
Dimensions: 30
Topology: Square
Initialization: asymmetrical
No. of particles: 20
No. of runs: 50
No. of iterations: 3000
(Kennedy, 2004)
Time-Increasing Inertia Weight PSO 37.4257
(--)
2.52679e+09
( 1.94479e+09)
Dimensions: 30
Topology: Fully connected
Initialization: asymmetrical
No. of particles: 20
No. of runs: 20
No. of iterations: 2000
(Zheng et al., 2003)
Time-Decreasing Inertia Weight PSO 316.4468
(--)
231.258
(286.765)
Dimensions: 30
Topology: Fully connected
Initialization: asymmetrical
No. of particles: 20
No. of runs: 50
No. of iterations: 2000
(Kennedy et al., 2001)
Stochastic Inertia Weight PSO 35.277
(55.751)
24.5597
(35.0822)
Dimensions: 30
Topology: Fully connected
Initialization: asymmetrical
No. of particles: 40
No. of runs: 50
No. of iterations: 5000
(Ratnaweera et al., 2004)
Fully Informed Particle Swarm 67.03906
(57.48949)
389.118
(909.047)
Dimensions: 30
Topology: Square
Initialization: asymmetrical
No. of particles: 20
No. of runs: 50
No. of iterations: 3000
(Kennedy, 2003)
Self-Organizing Hierarchical Particle
Swarm Optimizer with Time-varying
Acceleration Coefficients
13.666
(11.006)
67.0844
(46.3846)
Dimensions: 30
Topology: Fully connected
Initialization: asymmetrical
No. of particles: 40
No. of runs: 50
No. of iterations: 5000
(Ratnaweera et al., 2004)
Adaptive Hierarchical Particle Swarm
Optimizer
19 (aprox)*
(--)
46.6737
(57.1728)
Dimensions: 30
Topology: --
Initialization: symmetrical
No. of particles: 40
No. of runs: 100
No. of iterations: 3000
(Janson and Middendorf, 2005)
Griewank Canonical-PSO 0.0106
(--)
0.0117472
(0.017055)
Dimensions: 30
Topology: Square
Initialization: asymmetrical
No. of particles: 20
No. of runs: 50
No. of iterations: 3000
(Kennedy, 2004)
Time-Increasing Inertia Weight PSO 18.1028
(--)
0.0216872
(0.0235111)
Dimensions: 30
Topology: Fully connected
Initialization: asymmetrical
No. of particles: 20
No. of runs: 20
No. of iterations: 2000
(Zheng et al., 2003)
Time-Decreasing Inertia Weight PSO 0.0182
(--)
0.0141078
(0.0176244)
Dimensions: 30
Topology: Fully connected
Initialization: asymmetrical
No. of particles: 20
No. of runs: 50
No. of iterations: 2000
(Kennedy et al., 2001)
Stochastic Inertia Weight PSO 0.0175
(0.018)
0.0207172
(0.0202154)
Dimensions: 30
Topology: Fully connected
Initialization: asymmetrical
No. of particles: 40
No. of runs: 50
No. of iterations: 5000
(Ratnaweera et al., 2004)
Fully Informed Particle Swarm 0.003534
(0.009502)
8.26762
(7.53187)
Dimensions: 30
Topology: Square
Initialization: asymmetrical
No. of particles: 20
No. of runs: 50
No. of iterations: 3000
(Kennedy, 2003)
Self-Organizing Hierarchical Particle
Swarm Optimizer with Time-varying
Acceleration Coefficients
0.01
(0.0035)
0.00256344
(0.00413481)
Dimensions: 30
Topology: Fully connected
Initialization: asymmetrical
No. of particles: 40
No. of runs: 50
No. of iterations: 5000
(Ratnaweera et al., 2004)
Adaptive Hierarchical Particle Swarm
Optimizer
0.004 (aprox)*
(--)
0.0060568
(0.00820175)
Dimensions: 30
Topology: --
Initialization: symmetrical
No. of particles: 40
No. of runs: 100
No. of iterations: 3000
(Janson and Middendorf, 2005)
Rastrigin Canonical-PSO 95.0581
(--)
68.7913
(21.8641)
Dimensions: 30
Topology: Square
Initialization: asymmetrical
No. of particles: 20
No. of runs: 50
No. of iterations: 3000
(Kennedy, 2004)
Time-Increasing Inertia Weight PSO 123.3182
(--)
74.174
(20.0151)
Dimensions: 30
Topology: Fully connected
Initialization: asymmetrical
No. of particles: 20
No. of runs: 20
No. of iterations: 2000
(Zheng et al., 2003)
Time-Decreasing Inertia Weight PSO 47.2941
(--)
43.0845
(10.2529)
Dimensions: 30
Topology: Fully connected
Initialization: asymmetrical
No. of particles: 20
No. of runs: 50
No. of iterations: 2000
(Kennedy et al., 2001)
Stochastic Inertia Weight PSO 69.7266
(20.7)
60.3939
(15.3708)
Dimensions: 30
Topology: Fully connected
Initialization: asymmetrical
No. of particles: 40
No. of runs: 50
No. of iterations: 5000
(Ratnaweera et al., 2004)
Fully Informed Particle Swarm 57.8667
(16.66862)
77.0502
(19.4693)
Dimensions: 30
Topology: Square
Initialization: asymmetrical
No. of particles: 20
No. of runs: 50
No. of iterations: 3000
(Kennedy, 2003)
Self-Organizing Hierarchical Particle
Swarm Optimizer with Time-varying
Acceleration Coefficients
0.044
(0.196)
12.8561
( 6.43465)
Dimensions: 30
Topology: Fully connected
Initialization: asymmetrical
No. of particles: 40
No. of runs: 50
No. of iterations: 5000
(Ratnaweera et al., 2004)
Adaptive Hierarchical Particle Swarm
Optimizer
30 (aprox)*
(--)
42.7036
(13.21)
Dimensions: 30
Topology: --
Initialization: symmetrical
No. of particles: 40
No. of runs: 100
No. of iterations: 3000
(Janson and Middendorf, 2005)
Schaffer's F6 Canonical-PSO 0.0006
(--)
0.00038864
( 0.00192325)
Dimensions: 2
Topology: Square
Initialization: asymmetrical
No. of particles: 20
No. of runs: 50
No. of iterations: 3000
(Kennedy, 2004)
Time-Increasing Inertia Weight PSO --
(--)
0.00437216
(0.00495917)
Dimensions: 2
Topology: Fully connected
Initialization: asymmetrical
No. of particles: 20
No. of runs: 20
No. of iterations: 2000

Not tested in reference
(Zheng et al., 2003)
Time-Decreasing Inertia Weight PSO --
(--)
0.00116591
(0.00318935)
Dimensions: 2
Topology: Fully connected
Initialization: asymmetrical
No. of particles: 20
No. of runs: 50
No. of iterations: 2000

Not tested in reference
(Kennedy et al., 2001)
Stochastic Inertia Weight PSO 0.0029
(0.004)
0.00233182
(0.00419163)
Dimensions: 2
Topology: Fully connected
Initialization: asymmetrical
No. of particles: 40
No. of runs: 50
No. of iterations: 1000
(Ratnaweera et al., 2004)
Fully Informed Particle Swarm 0.001675
(0.003485)
0.00296635
(0.00427008)
Dimensions: 2
Topology: Square
Initialization: asymmetrical
No. of particles: 20
No. of runs: 50
No. of iterations: 3000
(Kennedy, 2003)
Self-Organizing Hierarchical Particle
Swarm Optimizer with Time-varying
Acceleration Coefficients
0.01
(0.007)
0.00446932
(0.00489155)
Dimensions: 2
Topology: Fully connected
Initialization: asymmetrical
No. of particles: 40
No. of runs: 50
No. of iterations: 1000
(Ratnaweera et al., 2004)
Adaptive Hierarchical Particle Swarm
Optimizer
<< 0.0001 (aprox)*
(--)
3.90043e-09
(3.10343e-09)
Dimensions: 30
Topology: --
Initialization: symmetrical
No. of particles: 40
No. of runs: 100
No. of iterations: 3000
(Janson and Middendorf, 2005)
* Data taken from plots.

 

Solution Quality Over Time

Median solution quality over time
Function Fully Connected Topology Ring Topology
Griewank
Rastrigin
Rosenbrock
Schaffer's F6
Sphere

 

Run Length Distributions

Run-Length Distributions
Function Fully Connected Topology Ring Topology
Griewank
0.01%
Rastrigin
30.0%
Rosenbrock
10.0%
Schaffer's F6
0.0001%
Sphere
0.01%

References:

S. Janson and M. Middendorf. A Hierarchical Particle Swarm Optimizer and Its Adaptive Variant. IEEE Transactions on Systems, Man and Cybernetics--Part B Vol. 35 (6). pp 1272--1282. 2005.
J. Kennedy, R. Eberhart with Y.Shi. Swarm Intelligence. Morgan Kaufmann. 2001
J. Kennedy. Probability and Dynamics in the Particle Swarm. Proc. of the 2004 IEEE Congress on Evolutionary Computation. pp. 340--347. 2004
A. Ratnaweera, S. K. Halgamuge and H. C. Watson. Self-Organizing Hierarchical Particle Swarm Optimizer With Time-Varying Acceleration Coefficients. IEEE Transactions on Evolutionary Computation Vol. 8 (3). pp 240--255. 2004.
Y. Zheng, L. Ma, L. Zhang and J. Qian. Empirical Study of Particle Swarm Optimizer with an Increasing Inertia Weight. Proc. of the 2003 IEEE Congress on Evolutionary Computation. pp. 221--226. 2003