Colonia de hormigas

Expert Systems with Applications xxx (2010) xxx–xxx

Contents lists available at ScienceDirect

Expert Systems with Applications
journal homepage: www.elsevier.com/locate/eswa

A software model to prototype ant colony optimization algorithms
Roberto Fernandes Tavares Neto *, Moacir Godinho Filho
Industrial Engineering Department, Federal University of São Carlos (UFSCar), RodoviaWashington Luis, Km 235, São Carlos – SP, Brazil

a r t i c l e
Keywords: Ant colony system Software model ACS AS MMAS

i n f o

a b s t r a c t
The study of multi-agent systems usually begins by implementing a base-algorithm, which is changed as required by the aim of the research. In this context, carrying out different algorithms, which have already been established, is not a trivial task asit requires implementing these algorithms. This paper presents a software model that allows one to prototype variations of the Ant Colony Optimization metaheuristic. This model can be used to avoid implementations in duplicity, allowing, with less effort, the generation of different algorithms to be used on the same problem. Results shown that, specially for more elaborated algorithms, theadoption of the proposed software model reduce significantly the coding effort required. Crown Copyright Ó 2010 Published by Elsevier Ltd. All rights reserved.

1. Introduction The Ant System (AS) algorithm was introduced in 1991 by Colorni et al. Since then, a lot of research has been done by applying ants’ behavior to classic and new problems reported in the literature. Gambardella and Dorigo(1996) introduced the Ant Colony System (ACS) algorithm improving the original AS algorithm and producing better results to solve combinatory problems. Several researchers have adapted the heuristics proposed by Gambardella and Dorigo (1996) to specific problems. ACS was first used to solve the classical Traveling Salesman Problem (TSP), symmetric and asymmetric, (Dorigo, Maniezzo, & Colorni, 1996;Gambardella & Dorigo, 1996). After that, several other applications were developed, such as the Sequential Ordering Problem – SOP, (Gambardella & Dorigo, 2000), the Capacitated Vehicle Routing Problem – CVRP, originally solved by Bullnheimer, Hartl, and Strauss (1997), scheduling problems (Bauer, Bullnheimer, Harlt, & Strauss, 2000; Blum, 2002; Stützle & Hoos, 2000) among others. For moreinformation, Dorigo and Stutzle (2004) present a sample of more than 60 applications of AS and ACS. According to Stutzle and Linke (2000), all of this research is based on the same core algorithm with small modifications incorporated in order to include the new characteristics, maintaining the basic functions of the ant colony algorithm. However, for each implementation, a different computational tool isused, so it is common to find mentions of codes written in C, C++, JAVA or even using mathematical processing tools such as Matlab, depending on the availability of resources and technical preferences of each researcher. This lack of standardization in code structure is a

* Corresponding author. Tel.: +55 16 3351 9540; fax: +55 16 3351 8240. E-mail addresses: tavares@dep.ufscar.br (R.F. TavaresNeto), moacir@dep.ufscar.br (M. Godinho Filho).

problem usually found for researchers who want to apply and to compare different algorithms. Within this context, this paper proposes and implements a software model that facilitates information exchange between researchers who use the AS algorithm and its variations. Analyzing the necessary changes in the original core of the AS for theimplementation of the different heuristics, it is possible to establish a relationship between them and their classification. Using the proposed software model, the creation of new algorithms from the initial AS core is made easier, since all the support functions and the basic behavior is already validated. At the same time, implementing different algorithms with the same input data representation model...