When I saw that the latest Informs blogging challenge was OR and food, I immediately thought of the diet problem and minimizing grocery bills while maximizing nutrition (a knapsack problem, perhaps). But I also thought about Ant Colony Optimization which I have been interested in incorporating into my optimization toolbox for some time now. Ant Colony Optimization (ACO) is an optimization algorithm that at its very core is about food – finding the optimal path from an ant colony to a food source.
Ants are well-known in popular culture as being very strong (they can lift 20 times their weight — or a car if they were human!) but it is their food foraging skills that are the basis for ACO. An ant colony works together to efficiently find food sources, with scavengers laying pheromone paths to food sources that other ants in the colony can follow. As additional ants use this trail to successfully find food, they reinforce it. When a food source is exhausted, ants following the path will no longer find food and thus stop reinforcing the path, allowing it to expire. This allows ACOs to adapt to changes in the original problem without requiring a restart of the algorithm.
Ant Colony Optimization is similar to my all-time favorite metaheuristic, the Genetic Algorithm, since its optimization is based on biology (evolution in GAs vs. ant colony behavior in ACO) and it uses a population of entities (chromosomes and genes in GAs vs. ants in ACO) to find a solution. And like GAs, the solution representation is vital to the success of an ACO. There has to be a way to correlate an efficient path to food with a good solution in the original problem.
I am still in the introduction stage with Ant Colony Optimization and have not had a chance to code up an example problem to see the algorithm in action. But I have high hopes because I learned from Genetic Algorithms that Mother Nature is a pretty good optimizer. Hopefully in the next few weeks I’ll have time to put together a basic ACO algorithm and post a follow-up post comparing its performance with other optimization techniques. In particular, I have a few scheduling applications that are reduced to a set partitioning MIP currently solved with Cplex. I have been trying to development a GA as an alternative solution method but haven’t come up with an efficient chromosome representation for large-scale production problems. ACO has been used for a variety of problems, including set partitioning problems, so this is one of the first problems I will tackle.
Have you ever used Ant Colony Optimization and if so, what types of problems did it work well for? Do you have any “lessons learned” for Operations Researchers just getting started with ACO?
This blog post is a contribution to INFORMS’ monthly blog challenge. INFORMS will summarize the participating blogs at the end of the month.