Ant Algorithms and Generalized Finite Urns
C. Leith · 2005
Researchers in various fields are constructing algorithms that mimic the desirable collective behaviour of pheromone trail laying biological agents. These ant algorithms, as they are commonly called, can be used to solve complex optimization problems, or act as a distributed control layer in a dynamic system. Our interest lies mainly with the latter application. Analyzing the effectiveness of ant-based algorithms is typically conducted by computer simulation alone. There are few mathematical studies that attempt to capture their seemingly random yet controlled behaviour. In this work, we build probabilistic models that guide our exploration of ant-based algorithms. We develop a generalized finite urn and investigate it in detail. We then abstract this base model into a Markovian process that is better suited to studying a dynamic environment, such as ant-based routing. Later, harnessing our mathematical findings, we propose a new framework for a general class of ant algorithms. Specifically, we introduce additional data structures that allow us increased control over the decoupling of ant actions and the underlying system that they indirectly manage. Finally, to complement our mathematical approach, we also evaluate the performance of our modified ant algorithm implementation through computer simulation.