«An Ant Colony Optimisation Algorithm for the Bounded Diameter Minimum Spanning Tree Problem ausgef¨hrt am u Institut f¨r Computergraphik und ...»
The ACO for the BDMST problem, proposed within the context of this master thesis, is based on the ant colony system (ACS), ﬁrst proposed by Dorigo et al. in 1996 [12, 11]. A property taken from the ACS for the travelling salesman problem (TSP) is the pheromone initialisation process. Another adapted characteristic is that every artiﬁcial ant is only responsible for constructing a solution, since the pheromone update process is managed by a daemon. This daemon identiﬁes, as it is representative for ACS algorithms, the best solution found by the whole colony in one iteration and updates the pheromone information proportional to the ﬁtness of this best solution found. Pheromone trail evaporation is also performed by the daemon. A main diﬀerence between the ACS concept and the ant colony optimisation metaheuristic presented here lies in the local decision policy. In general the decision policy of ACS algorithms includes a heuristic component when computing a state transition. This heuristic component for the local decision policy is completely omitted for this ACO algorithm.
For the implementation of the ACO algorithm some data structures are required, most of
them already known from the four diﬀerent neighbourhoods:
• Again the successor lists succ, storing for each node its immediate successors, the predecessor array pred, saving for each node its predecessor in the directed tree from the centre to the leaves, the level information lev, stating the level a node is assigned to and the level sets Vl with l = 0,..., D/2, containing all nodes at the level l, are used.
• In addition, a two dimensional n × ( D/2 + 1) pheromone matrix is needed to keep one pheromone entry for each combination of a node and a level. The value τi,j reﬂects the desirability of assigning node i to level j.
regarding pheromone deposition in comparison to the basic ACO concept for the TSP proposed by Dorigo [10, 13]. There they operate on a graph G = (V, E) where pheromone is deposited – either by ants themselves or by a daemon – on edges e ∈ E contained in the solution. The ACO algorithm presented here does not deposit pheromone on edges but exploits the fact that once given the level information lev(v) for all nodes v ∈ V an optimal solution for the bounded diameter spanning tree problem with respect to this level information lev can be easily derived. Therefore simply for each non centre node v the least cost predecessor p with lev(p) lev(v) has to be found. In case of several possible least cost predecessors, always one with minimum level is selected. Thus ants construct a solution not by “running” through the graph structure, but by assigning nodes to levels, building the level information lev. So the pheromone information reﬂects instead of the desirability of using an edge the desirability of assigning a node to a certain level. Algorithm 9 gives an overview of the ant colony optimisation algorithm developed in the context of this master thesis.
To be able to construct a solution based on the information stored in the pheromone matrix, it has to be ﬁrst initialised. This initial amount of pheromone for each combination of node and level has to be in relation to those values the pheromone update process is going to write into the matrix. E.g., if the initial values are too big compared to those, the pheromone update process is going to deposit, it will last very long until the ant colony will be capable of exploiting the information stored in the pheromone matrix. To guarantee that ants are able to use the collected information very soon the pheromone initialisation process follows the scheme of ACS algorithm for the TSP [12, 11], where the initial amount of pheromone deposited is proportional to the product of an initial solution value and the total number of nodes of the instance graph. Therefore in the ﬁrst line of Algorithm 9 a solution S using the randomised tree construction (RTC) heuristic  is computed. The solution value obtained from the RTC heuristic, together with the total number of nodes n is used to initialise the pheromone matrix with τi,j = 1/(S ∗ n), i = 0,..., n − 1 and j = 0,..., D/2.
Until no termination condition is met (line 3), which can be either a time limit, a maximum number of iterations without further improvement or both combined, in each iteration an colony of a ﬁnite number of artiﬁcial ants tries to ﬁnd good solutions based on the so far collected information on the problem instance.
Each artiﬁcial ant builds a solution based on the information stored in the pheromone matrix. As already mentioned, the solution construction process exploits the fact that a given level information lev for each node is enough to construct the local optimal tree.
5. Ant Colony Optimisation for the BDMST Problem 43 Algorithm 9: ACO for the BDMST create an initial solution S using the RTC heuristic;
initialise the pheromone matrix with 1/(S ∗ n);
while termination condition not met do for each ant of the colony do create a solution T, based on the information saved in the pheromone matrix;
So each ant simply sets each node to a certain level. The level a node is assigned to is selected randomly with a probability proportional to the pheromone information stored for this node, i.e. Pi,l is the probability that node i is assigned to level l.
In general – due to the stochastic level selection process – each node can be assigned to any level as long as no entry in the pheromone matrix is zero. This is a desirable behaviour except for level 0, where the number of nodes is ﬁxed in advance based on the diameter bound. Therefore the centre node(s) is (are) selected separately based on the information stored in the ﬁrst column of the pheromone matrix (the pheromone values of level 0 for each node). As said above this local decision policy has no heuristic component, every node is assigned to a certain level independently from all other nodes, only the decoding step – deriving a tree from the level information – makes use of a problem speciﬁc heuristic when using for each non centre node its cheapest available predecessor.
To improve solutions built by artiﬁcial ants the variable neighbourhood descend for the BDMST, presented in the previous section, is applied to these solutions. Thus each ant constructs a solution based on the information stored in the pheromone matrix. Afterwards the VND algorithm tries to improve this solution (lines 5 to 6).
The daemon is responsible for collecting all solutions found by the ant colony in the current iteration (line 7). From this pool of solutions it selects the best one T and determines the amount of pheromone, that is proportional to the ﬁtness of this best solution, going to be written into the pheromone matrix for the appropriate node/level combinations.
5. Ant Colony Optimisation for the BDMST Problem 44
After having calculated the amount of pheromone to be deposited, the pheromone matrix is updated (line 8). This update process combines the pheromone laying and the pheromone
evaporation process and follows the scheme introduced for ACS algorithms:
The parameter ρ, with 0 ≤ ρ ≤ 1 has a crucial impact on the convergence of the ant colony.
The greater ρ the faster the ant colony commits itself to a certain solution, it converges faster, perhaps too fast. On the contrary, the smaller ρ the later the ant colony is able to exploit already collected knowledge of the problem instance, in terms of the pheromone matrix, to construct good solutions, but therefore the solution space is explored in more detail. So using this parameter the behaviour of this ant colony optimisation algorithm can be inﬂuenced substantially and adjusted for diﬀerent applications.
In line 9 and 10 the daemon veriﬁes if the best solution found by the ant colony in the current iteration is better than the best solution found so far. If so this solution is saved as new best solution.
6. IMPLEMENTATION The ant colony optimisation metaheuristic, introduced in this master thesis, is implemented in C++, following the C++ coding standard, e.g. representing each class through a header ﬁle, stating the attribute and method declarations, and an implementation ﬁle, stating the program code. The only non-standard class library used is LEDA (Library of Eﬃcient Data Types and Algorithms) in terms of version 5.0.1. The aim of the LEDA project, launched in 1988, was to build a small, but extendable library of data structures and algorithms for combinatorial computing in a form making them easy to use. Since February 1st, 2001, Algorithmic Solutions Software GmbH is responsible for maintaining and developing LEDA1.
Figure 6.1 shows the UML class diagram of the major classes, their relationships as well as the most important attributes and methods of the respective classes.
The Instance class encapsulates all relevant information concerning a BDMST problem instance that does not change during computations, e.g. the underlying graph or the diameter bound. Due to this fact, each run of the ant colony optimisation algorithm has exactly one Instance object.
The InstanceParser is responsible for parsing the input ﬁle and storing the relevant information in the corresponding data structures. The InstanceParser is able to parse various ﬁle formats, e.g. GNUplot or EA graph instances. GNUplot ﬁles were created at the Institute of Computer Graphics and Algorithms for testing and visualising purposes.
EA ﬁles are instances from the Beasley’s OR-Library2 which haven been originally intended for Euclidean Steiner tree problems. As in [31, 25, 21] these instances have been used for comparing this ACO with other state-of-the-art metaheuristics.
are used. The predecessor attribute stores for each node its direct predecessor and centreNode keeps the centre node. In case of an odd diameter centreNode2 saves the second one. To express the correlation between a Solution object and the instance it belongs to, a pointer to the Instance object is passed to in the constructor of the Solution class. This pointer enables the Solution object to access instance speciﬁc information, like number of nodes, diameter bound or connection costs between two nodes. Important methods of the Solution class are ValidateSolution() and CalcSolValue(). The ValidateSolution() method veriﬁes if the solution represented by this Solution object contains all nodes of the problem instance, if the diameter bound is not violated and if the solution is free of circles. If it turns out that the Solution object represents a valid BDMST true is returned, otherwise false. The CalcSolValue() method calculates the total costs of the solution represented by the object and returns this objective value.
LocalSearch class a reference to a Solution object is passed to. This enables diﬀerent LocalSearch objects, in case they are referencing the same object, to operate on the same Solution object in a sequential order. Additional instance speciﬁc information can be accessed via this reference to the Solution object and its pointer to the Instance object.
The Execute() method, each subclass of LocalSearch has to implement, starts the improvement process, stopping in a local optimal solution with respect to the neighbourhood structure implemented by this subclass. In case the objective value of the solution passed to the constructor of the LocalSearch class has been improved, Execute() returns true, otherwise false.
EdgeExchange is a subclass of the
LocalSearch class and implements the Edge Exchange neighbourhood. All improvement moves found by the Execute() method are executed directly on the Solution object passed to it in the constructor. This holds true for all other subclasses of the abstract LocalSearch class, too.
Node Swap, another subclass of LocalSearch, implements the second neighbourhood structure based on the successor and predecessor relationships of the nodes, beside Edge Exchange, namely – as the name already presumes – Node Swap.
The LevelBased class is abstract and summarises attributes and methods used by its two subclasses, CentreExchange and LevelChange, implementing neighbourhoods based on the level representation of a solution. An example for such an additional attribute is nodesAtLevel which stores for each level all nodes assigned to it.
As already mentioned CentreExchange and LevelChange are subclasses of LevelBased.
The Execute() method of CentreExchange computes a local optimal solution with respect to the Centre Exchange neighbourhood, whereas LevelChange implements the Level Change neighbourhood.
The Aco class is the core of this ant colony optimisation program. It is responsible for creating all the required objects, as there are for example the sole object of the Instance class, objects of Solution and subclasses of the abstract LocalSearch class. Furthermore, it administrates – strictly speaking initialises and updates – the pheromone matrix. Based on the information stored in this pheromone matrix each artiﬁcial ant builds a solution by calling the CreateSolution() method. These solutions are then tried to be locally improved by a variable neighbourhood descent algorithm using the four diﬀerent neighbourhood structures implemented as subclasses of LocalSearch.
6. Implementation 48
6.1 User Manual
The proposed ant colony optimisation metaheuristic, implemented in C++, is a simple command line program, named Aco. The program was developed under Linux 2.4.21.
The program was compiled using gcc in version 3.3.1 under glibc in version 2.3.2. To start the program some mandatory parameters have to be speciﬁed. If they are missing the program will prompt an error message followed by a usage instruction. Furthermore, Aco has some optional parameters, that can be omitted when starting the ant colony optimisation program. In the following a synopsis of the program parameters is shown.