Toward the formal foundation of Ant Programming

This paper develops the formal framework of ant programming with the goal of gaining a deeper understanding on ant colony optimization and, more in general, on the principles underlying the use of an iterated Monte Carlo approach for the multi-stage solution of combinatorial optimization problems. 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 we adopt 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 such as state, representation, and sequential decision process under incomplete information.In M. Dorigo, G. Di Caro, and M. Sampels (Eds.), Ant Algorithms, 3rd International workshop, ANTS 2002. Springer, Berlin, GermanySCOPUS: cp.k