Mauro BIRATTARI, Gianni DI CARO and Marco DORIGO
For a Formal Foundation of the Ant Programming Approach to Combinatorial Optimization
Abstract:This paper develops the formal framework of ant programming with the goal of gaining a deeper understanding on ant colony optimization, a heuristic method for combinatorial optimization problems inspired by the foraging behavior of ants. Indeed, ant programming allows a deeper insight into the general principles underlying the use of an iterated Monte Carlo approach for the multi-stage solution of a combinatorial optimization problem. Such an insight is intended to provide the designer of algorithms with new categories, an expressive terminology, and tools for dealing effectively with the peculiarities of the problem at hand.
Ant programming searches for the optimal policy of a multi-stage decision problem to which the original combinatorial problem is reduced.
In order to describe ant programming, the paper adopts on the one hand concepts of optimal control, and on the other hand the ant metaphor suggested by ant colony optimization. In this context, a critical analysis is given of notions as state, representation, and sequential decision process under incomplete information.