Global Optimization, and … Ants?

“Find the best solution” — it’s one of those statements that can rapidly spiral into chaos depending on what exactly one means when they say “best”. For example, “what is the largest number in this list?” is easy, but “what is the best movie of the year?”, well, not so much, right?

In math, Global optimization is what we call the the task of finding the best set of conditions to achieve the objective. It also happens to be one of the parts of an area called nonlinear programming (but that’s a different topic).

It turns out that Swarm Intelligence — emergent behavior that arises from a few simple rules — is actually a pretty good way to come up with the solution. (•). It comes from the way ants search for food, and as algorithms go, it’s really quite straightforward

1. 1. Each ant (agent) picks a random direction and heads out.
2. 2. If it finds something, it tells its buddies, and starts bringing pieces back home.
3. 3. If it doesn’t find anything, it asks its buddies if they found anything. If they did, it joins them on retrieving the food.
4. 4. If neither found anything they both pick a new random direction.

Now, replace “searching for food” with “work on a problem”, and you’ve got a pretty good implementation of an approach to global optimization called Stochastic Differential Search. The algorithm is almost a straight implementation of the above (replace “ants” with “agents”, and “food” with “work”).

1. 1. Each agent picks a randomly chosen candidate solution to the problem at hand.
2. 2. The agents then share the hypothesis, and tentative results with their immediate buddies, and compares results.
3. 3. They then jointly start working on the more promising hypothesis, pending information retrieved from other buddies.
4. 4. If the solution bombs, the agents pick a new random candidate.

It’s actually a remarkably effective solution, and has uses in all sorts of areas, from locating cell towers, object recognition, and more. Mind you, it does suffer from the “No Free Lunch” problem, the better the algorithm is at solving a specific type of problem, the worse it gets in other areas (••). Ah well, you can’t have everything…

(•) For an example of Swarm Intelligence in bridge building, check out this article.
(••) “Stochastic Diffusion Search: A Comparison of Swarm Intelligence Parameter Estimation Algorithms with RANSAC” by Howard Williams and Mark Bishop