«An Ant Colony Optimisation Algorithm for the Bounded Diameter Minimum Spanning Tree Problem ausgef¨hrt am u Institut f¨r Computergraphik und ...»
Generally it can be noted, that the ACO algorithm is very slow in the beginning of the computation process, as the solutions constructed in this phase are very poor and the variable neighbourhood descent part can substantially improve these solutions, but this local improvement step is very time consuming. As time proceeds the artiﬁcial ants will construct better and better solutions, due to the information stored in the pheromone matrix. As a consequence the neighbourhood descent part needs less and less time to improve these solutions. So the time required for one iteration decreases over the whole runtime of the ACO algorithm, as the time needed by an artiﬁcial ant to build a solution is constant.
Another important characteristic of the ant colony optimisation algorithm, developed within the context of this master thesis, is the way artiﬁcial ants construct solutions. A tree is not built by starting from a single node and successive connecting the remaining ones, but ants distribute the nodes to various levels, since given this level information always a local optimal minimum spanning tree ensuring the diameter bound can be derived in an easy and straightforward way.
To evaluate the overall performance of the ant colony optimisation algorithm it was compared to the so-far-leading variable neighbourhood search implementation for the BDMST, that operates on the same neighbourhood structures, as well as to three evolutionary algorithms, namely a permutation, a random-key and a edge-set coded EA. Results on complete Euclidean instances turned out, that when considering solution quality the ACO algorithm is not only superior to the EAs but also to the VNS, especially on larger instances. In case the computation time is highly restricted the solutions provided by the ACO algorithm are in-between those of the EAs and those of the VNS.
without a time limit. A starting point for further research activities could be to adapt this ACO approach in a way that it also works on instances where the underlying graph is incomplete or, since the ACO algorithm was only compared to other metaheuristics on Euclidean instances, to test its eﬀectiveness on random instances.
BIBLIOGRAPHY Ayman Abdalla, Narsingh Deo, and Pankaj Gupta. Random-tree diameter and the diameter constrained MST. Congressus Numerantium, 144:161–182, 2000.
 N. R. Achuthan and L. Caccetta. Models for vehilce routing problems. Proceedings of the 10th National Conference of the Australian Society for Operations Research, pages 276–294, 1990.
 N. R. Achuthan and L. Caccetta. Minimum weight spanning trees with bounded diameter. Australasian Journal of Combinatorics, 5:261–276, 1992.
 N. R. Achuthan, L. Caccetta, P. Caccetta, and J. F. Geelen. Computational methods for the diameter restricted minimum weight spanning tree problem. Australasian Journal of Combinatorics, 10:51–71, 1994.
 K. Bala, K. Petropoulos, and T. E. Stern. Multicasting in a linear lightwave network.
In IEEE INFOCOM’93, pages 1350–1358, 1993.
 Christian Blum and Andrea Roli. Metaheuristics in combinatorial optimization:
Overview and conceptual comparison. ACM Computing Surveys, 35(3):268–308, 2003.
 A. Bookstein and S. T. Klein. Compression of correlated bit-vectors. Information Systems, 16(4):387–400, 1991.
 A. E. F. Clementi, M. Di Ianni, A. Monti, G. Rossi, and R. Silvestri. Experimental analysis of practically eﬃcient algorithms for bounded-hop accumulation in ad-hoc wireless networks. In Proceedings of the 19th IEEE International Parallel and Distributed Processing Symposium (IPDPS’05), workshop 12, volume 13, page 247.1, 2005.
 J.-L. Deneubourg, S. Aron, S. Goss, and J.-M. Pasteels. The self-organizing exploratory pattern of the argentine ant. Journal of Insect Behavior, 3:159–168, 1990.
 M. Dorigo and L. M. Gambardella. Ant colonies for the traveling salesman problem.
BioSystems, 43:73–81, 1997.
 M. Dorigo and L. M. Gambardella. Ant colony system: A coopeartive learning approach to the traveling salesman problem. IEEE Transactions on Evolutionary Computation, 1(1):53–66, 1997.
 M. Dorigo, V. Maniezzo, and A. Colorni. Positive feedback as a search strategy.
Technical Report 91-016, Dipartimento die Elettronica, Politecnico di Milano, IT, 1991.
 A. C. dos Santos, A. Lucena, and C. C. Ribeiro. Solving diameter constrained minimum spanning tree problems in dense graphs. In Proceedings of the International Workshop on Experimental Algorithms, volume 3059 of LNCS, pages 458–467. Springer, 2004.
 M. R. Garey and D. S. Johnson. Computers and Intractability. A Guide to the Theory of NP-Completeness. W.H. Freeman, New York, 1979.
 F. Glover. Future paths for integer programming and links to artiﬁcial intelligence.
Comput. Oper. Res., 13:533–549.
 S. Goss, S. Aron, J. L. Deneubourg, and J. M. Pasteels. Self-organized shortcuts in the argentine ant. Naturwissenschaften, 76:579–581, 1989.
 Luis Gouveia and Thomas L. Magnanti. Network ﬂow models for designing diameterconstrained minimum spanning and Steiner trees. Networks, 41(3):159–173, 2003.
 Luis Gouveia, Thomas L. Magnanti, and Christina Requejo. A 2-path approach for odd-diameter-constrained minimum spanning and Steiner trees. Networks, 44(4):254– 265, 2004.
 P. Hansen and N. Mladenovi´. An introduction to variable neighborhood search. In c S. Voss, S. Martello, I.H. Osman, and C. Roucairol, editors, Meta-heuristics, Advances and Trends in Local Search Paradigms for Optimization, pages 433–458. Kluwer Academic Publishers, 1999.
 B. A. Julstrom and G. R. Raidl. A permutation-coded evolutionary algorithm for the bounded-diameter minimum spanning tree problem. In A. Barry, F. Rothlauf, D. Thierens, et al., editors, in 2003 Genetic and Evolutionary Computation Conference’s Workshops Proceedings, Workshop on Analysis and Desgn of Representations, pages 2–7, 2003.
 Bryant A. Julstrom. Encoding bounded-diameter minimum spanning trees with permutations and with random keys. In Kalyanmoy Deb et al., editors, Genetic and Evolutionary Computation Conference – GECCO 2004, volume 3102 of LNCS, pages 1282–1281. Springer, 2004.
 Bryant A. Julstrom. Greedy heuristics for the bounded-diameter minimum spanning tree problem. Technical report, St. Cloud State University, 2004. Submitted for publication in the ACM Journal of Experimental Algorithmics.
 T. Magnanti and R. Wong. Network design and transportation planning: Models and algorithms. Transportation Science, 18(1), 1984.
 N. Mladenovi´. A variable neighborhood algorithm - a new metaheuristic for combic natorial optimization. Abstracts of papers presented at Optimization Days. Montreal, 1995.
 N. Mladenovi´ and P. Hansen. Variable neighborhood search. Computers Opers. Res., c 24:1097–1100, 1997.
 C. H. Papadimitriou and K. Steiglitz. Combinatorial Optimization-Algorithms and Complexity. Dover Publications, Inc., New York, 1982.
et al., editors, Proceedings of the 2003 ACM Symposium on Applied Computing, pages 747–752, New York, 2003. ACM Press.
 Kerry Raymond. A tree-based algorithm for distributed mutual exclusion. ACM Transactions on Computer Systems, 7(1):61–77, 1989.
 T. St¨tzle and H. Hoos. Introducing MAX − MIN ant system. In Proceedings of the u International Conference on Artiﬁcal Neural Networks and Genetic Algorithms, pages 245–249. Springer Verlag, 1997.
 T. St¨tzle and H. Hoos. MAX − MIN ant system and local search for the travelu ing salesman problem. In Proceedings of IEEE-ICEC-EPS’97, IEEE Conference on Evolutionary Computation and Evolutionary Programming Conference, pages 309–314.
IEEE Press, 1997.
 S. Voß, S. Martello, I. H. Osman, and C. Routacirol. Meta-Heuristics-Advances and Trends in Local Search Paradigms for Optimization. Kluwer Academic Publishers, Dordrecht, The Netherlands.