Finding Social Landscapes for PSOs via Kernels
W. B. Langdon
Paper presented at CEC-2006
- Definition of social landscape
- Using genetic programming to evolve kernels (filters) to transform original landscape into social landscape.
- Experiments on Rastrigin.
- Results: equivalent landscape is smoother than original.
PSO succeeds if filtered landscape easier original
Individual landscape→Social Landscape
- In some ways groups, schools, swarms, etc. behave like macro-organisms. How can we model this?
- Know “fitness” seen by particles; what is the landscape effectively seen by whole swarm?
- Use convolution with kernel to transform optimisation benchmark into social landscape.
- A “macro-individual” sees only the social landscape and so behaves like the pop average
Evolution of Social Landscape
Top: original landscape
Below: Equivalent social landscape given by convolution of evolved kernel and original landscape
Genetic Programming of Kernel
- tinyGP. Evolve function of x using +-×÷ and constants. E.g. -1/(188x+1/(0.39+x))
- Steady state pop=1000 (Rastrigin). Binary tournaments, 10% crossover. 2% point mutation per node. 100 generations.
- Fitness revaluated every tournament.
- I.e. run PSO five times; run hill-climber on convolution of kernel and Rastrigin 5 times. Mutate etc. kernel with lower RMS error.
- The hill climber move at each step is given exactly by the current gradient.
- Gradient calculated by convolving gradient kernel evolved by GP with Rastrigin.
- Note: for simplicity, speed, stability etc. GP actually evolves the gradient of kernel, rather than the kernel itself.
- Fixed learning rate: 1.
- Speed limited Gbest PSO. Swarm size=5. No constriction. 1-dimensional Rastrigin
- Start swarm well away from optimum.
- Track position of swarm centre in five PSO runs.
- GP fitness function how closely does simple hill climber moving on new landscape track centre of PSO population.
Rastrigin set up as a maximisation problem. Global optimum at the origin.
- Comparison of first five PSO test runs on Rastrigin with five hill climbing runs Training RMS error 0.47 v. test error 0.58
Rastrigin PSO Kernel
PSO Test error 0.66 (sd 0.29)
Movie showing movement of a five member
PSO on Rastrigin and the corresponding
movement of the hill climber on the equivalent social landscape.
Note the RMS error between the
center of the PSO and the position of the hill climber
(both shown with blue squares) is on average only 0.66
when started from random positions not used in training the GP.
GA Test Error 0.86 (sd 0.35)
Movie showing the location of every GA individual
(and the values of its bits, red or blue)
versus the location of the hill climber on the equivalent
social landscape. Again note closeness of match of the two squares.
- Often people claim that their optimiser (PSO, GA...) works because the landscape “seen” by the population is “smooth”. Here we have graphs of the equivalent landscapes (and they are smooth!)
- May be mathematical kernels offer way of modelling the combination of 100++ individual sights, thoughts, actions by members of a shoal to give its gross properties.
Extended Particle Swarms
- Social landscapes exist.
- (At least in these cases) they are algorithm and problem specific.
- I.e. the social behaviour of a GA need not be the same as that of a PSO.
- In at least some cases they can be readily found.
25 July 2006