مدل نرم افزار نمونه ی اولیه الگوریتم بهینه سازی کلونی مورچه

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 as it 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, the adoption of the proposed software model reduce significantly the coding effort required.

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 et al., 1996 and Gambardella and 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 et al., 2000, Blum, 2002 and Stützle and Hoos, 2000) among others. For more information, 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 is used, 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 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 the implementation 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 facilitates the evaluation of the use of techniques that are already available in different classes of problems. Similar studies can be found in the literature, for example Andreatta, Carvalho, and Ribeiro (2002), who present a software model for the creation of local search heuristics; Laguna (1997), who present a software for optimization with genetic algorithms; and the projects “Genetic Algorithms Framework” (GA-FORK, 2008) and “COIN” (Hunsaker, 2008) which provide respectively a multiplatform software model to solve problems using genetic algorithms and a computational infrastructure for operational research problems. Nonetheless, no software model applied to design prototypes of systems based on the ant colony metaheuristic was found in the literature. In order to achieve the proposed goals, the algorithms Ant-Cycle, Ant-Density, and Ant-Quantity, proposed by Colorni et al., 1991 and Dorigo et al., 1996, were used. The results obtained from surveys (Dorigo and Blum, 2005 and Stovba, 2005) will be the basis to show how the system proposed can be used for the implementation of variations of the single colony AS. In addition, using the paper of Ellabib, Calamai, and Basir (2007) we demonstrate how to implement AS multiple colony algorithms using the software model presented. Results show that when the proposed model is used, the implementation effort could be reduced significantly. As an example, the implementation of the Max–Min Ant System (Stützle & Hoos, 2000) required only three simple methods to be written while without the software model, 40 methods were necessary to be written. This article is structured as follows; Section 2 presents the definition of the AS algorithm, and its major characteristics and variations. Section 3 presents the software model proposed. Section 4 presents the project choices for the implementation of the structure introduced, the necessary changes for the implementation of some algorithms described in Section 2, and also the results of a set of tests to validate the implemented procedures. The last section presents some final considerations and ideas for further research.

This study proposed a software model for the quick prototype of multi-agent heuristic systems based on ant colony algorithms. The most popular AS algorithms in the literature were used as a basis. The focus was on the definition of a minimum set of independent entities which could establish a set of behaviors present in the algorithms studied. During the development of the architecture proposed, it could be seen that there was gain in terms of computational costs when the information about problem to be solved is given to the entity Ant. The execution of the taboo list – that is, the memory of the graph nodes already traversed by the ant – is faster when the size of the problem is established. Implementing the structure proposed by the object-orientation paradigm, the concept of class inheritance allows the code reuse, making the evolution of new algorithms a much simpler task. Establishing the rules that are modified between the evolutions of AS algorithms, it is possible to carry out a comparative analysis such as the one in Chart 7. The definition and initial validation of the computational framework allow the proposition of a study to be developed further: its implementation in dedicated systems. The implementation of this structure in several dedicated systems seemed feasible. A bigger set of tests is necessary. Another work to be developed in the future is the implementation of a bigger number of algorithms using the same software model. Although this study aimed at validating the computational structure, it is inevitable that the next steps are the inclusion of other algorithms evolutions based on ants behavior available in the literature. Finally, it can be said that the software model proposed allowed the rapid implementation and characterization of complex algorithms such as the MMAS and even the multiple colony structures with a reduced effort – the implementation of only 2–13% of the methods necessary for system functioning (disregarding the Mac-He algorithm, which did not require any implementation, but only a change in the configuration files). Therefore, the proposed prototype design of a system based on AS algorithms was successfully achieved.