«An Ant Colony Optimisation Algorithm for the Bounded Diameter Minimum Spanning Tree Problem ausgef¨hrt am u Institut f¨r Computergraphik und ...»
./Aco -t graphtype -d diameter -i instancefile [-g instancefile] [-r rho] [-s time_limit] [-l iteration_limit] [-a ants] Here in alphabetical order the list describing all optional as well as mandatory parameters
of the Aco program in detail:
• a is an optional parameter. It indicates the number of artiﬁcial ants forming the ant colony. If it is omitted a default colony size of 10 ants is used.
• d is a mandatory parameter, since it speciﬁes the diameter bound. The number declared has to be a positive integer number greater or equal to 4, otherwise an error message is prompted.
• i has also to be speciﬁed, stating the path to the instance ﬁle.
• g is only a mandatory parameter when a GNUplot graph instance is used, since GNUplot instances consist of two ﬁles, a point and a line ﬁle. So in case of a GNUplot graph instance the parameter g takes the line ﬁle, the corresponding point ﬁle has to be speciﬁed using parameter i. In case of all other graph types this parameter has to be omitted, otherwise an error message is prompted.
• l speciﬁes the maximum number of iterations without an improvement of the best solution found so far. As it is an optional parameter it can be omitted, in this case the program sets it per default to 1000.
• s is an optional parameter indicating the time limit in seconds, otherwise no time limit is set. Only positive integer numbers are valid values for this parameter, all other speciﬁcations will result in a corresponding error message.
• t is a mandatory parameter and speciﬁes the type of the instance ﬁle. The instance
parser used by this program is able to read in four diﬀerent ﬁle formats:
The output of the Aco program is sent to standard out (std::cout) per default, but it can easily be redirected to any ﬁle with the help of the appropriate Unix operator “”. The output starts with a summary of all instance relevant information, e.g. instance ﬁle, number of nodes or diameter bound. Then a summary of each iteration follows, containing various information on every ant of the colony. Each ant builds a solution exploiting the knowledge stored in the pheromone matrix. Afterwards, this solutions is tried to be improved by a VND algorithm using four diﬀerent neighbourhood structures. This iteration summary states for each artiﬁcial ant the total costs of the solution found after local improvement by VND, the total costs of the best solution found so far, time needed so far and ﬁnally an indicator if the current best solution was achieved by this ant. Finally, when a termination condition is met – either time limit or x rounds without further improvement of the best found solution – a complete summary of the optimisation process is printed, containing again all instance relevant information plus total costs of the best solution found and the time in seconds until the program was terminated. Note, that it in general the time stated at the end of this summary is not the time required to achieve the best solution. In the
following a sample output of an Aco run is presented:
------------------------------------------------------------------------Bounded diameter minimum spanning tree problem: ACO [ver. 1.0 / 10.2005]
------------------------------------------------------------------------Reading in instance...
Successfully read in EA instance...../data/ea/estein500_01.eu
Creating Solution object to save best solution... done Creating Solution object for computations... done Creating EdgeExchange object... done Creating NodeSwap object... done Creating CentreExchange object... done Creating LevelChange object... done Creating starting solution value... done
------------------------------------------------------------------------Ant 0 found 1877464 [vnd] 1877464 [ACO] 1.75 sec.
* Ant 1 found 1858671 [vnd] 1858671 [ACO] 3.65 sec.
Ant 2 found 1885506 [vnd] 1858671 [ACO] 5.30 sec.
Ant 4 found 1918045 [vnd] 1836331 [ACO] 8.92 sec.
Ant 5 found 1884828 [vnd] 1836331 [ACO] 11.30 sec.
Ant 6 found 1887286 [vnd] 1836331 [ACO] 13.10 sec.
Ant 7 found 1945281 [vnd] 1836331 [ACO] 15.31 sec.
Ant 8 found 1876021 [vnd] 1836331 [ACO] 18.13 sec.
Ant 9 found 1918894 [vnd] 1836331 [ACO] 20.05 sec.
------------------------------------------------------------------------Updating pheromone matrix... 1836331 [ACO] 20.05 sec.
------------------------------------------------------------------------COMPUTATIONAL RESULTS This chapter takes a closer look at the performance of the ACO algorithm for the BDMST problem, developed within the context of this master thesis, and compares it to that of other heuristics for the BDMST problem. Three state-of-the-art metaheuristics have been selected for this comparison, a VNS implementation by Gruber and Raidl , a permutation coded EA as well as a random-key coded EA from . Of major interest is the comparison of the ACO presented here and the VNS by Gruber and Raidl, since they use in principle the same neighbourhood structures for their VND as it is done in the ACO, especially because the VNS is the so far leading metaheuristic for the BDMST problem.
For comparison the same instances, diameter bounds, time limits and termination conditions as in  were used. The instances were taken from the Beasley’s OR-Library1 and have been originally proposed for the Euclidean Steiner tree problem. All nodes of a graph are settled within the unit square and the Euclidean distance between any pair of nodes corresponds to the edge costs between these two nodes. Furthermore, as in , the tests were grouped into long-term and short-term runs. The long-term runs concentrated on achieving as good results as possible. In the short-term runs the diﬀerent algorithms had a relatively short time with respect to the instance size for yielding good solutions. The size of the ant colony was set to ten artiﬁcial ants for all test categories. Before presenting the computational results it should be noted, that all test runs were performed on a Pentium R 4
2.8 GHz system using Linux 2.4.21 as operating system.
First the results of the long-term runs are discussed. As in  the ﬁrst ﬁve instances of each size n = 100, 250, 500 available in the OR-Library were used and the diameter bound was set to 10 for instances with 100 nodes, to 15 for instances with 250 nodes, and to 20 for instances with 500 nodes. Two diﬀerent termination conditions were introduced for these long-term runs for the ACO, adopted from : The ACO algorithm terminated either if the last 1000 iterations yielded no improvement of the best found solution so far or if a time limit was reached. This time limit was set to 2000 seconds for instances with 100 nodes, to 3000 seconds for instances with 250 nodes, and to 4000 seconds for instances with 500 http://people.brunel.ac.uk/∼mastjjb/jeb/orlib/esteininfo.html
7. Computational Results 53
Table 7.1 shows the computational results of the long-term runs.
It lists for each instance the number of nodes, the diameter bound, the instance number, and for each metaheuristic the objective values of the best and mean solutions found. Furthermore, the standard deviation of 50 (EAs) and 30 (VNS, ACO) independent runs is presented.
In addition, for the ACO the mean times for identifying the best solutions are given. As indicated in Table 7.1 ρ varies among the diﬀerent instance sizes in order to obtain better solutions. The results for the EAs as well as those for the VNS are taken from .
Like the VNS implementation the ACO algorithm outperforms the two EAs concerning either best as well as mean solution values. Comparing the ACO with the VNS it can be seen that on instances with 100 nodes the ACO algorithm is still close to the VNS implementation concerning best solutions, but is already better regarding mean values.
The greater the instances the larger the gap between the ACO algorithm and the VNS.
While on instances of size n = 250 the ACO performs already clearly better than the VNS concerning best as well as mean solutions, on instances with 500 nodes the mean objective value of the solutions found by the ACO is close to – in one case it is even better than – the best solution identiﬁed by the VNS. In addition, the standard deviation of the ACO algorithm is much smaller than those of the three other metaheuristics. Furthermore, it is interesting to observe, that the time limit was never reached. For each instance size 1000 iterations without further improvement terminated the ACO algorithm, in contrast to, for example, the VNS, which requires the whole 4000 seconds to compute the solutions listed for the instances with 500 nodes.
As in  for the short-term tests the permutation coded EA was replaced by an edgeComputational Results 54 set coded EA from , since it makes use of operators with linear time complexity and therefore scales much better with larger instances. The same tests should be performed but for the 1000 node instances the time limit turned out to be really though for the ACO.
When using the time limit of 100 seconds no useful results could be achieved due to the following reason: In the ﬁrst iteration of the colony with its ten artiﬁcial ants every solution constructed by an artiﬁcial ant is more or less random, as the pheromone matrix contains no practical information yet (it is initialised uniformly). Therefore the variable neighbourhood descent part of the ACO algorithm can substantially improve these solutions, but this improvement process requires a lot of time due to the fact that the quality of the solution constructed by an ant is very poor. As a consequence only four to six solutions could be processed within the time limit of 100 seconds. Since not even one iteration could be ﬁnished within this time limit, thus no update of the pheromone matrix was performed, no relevant results for the ACO can be presented here for the 1000 nodes instances in combination with a time limit of 100 seconds. Using a time limit of 1000 seconds enables the ACO algorithm to ﬁnish at least ﬁve to eight complete iterations.
Table 7.2 presents the results of the short-term runs.
It shows the number of nodes, the diameter bound, the instance number, and the time limit in seconds. Furthermore, for each metaheuristic the objective values of the best solutions found, the mean values and the standard deviations are listed. For each instance 50 (EAs) respectively 30 (VNS, ACO) independent runs have been performed.
In addition for the ACO algorithm the parameter ρ used for the experiments is given, since varying it depending on the time limit and instance size yielded better results. Again the results for the EAs as well as those for the VNS are taken from .
From Table 7.2 it can be seen that the ACO algorithm consistently outperforms the two EAs. Considering the 500 node instances, the mean values of the ACO with tighter time limits, as well as those of the VNS, are even better than the objective values of the best solutions found by any of the EAs. Unfortunately, the good results of the VNS cannot be reached by the ACO. Looking at the 500 node instances it can be seen that when using a time limit of 500 seconds the ACO algorithm comes closer to the results of the VNS but cannot really exceed them. Just on two instances the ACO yields a better solution, and it beats the VNS only one time concerning the mean values. The main reason for this behaviour is – as already mentioned above – that the ACO algorithm starts with very poor, more or less random solutions, since in the ﬁrst iteration the solutions constructed by the artiﬁcial ants are based on a uniformly initialised pheromone matrix. In the following
7. Computational Results 55
these solutions can be improved signiﬁcantly by the variable neighbourhood descent, but at the expense of a high running time. Another aspect that has to be taken into account in the short-term runs is the value chosen for the parameter ρ which controls how much inﬂuence the best solution identiﬁed within one iteration shall have on the pheromone and – consequently – on the probabilities calculated based on this pheromone information for the following iterations. Remember, that based on these probabilities all artiﬁcial ants construct solutions. The greater the ρ value the higher the probability to assign node v to level l also in a subsequent iteration (if this combination was part of the best solution) since the pheromone value for this combination of node and level will dominate the other ones relatively fast. As a consequence the ACO algorithm converges to a certain solution after only a small number of iterations. As the ﬁrst solutions are in general of a poor quality (even after the VND local improvement step), a great ρ value will not yield good solutions at all, since a solution close to these bad solutions will be favoured very soon. On the other hand, if the value of the parameter ρ is chosen too low the pheromone updates written into the pheromone matrix are so small compared to the values already stored there that they have only marginal eﬀects on the probabilities calculated from the pheromone information.
So within the next iteration nearly the same probabilities can be met. When using a too tough time limit with respect to the ρ value it is likely to occur that the already collected information cannot be exploited at all. Table 7.2 indicates this eﬀect. For instances with 500 nodes and a time limit of 50 seconds a relatively great ρ value has been used in order to make use of the information already written to and stored in the pheromone matrix. By
7. Computational Results 56 decupling the time limit an obviously smaller ρ can be applied. This smaller ρ is responsible for the behaviour that the algorithm does not favour – as fast as in the prior test category – a certain solution, but explores a greater part of the solution space before preferring a certain solution. This leads inevitably to much better results.