Abstract: This paper describes an Object-Oriented framework written in Java designed to implement Ant Colony Systems. Thanks to Object-Oriented methodology the proposed framework can be reused and adapted to implement Ant Colony Systems able to solve specific problems such as the Travel Salesman Problem, the Multicasting Problem in a Network, the Steiner Problem on Networks and so on.
In the first part of this paper we introduce the framework showing how it has been designed and what are the base abstract classes the composed it. In the second part we describe how we adapted the framework to solve the Travel Salesman Problem showing how we specialized the base classes and what are the results we found. Finally in the third part we further specialize the framework to solve the Multicasting Problem in a Network, seen as an instance of the Steiner Problem on a Network. We describe how the Steiner problem can be solved by using an Ant Colony System and how the classes for the Travel Salesman Problem can be adapted to solve it, showing, at the end, the results we found.

Source code available on github: Java-Ant-Colony-System-Framework

Introduction

It’s common opinion that Object-Oriented Programming is a good methodology to develop modular software that can be adapted and reused more times with few changes. Usually, such a modeling and programming methodology starts by designing an abstract model which cover the main and more general aspects of a problem, seen in its most general instance, and goes on with several specializations derived from the starting model, each of them solving a particular instance of the problem. In other words, if the main model and the derived ones have been designed with a high level of modularity and abstraction they can be reused, or sometimes adapted, for other similar problems with very few, (or, in the best case, without), changes dropping down the costs of the software development.
Java language, more then its competitors and predecessors such as C++, Smalltalk, etc., supplies a simply and elegant approach in designing and developing software using such a methodology and has contributed to diffuse, more than before, the use of the Object-Oriented Programming.
Following this philosophy we carried out a Java Framework for Ant Colony System in order to have a basic skeleton with an high level of abstraction by which one can implement and solves problems, in the set of problems solvable by ACS, without writing bulky lines of code, but simply specializing with few lines, the basic classes supplied by the framework.
In the next paragraphs we’ll show the classes that compose the framework. In the subsequent chapters we’ll specialize the framework to solve the Travel Salesman Problem (TSP) [1] and, finally, we further derive from the classes for TSP to create a specialized model able to solve the Multicasting Problem [3] in an actual network seen as an instance of the Steiner Problem on a network [2].

Java Ant Colony System Framework

Referring to the paper wrote by M. Dorigo and L.M. Gambardella [1], Ant Colony System consists of a set of cooperating agents called ants that cooperate to find a good solution for optimization problems on graphs similar to the Travel Salesman Problem. Each single ant reflects a very trivial behavior: it simply goes from a node to another across an arc, but when all ants cooperate, like actual ants do in a real colony, the whole system reveals an intelligent behavior, as much as it is able to find a good solution for the TSP.
In this work we took the same assumptions made in the mentioned paper:
- the problem is represented by a graph G = (N, A) where N is the set of nodes and A is the set of arcs which connect the nodes;
- cooperation between ants is made by using an indirect form of communication mediated by pheromones they deposit on the arcs of the graph representing the problem;
- the functions cost measure d(r, s) and desirability measure t(r, s), where r, s ε N, are defined on the graph;
- the rules defining the behavior of the ants and the whole colony are the same as those proposed in the mentioned paper:
- a State Transition Rule which brings the concrete ant from a node to another across an arc;
- a Local Updating Rule which updates the pheromones deposited by the ant on the arc it walked in;
- a Global Updating Rule which updates the pheromones deposited on the arcs when an ant ends its trip;
In addition we defined a Comparison Function which says if a given path is better then another and an End Of Activity Rule which specifies when an ant has completed its trip.
Following those assumptions, we started to design our framework. We considered three entities which play together in an Ant Colony System: a set of ants, an ant colony which coordinates all ants and a graph which defines the topology of the space where the ants move (or, from another point of view, where the colony lives).
Then, we mapped these entities into an object model using the Object-Oriented methodology and we obtained the object model shown in the Picture 1 using UML (version 1.3) notation.

Picture 1 Object Model of the JACSF in UML (version 1.3) notation.

The framework is composed by three classes:

- Ant is an abstract class which implements the general behavior of an artificial Ant.It must be specialized, in the context of the specific problem, in order to behave as a concrete Ant. As can be seen in the Picture 1, the abstract methods which must be implemented in a concrete derived class are stateTransitionRule, localUpdatingRule, compare and end which correspond to the rules mentioned above. The method start launches a thread in which the ant works. This means that each ant works in its own thread in parallel with all others giving to ACS the parallelism shown by actual ant colonies. The other class methods and members, such as init, m_nCurNode, etc., are used internally to perform the activity of the ant. The algorithm which drives the artificial ant during its trip is shown in Picture 2.  Picture 10 in appendix A proposes a possible implementation in Java.

- AntColony is an abstract class implementing the general behavior of an Ant Colony System. It must be specialized, in the context of the specific problem, in order to implement a concrete Ant Colony. The abstract methods which must be implemented in a concrete derived class are createAnts and globalUpdatingRule. The first one creates the instances the class Ant which walk on the edges of the graph. The second one matches with the corresponding rule mentioned above. The other class methods and members, such as start, iteration, m_ants, etc., are used internally to perform and track the activity of the whole ant colony. The algorithm which directs the colony is shown in Picture 3. Picture 9 in appendix A illustrates a possible implementation in Java.

- AntGraph is a class which realizes the features of a graph specific for Ant Colony Systems. It supplies the values for the cost measure d(r, s) and for the desirability measure t(r, s) and gives a method to update the value t(r, s). Because the ants work really in parallel they access asynchronously and unpredictably to the graph. To avoid that an ant tries to read from the graph while another are writing on, the accesses to AntGraph objects are synchronized by using the synchronization mechanism supplied by Java language.

The resulting framework, that we named Java Ant Colony System Framework or JACSF,  forms an Application Programming Interface (API) which allows straightforwardly to realize artificial ant colonies in Java. In fact, by design, is necessary to create two classes, derived respectively from Ant and AntColony, implementing only the Transition Rule, Local Updating Rule, Global Updating Rule, End Of Activity and the Comparison Function in the related abstract methods, leaving out definitely all the aspects related to the algorithms that drives the general activities of the ants and the colony which has been implemented once and for all in the base classes of the framework. 

Picture 2 Algorithm of a single artificial ant

Picture 3 Algorithm of an Ant Colony

The source code of the proposed Ant, AntColony and AntGraph classes and the API’s reference manual are available for download at: http://www.ugochirico.com.
In the next paragraphs we’ll see how the classes Ant and AntColony have been specialized to solve TSP and the Multicasting Problem in a network.          

JACSF applied on TSP

To apply JACSF to the Travel Salesman Problem we took the instance of ACS, defined in [1], solving the Travel Salesman Problem and we implemented it using JACSF.
The Picture 4 shows the equations, described in [1], which define the State Transition Rule (Eq. (1) and (2)), the Local Updating Rule (Eq. (3)) and the Global updating Rule (Eq. (4))

Picture 4 Set of rules of ACS as described in [1]. (1) and (2) compose the State Transition Rule; (3) is the Local Updating Rule; (4) is the Global Updating Rule; J_k is the set of nodes not yet visited by the ant k.

We designed two concrete classes Ant4TSP and AntColony4TSP, derived respectively from the classes Ant and AntColony, which implement the transition and updating rules described above. The object model of the resulting class hierarchy, reported in UML notation, is shown in Picture 5.

Picture 5 Object Model derived from JACSF for TSP

AntColony4TSP implements in the method globalUpdatingRule the rule (4) in Picture 4 and defines in the member variable A the value of the parameter α. Picture 11 in appendix A shows the implementation of such a method in java.

Ant4TSP implements in the method stateTransitionRule the State Transition Rule mixing the rule(1) and (2) in Picture 4 while in the method localUpdatingRule it implements the rule (3). In the member variables B, R, Q0 it defines respectively the values for the parameters β, ρ, q₀. Picture 12and Picture 13  in appendix A show a possible implementation of both methods in java. The source code for Ant4TSP and AntColony4TSP classes is available at: http://www.ugochirico.com.

As suggested in [1] we set A = 0.1, B = 2, R = 0.1. The parameter q₀ has been set to Q0 = 0.8 because, after several tests, we found a better behavior of the colony with this value. Finally, the initial value for τ(r,s), τ₀, has been set using the Eq. (5) and the starting node for each ant is selected randomly.

Picture 6 Initial value for τ(r, s)

In order to test the proposed system we launched a colony composed by 10, 20 and 30 ants on a graph containing 50 cities for 2500 iterations. The results we found, shown in the Table 1, matches with the ones we expected and agrees with the results presented in [1]. 

Table 1 Results of an ant colony for TSP composed by 10, 20 and 30 ants on 50 cities for 2500 iterations

JACSF applied to Multicasting Problem in a network     

Multicasting in a network is the targeting of a single data packet to a selected set of receivers in the network. It is in opposition to traditional communication modes unicast and broadcast that are, respectively, one-to-one and one-to-all communications.

Efficient multicasting is a fundamental issue for the success of several real-time internet services involving at the same time a given number of clients and a great amount of data, such as video conferencing, computer supported co-operative work applications, e-teaching, and so on. Such typical multimedia applications communicate using a collection of information formats, such as audio and video, which can be classified as continuous and time dependent media and which must be sent continuously to each client with a very few delay, in order to give him the impression of a real-time application.

Considering the needs of efficiency, expressed in term of low delay during transmissions and limited bandwidth, solving the Multicasting Problem means generating a tree of nodes from the sender to the given set of clients which has the minimal cost in term of time and bandwidth.

Because the Multicasting Problem in networks can be seen as an instance of Steiner Problem on a network [2], we moved our attention on it.

The Steiner Problem, as described in [2], can be represented by a graph G = (N, A), where N is the set of nodes and A is the set of arcs connecting the nodes, a set Z Í N (referring to Multicasting Problem Z is the set of clients which must receive the data packets) and a cost measure δ(r, s) : G ?› R which determines the cost of the arc from the node r to the node s. Solving the Steiner Problem means finding a set T Í G, such that Z Í T, having the minimum cost. Formally:

If δ(r, s) always is positive the subset T is a tree called Steiner Tree and it gives a solution to the corresponding Multicasting Problem.

Because Steiner Problem is very similar to TSP, we adapted our ACS for TSP to solve it. We made the following assertions:

-          State Transition Rule, Local Updating Rule and the Comparison Function are the same as the ACS for TSP described in the previous chapter;

-          Global Updating Rule is modified in the following way: evaporation of pheromones is applied on an arc only if it brings to a node not in Z (see Eq. (6)). Such a modification allows to make “less desirable” arcs which doesn’t bring to nodes in Z and its global effect is to limit the number of nodes in T which tend to the number of nodes in Z;

-          End of Activity Rule returns true when an ant has covered all nodes in Z;

-          the initial value τ (r, s) is τ₀ for each arc between nodes not in Z (as in ACS for TSP) and λτ₀(where 0<λ<1) for each arc between nodes in Z. In this way we suggest to our ants a “preferred tour” which covers the nodes in Z.

-          the starting node for each ant is selected from Z.

Picture 7 Global Updating Rule modified to solve the Steiner Problem.         

Then, we designed two classes Ant4SP and AntColony4SP, derived respectively from the Ant4TSPand AntColony4TSP. We opted to derive from the classes designed for TSP because there are very few changes to do respect to the base classes. The object model of the resulting class hierarchy is depicted using UML notation in Picture 8.

The class AntColony4SP differs from AntColony4TSP in the method globalUpdatingRule, defined in the Eq. (6), and in the method createAnts in which it creates the ants setting for each of them a starting node selected from Z. Its constructor sets the initial value τ(r, s) to λτ₀ for each arc between nodes in Z and τ₀ for other arcs (as in ACS for TSP). Finally the parameter λ is defined by the member variable L. Picture 14 in appendix A shows a possible implementation of the Global Updating Rule in Java.

The class Ant4TSP differs from Ant4TSP only in the method end because the End of Activity Rulemust return true when all nodes in Z has been covered (the source code for Ant4SP andAntColony4SP classes is available at: http://www.ugochirico.com)

We set A = 0.1, B = 2, R = 0.1 and Q0 = 0.8, L = 0.5 and we launched a colony composed by 10, 20 and 30 ants on a graph containing 50 nodes, with |Z| = 10 nodes, for 2500 iterations.

Table 2 reports the results we found. Again, the results we found matches with the one we expected.

Table 2 Results of an ant colony for the Steiner Problem composed by 10, 20 and 30 ants with |G| = 50 nodes and |Z| =10 nodes for 2500 iterations. 

Picture 8 Object Model, derived from JACSF, designed for Steiner Problem on networks

Conclusions

In this work we have explained how an Ant Colony System can be easily implemented in Java, proposing also an implementation for solving the Travel Salesman Problem and the Steiner Problem on a network. The proposed framework is only one of the possible implementation in Java but, we find that it is a good starting point to make a good implementation for a given problem. Currently we are using the implementation for the Steiner Problem to solve an actual Multicasting Problem on a network for one of our customer and now we are dealing with the values to give to the parameters in order to have the best performances. In the near future we hope to apply the framework to other optimization problems.

References:    

[1] Dorigo, M., Gambardella, L.M., “Ant Colony System: A Cooperative Learning Approach to the Travel Salesman Problem”, TR/IRIDIA/1996-5, Université Libre de Bruxelles

[2] Dreyfus S. E., Wagner, E.A., “The Steiner Problem in graphs”, Networks, 1, 1972, pp. 195-207

[3] Kompella V.P., Pasquale, J.C., Polyzos, G.C., “The Multicasting multimedia problem”, Tech. Rep. CS93-313, September 1993

Appendix A: Implementation in Java