A general purpose Heuristic Optimization algorithm: Particle Swarm Optimization

2010 March 9
by Daniel Lakeland

Today I read about Particle Swarm Optimization (or see the wikipedia article). It's a member of the general class of stochastic search algorithms. The basic idea is that some particles fly through the possible search domain, and they communicate to each other about what they find. The particles are attracted to "better" regions by having a memory of the best region they have seen, as well as communications between groups of particles about the best region that other particles have seen.

This is what you might call a 'metaheuristic', in other words a seed idea that is the basis for a general class of algorithms. The advantage of this kind of system is that it's relatively easy to program and produces relatively robust and efficient searches through high dimensional parameter spaces.

I'm thinking of using particle swarms and radial basis functions together to solve an optimization problem involving choosing a control strategy for a dynamical system. The idea is to converge simultaneously on an optimum strategy which fits the constraints imposed by the dynamical system (some integro-differential equations). Given a strategy (which is specified by a set of functions of two variables, A and t), there is a set of implied surfaces that solve the I-D equations. These surfaces are then combined and the result is integrated to get an overall cost. The I-D equations should be solved on a grid of around 100 to 300 points, and there are several equations, leading to several hundred dimensions. I had considered using a genetic algorithm to do the search, but the particle swarm technique sounds appealing.

One appealing thing is the idea of converging simultaneously on the optimum and the I-D solution. For each trial strategy it is moderately straightforward but extremely time consuming to calculate a solution to the I-D equations. And for all but the "best" strategy, that time is wasted. If you're seeking out an optimum, spending a lot of time finding the coefficients that satisfy the equations at a non-optimal intermediate value seems like a waste.

No comments yet

Leave a Reply

Note: You can use basic XHTML in your comments. Your email address will never be published.

Subscribe to this comment feed via RSS