nach oben

Soft Computing

Erschienen in:

01.12.2011 | Original Paper

An artificial bee colony algorithm for the minimum routing cost spanning tree problem

verfasst von: Alok Singh, Shyam Sundar

Erschienen in: Soft Computing | Ausgabe 12/2011

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

Given a connected, weighted, and undirected graph, the minimum routing cost spanning tree problem seeks a spanning tree of minimum routing cost on this graph, where routing cost of a spanning tree is defined as the sum of the costs of the paths connecting all possible pairs of distinct vertices in that spanning tree. This problem has several important applications in networks design and computational biology. In this paper, we have proposed an artificial bee colony (ABC) algorithm-based approach for this problem. We have compared our approach against four best methods reported in the literature—two genetic algorithms, a stochastic hill climber and a perturbation-based local search. Computational results show the superiority of our ABC approach over other approaches.

Vorheriger Artikel Lattice pseudoeffect algebras as double residuated structures

Nächster Artikel Torsion elements in effect algebras

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

Jetzt informieren

http://people.brunel.ac.uk/~mastjjb/jeb/info.html

Aho AV, Hopcroft JE, Ullman JD (1983) Data structures and algorithms. Addison-Wesley, Reading, pp 232–233

Basturk B, Karaboga D (2006) An artificial bee colony (ABC) algorithm for numeric function optimization, IEEE Swarm Intelligence Symposium 2006, May 12–14, 2006. Indianapolis, Indiana, USA

Campos R, Ricardo M (2008) A fast algorithm for computing the minimum routing cost spanning tree. Comput Netw 52:3229–3247MATHCrossRef

Fischetti M, Lancia G, Serafini P (2002) Exact algorithms for minimum routing cost trees. Networks 39:161–173MathSciNetMATHCrossRef

Grout V (2005) Principles of cost minimization in wireless networks. J Heuristics 11:115–133MATHCrossRef

Johnson DS, Lenstra JK, Roonoy Kan AHG (1978) The complexity of network design problem. Networks 8:279–285MathSciNetMATHCrossRef

Julstrom BA (2002) A genetic algorithm and two hill climbers for the minimum routing cost spanning tree problem. In: Arabnia HR, Mun Y (eds) Proceedings of the international conference on artificial intelligence, vol III, CSREA Press, pp 934–940

Julstrom BA (2005) The Blob code is competitive with edge-sets in genetic algorithms for the minimum routing cost spanning tree problem. In: Beyer HG et al (eds) Proceedings of the genetic and evolutionary computation conference 2005 (GECCO-2005), vol 1, pp 585–590, ACM Press

Karaboga D (2005) An idea based on honey bee swarm for numerical optimization, Technical Report TR06. Computer Engineering Department, Erciyes University, Turkey

Karaboga D, Basturk B (2007a) A powerful and efficient algorithm for numerical function optimization: artificial bee colony (ABC) algorithm. J Glob Optim 39:459–471

Karaboga D, Basturk B (2007b) Artificial bee colony (ABC) optimization algorithm for solving constrained optimization problems. Lecture Notes in Artificial Intelligence, Springer, Berlin, vol 4529, pp 789–798

Karaboga D, Basturk B (2008) On the performance of artificial bee colony (ABC) algorithm. Appl Soft Comput 8:687–697CrossRef

Karaboga D, Basturk B (2009) A comparative study of artificial bee colony algorithm. Appl Math Comput 214:108–132MathSciNetMATHCrossRef

Picciotto S (1999) How to encode a tree. PhD thesis, University of California, San Diego

Prim RC (1957) Shortest connection networks and some generalizations. Bell Syst Tech J 36:1389–1401

Raidl GR, Julstrom BA (2003) Edge-sets: an effective evolutionary coding of spanning trees. IEEE Trans Evol Comput 7:225–239CrossRef

Singh A (2008) A new heuristic for the minimum routing cost spanning tree problem. In: Proceedings of the 11th international conference on information technology (ICIT-2008), 9–13, IEEE CS Press

Singh A (2009) An artificial bee colony algorithm for the leaf-constrained minimum spanning tree problem. Appl Soft Comput 9:625–631

Wong R (1980) Worst case analysis of network design problem heuristics SIAM. J Algebraic Discrete Math 1:51–63MATHCrossRef

Wu BY, Chao KM (2004) Spanning trees and optimization problems, chapter 4. CRC Press, New York

Wu BY, Lancia G, Bafna V, Chao KM, Ravi R, Tang CY (1999) A polynomial time approximation schemes for minimum routing cost spanning trees. SIAM J Comput 29:761–768MathSciNetCrossRef

Titel: An artificial bee colony algorithm for the minimum routing cost spanning tree problem
verfasst von: Alok Singh
Shyam Sundar
Publikationsdatum: 01.12.2011
Verlag: Springer-Verlag
Erschienen in: Soft Computing / Ausgabe 12/2011
Print ISSN: 1432-7643
Elektronische ISSN: 1433-7479
DOI: https://doi.org/10.1007/s00500-011-0711-6

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Wirtschaft"

Springer Professional "Technik"

Weitere Artikel der Ausgabe 12/2011

Multiobjective genetic fuzzy rule selection of single granularity-based fuzzy classification rules and its interaction with the lateral tuning of membership functions

On a generalization of the concept of state property system

Torsion elements in effect algebras

Learning knowledge bases of multi-objective evolutionary fuzzy systems by simultaneously optimizing accuracy, complexity and partition integrity

Performance evaluation of evolutionary multiobjective optimization algorithms for multiobjective fuzzy genetics-based machine learning

Evolutionary fuzzy rule extraction for subgroup discovery in a psychiatric emergency department

Premium Partner