Evolving Optimisation Benchmarks

W. B. Langdon
Computer Science
University of Essex Logo

Paper presented at CEC-2005 Volume 1, Pages 81-88


Why Evolve Benchmarks?

GP driven by difference in Optimiser 1 - Optimiser 2

GP outer loop; fitness Optimizer 1 - Optimizer 2


PSO beats Differential Evolution

DE generations 0-1500 (0.33 -0.32x -2.32y)y
In quarter of runs DE fails to find optima, even after 1500 generations. From the random starting points in the above example, the whole differential evolution population converges on the smaller sub-optimal peak. While particle swarm optimiser always finds an optimum.
   The next picture shows the PSO, starting from the same positions as the DE above, finding an optimum in only three generations.

PSO > Differential Evolution

Particle Swarm Optimiser (Pop=30, Vmax=10) (0.33 -0.32x -2.32y)y


Differential Evolution > PSO

Differential Evolution Generations 0-44 0.0003(0.11+x+0.7y)

DE 900 evaluations but PSO (vmax=10) does not find solution
The global optimum proves to be too small for the PSO (without constriction) to find reliably. While the gradient leads DE to the optimum every time.
   Note DE tends to overshoot the optima and so many DE fitness evaluations are wasted. This suggests DE might have problems with "cliff edges", such are expected in constrained optimisation problems.

Differential Evolution > PSO

PSO (no constriction) Particle 0 Generation 0-44 0.0003(0.11+x+0.7y)

PSO (vmax=10) does not find solution
The above animation shows a single PSO particle. (The other 29 members of the swarm behave similarly.) Note that it oscillates about its own and the global best (coloured dots). While these do move closer to the optimum, (in this run) they never reach it.

Some lessons for DE, PSO, etc



PSO Constriction 0.7

Note 0.0003(0.11+x+0.7y) landscape can be easily solved by PSO if constriction is used.
PSO (no constriction) Particle 17 Generation 0-27 0.0003(0.11+x+0.7y)

W.B.Langdon 6 September 2005 (last tweak 12 Oct)