Fitness for GP is difference between performance of one optimiser above the other.
PSO out performing Differential Evolution
DE out performing Particle Swarm Optimisation
Conclusions
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.
Conclusions
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.
end
PSO Constriction 0.7
Note 0.0003(0.11+x+0.7y)
landscape can be easily solved by PSO if constriction is used.
