FREE ELECTRONIC LIBRARY - Thesis, documentation, books

Pages:     | 1 |   ...   | 6 | 7 ||

«An Ant Colony Optimisation Algorithm for the Bounded Diameter Minimum Spanning Tree Problem ausgef¨hrt am u Institut f¨r Computergraphik und ...»

-- [ Page 8 ] --

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 artificial 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 artificial ant to build a solution is constant.


This master thesis proposed an ant colony optimisation algorithm for the bounded diameter minimum spanning tree problem. Its main characteristic is that it makes use of a local optimisation heuristic, namely a variable neighbourhood descent, to improve overall solution quality. This VND approach is based on four different neighbourhood structures for the BDMST problem, namely Edge Exchange, Node Swap, Centre Exchange and Level Change. When developing these neighbourhood structures main focus was on an efficient and fast exploration of a certain neighbourhood, for example computing only cost differences when evaluating a solution. For two of them, namely Node Swap and Level Change, an incremental enumeration, applied after having identified and executed the most profitable move, was presented. This incremental exploration could not reduce the theoretical worst case time complexity, but accelerated computation essential in practise.

Another important characteristic of the ant colony optimisation algorithm, developed within the context of this master thesis, is the way artificial 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 effectiveness on random instances.


[1] Ayman Abdalla, Narsingh Deo, and Pankaj Gupta. Random-tree diameter and the diameter constrained MST. Congressus Numerantium, 144:161–182, 2000.

[2] 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.

[3] N. R. Achuthan and L. Caccetta. Minimum weight spanning trees with bounded diameter. Australasian Journal of Combinatorics, 5:261–276, 1992.

[4] 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.

[5] K. Bala, K. Petropoulos, and T. E. Stern. Multicasting in a linear lightwave network.

In IEEE INFOCOM’93, pages 1350–1358, 1993.

[6] Christian Blum and Andrea Roli. Metaheuristics in combinatorial optimization:

Overview and conceptual comparison. ACM Computing Surveys, 35(3):268–308, 2003.

[7] A. Bookstein and S. T. Klein. Compression of correlated bit-vectors. Information Systems, 16(4):387–400, 1991.

[8] A. E. F. Clementi, M. Di Ianni, A. Monti, G. Rossi, and R. Silvestri. Experimental analysis of practically efficient 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.

[9] 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.

–  –  –

[11] M. Dorigo and L. M. Gambardella. Ant colonies for the traveling salesman problem.

BioSystems, 43:73–81, 1997.

[12] 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.

[13] 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.

[14] 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.

[15] M. R. Garey and D. S. Johnson. Computers and Intractability. A Guide to the Theory of NP-Completeness. W.H. Freeman, New York, 1979.

[16] F. Glover. Future paths for integer programming and links to artificial intelligence.

Comput. Oper. Res., 13:533–549.

[17] S. Goss, S. Aron, J. L. Deneubourg, and J. M. Pasteels. Self-organized shortcuts in the argentine ant. Naturwissenschaften, 76:579–581, 1989.

[18] Luis Gouveia and Thomas L. Magnanti. Network flow models for designing diameterconstrained minimum spanning and Steiner trees. Networks, 41(3):159–173, 2003.

[19] 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.

–  –  –

[23] 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.

[24] 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.

[25] 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.

[26] 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.

[27] T. Magnanti and R. Wong. Network design and transportation planning: Models and algorithms. Transportation Science, 18(1), 1984.

[28] N. Mladenovi´. A variable neighborhood algorithm - a new metaheuristic for combic natorial optimization. Abstracts of papers presented at Optimization Days. Montreal, 1995.

[29] N. Mladenovi´ and P. Hansen. Variable neighborhood search. Computers Opers. Res., c 24:1097–1100, 1997.

[30] 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.

[32] Kerry Raymond. A tree-based algorithm for distributed mutual exclusion. ACM Transactions on Computer Systems, 7(1):61–77, 1989.

[33] T. St¨tzle and H. Hoos. Introducing MAX − MIN ant system. In Proceedings of the u International Conference on Artifical Neural Networks and Genetic Algorithms, pages 245–249. Springer Verlag, 1997.

[34] 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.

[35] 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.

Pages:     | 1 |   ...   | 6 | 7 ||

Similar works:

«COPYRIGHT NOTICE: Nathan M. Jensen: Nation-States and the Multinational Corporation is published by Princeton University Press and copyrighted, © 2006, by Princeton University Press. All rights reserved. No part of this book may be reproduced in any form by any electronic or mechanical means (including photocopying, recording, or information storage and retrieval) without permission in writing from the publisher, except for reading and browsing via the World Wide Web. Users are not permitted...»

«trans-kom 1 [2] (2008): 209-228 Seite 209 Iris Schrijver & Leona Van Vaerenbergh Die Redaktionskompetenz des Übersetzers: eine Mehrwertleistung oder ein Muss? Writing Skills: Bare Necessity or Added Value for Translators? – Abstract In appendix E of the European Quality Standard for Translation Services (DIN EN 15038 2006), technical writing is listed as an example of added value services for translators. It can thus be argued that technical writing is one of the multiple services offered by...»

«Swing Trading, pg. 1 Swing Trading Using Candlestick charting with Pivot Point Analysis Written by John L. Person Introduction: This booklet was written with the intention of enlightening your knowledge and awareness of different techniques of technical analysis. As a professional trader and public speaker I strive to help educate my community of investors and clients. As an example of my commitment to that goal I want to provide this manual to you. I believe that continued education can help...»

«TWO YEARS AFTER MAIDAN: UKRAINIANS COMMITTED TO DEMOCRACY, DISAPPOINTED IN UNMET ASPIRATIONS September 2015 This publication was produced by IFES for the U.S. Agency for International Development.Two Years after Maidan: Ukrainians Committed to Democracy, Disappointed in Unmet Aspirations Key Findings from a September 2015 IFES Survey in Ukraine Two Years after Maidan: Ukrainians Committed to Democracy, Disappointed in Unmet Aspirations Copyright © 2015 International Foundation for Electoral...»

«GENDER TROUBLE GENDER TROUBLE Feminism and the Subversion of Identity JUDITH BUTLER Routledge New York and London Published in 1999 by Routledge 29 West 35th Street New York, NY 10001 Published in Great Britain by Routledge 11 New Fetter Lane London EC4P 4EE This edition published in the Taylor & Francis e-Library, 2002. Copyright © 1990, 1999 by Routledge Gender Trouble was originally published in the Routledge book series Thinking Gender, edited by Linda J. Nicholson. All rights reserved. No...»

«Syllable based Lattice Transduction for Keyword Search Hang Su Electrical Engineering and Computer Sciences University of California at Berkeley Technical Report No. UCB/EECS-2015-268 http://www.eecs.berkeley.edu/Pubs/TechRpts/2015/EECS-2015-268.html December 23, 2015 Copyright © 2015, by the author(s). All rights reserved. Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed...»

«CGEH Working Paper Series Human Capital Formation from Occupations: The ‘Deskilling Hypothesis’ Revisited Alexandra M. de Pleijt, Utrecht University Jacob L. Weisdorf, University of Southern Denmark, Utrecht University, CEPR June 2014 Working paper no. 57 www.cgeh.nl/working-paper-series/ Human Capital Formation from Occupations: The ‘Deskilling Hypothesis’ Revisited Alexandra M. de Pleijt, Utrecht University Jacob L. Weisdorf, University of Southern Denmark, Utrecht University, CEPR...»

«Encouraging More People to Take up Snow Sports The snow sports sector is beset by many problems. One of the most important objectives for the sector is to find effective ways to increase the number of people taking up snow sports. In all sports, the majority of people who take up any given sport follow a cycle in which they progressively become more enthusiastic and improve their technical skills, and then, at some point, their interest tapers off and they give up the sport. In fact, there are...»

«MONEY PUMPS IN THE MARKET Ariel Rubinstein Ran Spiegler Tel Aviv University University College London Abstract Agents who employ non-rational choice procedures are often vulnerable to exploitation, in the sense that a profit-seeking trader can offer them a harmful transaction which they will nevertheless accept. We examine the vulnerability of a procedure for deciding whether to buy a lottery: observe another agent who already bought it and buy the lottery if that agent’s experience was...»

«TECHNISCHE UNIVERSITÄT MÜNCHEN Lehrstuhl für Technische Mikrobiologie Analysis of the diversity of water kefir microbiota by culture-dependent and -independent approaches Anna Jana Gulitz Vollständiger Abdruck der von der Fakultät Wissenschaftszentrum Weihenstephan für Ernährung, Landnutzung und Umwelt der Technischen Universität München zur Erlangung des akademischen Grades eines Doktors der Naturwissenschaften genehmigten Dissertation. Vorsitzender: Univ-Prof. Dr. S. Scherer Prüfer...»

«Transforming Lives Awards Washington Community and Technical Colleges January 2016 Celebrating Student Achievement Timothy Woodiwiss Angelica Gonzalez Andrea Fast Armando Garcia Tyler Gilmore Big Bend Green River College Shoreline Spokane Falls Whatcom Community College Community College Community College Community College Transforming Lives Washington Community and Technical College Student Awardees January 2016 Transforming Lives The Association of College Trustees (ACT) Transforming...»

«Diplomacy in the Digital Age Brian Hocking Jan Melissen Clingendael Report Diplomacy in the Digital Age Brian Hocking Jan Melissen July 2015 July 2015 © Netherlands Institute of International Relations Clingendael. All rights reserved. No part of this book may be reproduced, stored in a retrieval system, or transmitted, in any form or by any means, electronic, mechanical, photocopying, recording, or otherwise, without the prior written permission of the copyright holders. About the authors...»

<<  HOME   |    CONTACTS
2016 www.thesis.xlibx.info - Thesis, documentation, books

Materials of this site are available for review, all rights belong to their respective owners.
If you do not agree with the fact that your material is placed on this site, please, email us, we will within 1-2 business days delete him.