Speculative Evaluation in Particle Swarm Optimization

摘要

Particle swarm optimization (PSO) has previously been parallelized only by adding more particles to the swarm or by parallelizing the evaluation of the objective function. However, some functions are more efficiently optimized with more iterations and fewer particles. Accordingly, we take inspiration from speculative execution performed in modern processors and propose speculative evaluation in PSO (SEPSO). Future positions of the particles are speculated and evaluated in parallel with current positions, performing two iterations of PSO at once. We also propose another way of making use of these speculative particles, keeping the best position found instead of the position that PSO actually would have taken. We show that for a number of functions, speculative evaluation gives dramatic improvements over adding additional particles to the swarm.