AntNet

ACO features a multi-agent organization, stigmergic communication among the agents, distributed operations, use of a stochastic decision policy to construct solutions, stigmergic learning of the parameters of the decision policy. It has been applied with success to a large variety of combinatorial problems. AntNet has been the first ACO algorithm for routing in packet-switched networks. My first work on AntNet, under the supervision of Prof. Marco Dorigo, dates back to 1997.

AntNet, as well as most of the other ACO routing algorithms designed after AntNet, exhibits a number of interesting properties: it works in a fully distributed way, is highly adaptive to network and traffic changes, uses lightweight mobile agents (called ants) for active path sampling, is robust to agent failures, provides multipath routing, and automatically takes care of data load spreading.

AntNet's performance has been extensively tested in simulation, considering different networks and traffic patterns, and compared to several state-of-the-art routing algorithms. In the great majority of the considered situations, AntNet has largely outperformed all its competitors, showing excellent adaptivity and robustness. AntNet has been also tested in small physical networks, confirming the good performance also in these real-world tests.

The complete description of all different versions of the algorithm (my thesis):

My thesis contains a comprehensive description of AntNet and of other routing algorithms I've designed, as well as of related work.

Di Caro G.A. Ant Colony Optimization and its application to adaptive routing in telecommunication networks PhD thesis in Applied Sciences, Polytechnic School, Université Libre de Bruxelles (ULB), Brussels, Belgium, 2004 (Supervisor: Prof. Marco Dorigo).

Since the thesis is quite long and deals both with the general definition and study of the ACO metaheuristic and with its specific application to network routing, here you can find a link to the two chapters where AntNet is defined and its experimental results are reported.
As a shortcut, a less detailed description and discussion of the algorithms can be found in the two papers reported below.
Please refere exclusively to my thesis or to those two papers if you want to implement and discuss about AntNet, all the other older papers have to be considered as out-of-date.

The original journal paper:

The original journal paper which describes AntNet is the following one, although there were some previous conference papers describing preliminary versions of the algorithm:

Di Caro G., Dorigo M., "AntNet: Distributed Stigmergetic Control for Communications Networks", Journal of Artificial Intelligence Research (JAIR), Vol. 9, Pag. 317-365, 1998.

The conference paper with the description of the latest version of AntNet:

If you plan to implement AntNet for comparison studies, please refer either to my thesis or to the algorithm described in the paper indicated below, which contains some small but significant improvements over the version described in the JAIR paper above.

Di Caro G., Dorigo M., "Two Ant Colony Algorithms for Best-Effort Routing in Datagram Networks" , Proceedings of PDCS'98 - 10th International Conference on Parallel and Distributed Computing and Systems, Las Vegas, Nevada, October 28-31, 1998, (also Technical Report IRIDIA 98-09).

Software implementations of AntNet:

Don't ask me about my original code! I implemented the code for my own personal use, such that the code has no comments, no user manual, makes use of commercial libraries, etc. However, some software implementations of AntNet for popular network simulators are around:

Muddassar Farooq made an implementation of AntNet for OmNet++. The implementation is very close to the original algorithm, but I didn't fully checked and tested the code.

Lavina Jain made an implementation of AntNet for NS-2 (that can be also downloaded here). Starting from Jain's code, Richardson Lima has released a revised and updated version of AntNet for NS-2.33. Since I'm not an NS-2 user, I haven't checked these implementations, but I guess the Lima's implementation can be used as a good starting point. If you plan to use Lima's code, please feel free to contact me to check/improve the quality of the implementation.

At IDSIA, Frederick Ducatelle and Liliana Carrillo made an implementation of AntNet for QualNet (ver. 3.8), the commercial network simulator from Scalable Network Technologies. The implementation has not been fully tested and the code needs to be polished. However, it works and can be definitely used as a starting point (anybody willing to check, improve, or port this code to newer QualNet versions, is most welcomed!).

The Ant Colony Optimization metaheuristic

The original papers:

In 1999, we defined the metaheuristic as an a posteriori metaheuristic, taking into account the initial seminal work of Dorigo et al. (dating back to 1991) and the number of algorithms designed after this work. The reference papers where ACO is formally defined and extensively discussed are the following two (they also contain loads of reference to practical ACO implementations):

Dorigo M., Di Caro G., Gambardella L.M., "Ant Algorithms for Discrete Optimization" , Artificial Life, Vol. 5, N. 2, 1999

Dorigo M., Di Caro G., "The Ant Colony Optimization Meta-Heuristic", in Corne D., Dorigo M., Glover F., New Ideas in Optimization, McGraw-Hill, 1999

Comprehensive and up-to-date information sources:

My thesis contains an up-to-date/novel definition of ACO, as well as extensive discussions and review of implementations. A new terminology is introduced, stressing the relationship between ACO and other domains like reinforcement learning and Markov decision processes:

Di Caro G.A. Ant Colony Optimization and its application to adaptive routing in telecommunication networks, PhD thesis in Applied Sciences, Polytechnic School, Université Libre de Bruxelles (ULB), Brussels, Belgium, 2004.

The other main reference is the recently published book on ACO: Dorigo M., Stuetzle T., Ant Colony Optimization, MIT Press, 2005

Loads of additional information can be found in the official Ant Colony Optimization page.