Evolving Optimisation Benchmarks
W. B. Langdon
Paper presented at CEC-2005 Volume 1, Pages 81-88
- Why evolve optimization benchmarks?
- How? Use standard GP except evolving problems
- Fitness for GP is difference between performance of one optimiser above the other.
- PSO out performing Differential Evolution
- DE out performing Particle Swarm Optimisation
- Where does this lead next?
Why Evolve Benchmarks?
- Analysis of Optimisation algorithms is very hard. Easier to code than to understand.
- Often use experimental evaluation on benchmark problems.
- How realistic are benchmarks? Some old.
- New approach turns this on its head. Design problems to show strengths and weaknesses by comparing rival optimisers.
GP driven by difference in Optimiser 1 - Optimiser 2
PSO > DE
- GP steady state pop=1000, binary tournaments, 90% crossover, 2% point mutation per node, generation 10. PSO/DE initialisation range=±10.0
- Fitness = DE evals - PSO evals
- Evolved (0.33 -0.32x -2.32y)y
- PSO (vmax=10) always solves. DE only solves 77 times in 100 runs.
PSO beats Differential Evolution
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
DE > PSO
- GP steady state pop=1000, binary tournaments,10% crossover, 2% point mutation per node, generation 6. PSO/DE initialisation range=±10.0
- Evolved 0.0003(0.11+x+0.7y)
- DE always solves. PSO (vmax=10) only solves 6 times in 50 runs.
Differential Evolution > PSO
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 (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
- New list in new paper (For full details see papers).
- Set population size according to problem difficulty.
- PSO constriction (similar effect in DE) can limit search, so PSO and DE both need to be started near optima.
- Vmax, constriction etc. can control exploration v. exploitation of PSO. PSO may not focus search on narrow global optima.
- DE and PSO may not perform well on constrained optimisation problems due to "cliff edges".
- DE can be deceived
- Gradient search easily foiled by badly behaved problems Heuristics built into general algorithms can fail on specific problems.
- GP can evolve simple benchmarks which demonstrate advantages and weaknesses of pairs of optimisers.
- The technique is general and can be applied to any pair of optimisers.
- Have used number of fitness evaluations, but could use other objectives, such as best solution found within a resource limit.
- Provided we have an objective way of comparing optimisers, this could be applied to multi-objective optimisers.
PSO Constriction 0.7
Note 0.0003(0.11+x+0.7y) landscape can be easily solved by PSO if constriction is used.
W.B.Langdon 6 September 2005