Computer Science

- 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
- Conclusions
- Where does this lead next?

- 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 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.

The next picture shows the PSO, starting from the same positions as the DE above, finding an optimum in only three generations.

- 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.

DE 900 evaluations but PSO (vmax=10) does not find solution

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.

PSO (vmax=10) does not find solution

- 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.

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