C Iacopino & P L Palmer
In the last decade Ant Colony algorithms have received increasing attention due to their flexibility and adaptability to different applications. Despite these advantages, their design and analysis are still critical issues; research on formal methods could increase the reliability of these systems and extend their applications to critical scenarios such as space or military.
This paper aims at exploring the potential of formal modelling techniques already developed for studying the dynamical systems. The benefits of these techniques are shown in the analysis of a generic ant colony algorithm applied to problems modelled as binary chains. The theoretical model developed is able to give new insights on the overall system dynamics, predicting the system long-term behaviours and specifically the influence of the pheromone perception parameter on the system emergence. This paper first offers a complete stability analysis for a basic problem providing an easy description of the key concepts before generalizing to problems with n-node, allowing its application to real problems. The picture of the system dynamics is then completed by a convergence time analysis, which is necessary to draw sensible conclusions.
Update 21/11/12; final version