A swarm intelligence approach to the quadratic minimum spanning tree problem
Information SciencesPublished 7 May 2010
Shyam Sundar, Alok Singh
Citations108
SJR quartileQ1
SJR score1.80
SNIP1.98
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
TL;DR
An artificial bee colony (ABC) algorithm is presented, a new swarm intelligence approach inspired by intelligent foraging behavior of honey bees, to solve the quadratic minimum spanning tree problem.
Abstract
The quadratic minimum spanning tree problem (Q-MST) is an extension of the minimum spanning tree problem (MST). In Q-MST, in addition to edge costs, costs are also associated with ordered pairs of distinct edges and one has to find a spanning tree that minimizes the sumtotal of the costs of individual edges present in the spanning tree and the costs of the ordered pairs containing only edges present in the spanning tree. Though MST can be solved in polynomial time, Q-MST is NP-Hard. In this paper we present an artificial bee colony (ABC) algorithm to solve Q-MST. The ABC algorithm is a new swarm intelligence approach inspired by intelligent foraging behavior of honey bees. Computational results show the effectiveness of our approach.
Keywords
Computer ScienceEngineeringSocial Sciences
Journal of Global OptimizationA powerful and efficient algorithm for numerical function optimization: artificial bee colony (ABC) algorithm
7,504 Citations2007Derviş Karaboğa, Bahriye Akay
Artificial Bee Colony (ABC) Algorithm is an optimization algorithm based on the intelligent behaviour of honey bee swarm that is used for optimizing multivariable functions and the results showed that ABC outperforms the other algorithms.
AN IDEA BASED ON HONEY BEE SWARM FOR NUMERICAL OPTIMIZATION
5,440 Citations2005Derviş Karaboğa
Bell System Technical JournalShortest Connection Networks And Some Generalizations
4,498 Citations1957R. C. Prim
Simple and practical procedures are given for solving the basic problem of interconnecting a given set of terminals with the shortest possible network of direct links both graphically and computationally.
Applied Soft ComputingOn the performance of artificial bee colony (ABC) algorithm
3,661 Citations2007Derviş Karaboğa, B. Basturk
The simulation results show that the performance of ABC algorithm is comparable to those of differential evolution, particle swarm optimization and evolutionary algorithm and can be efficiently employed to solve engineering problems with high dimensionality.
Applied Mathematics and ComputationA comparative study of Artificial Bee Colony algorithm
3,198 Citations2009Derviş Karaboğa, Bahriye Akay
Results show that the performance of the ABC is better than or similar to those of other population-based algorithms with the advantage of employing fewer control parameters.
Lecture notes in computer scienceArtificial Bee Colony (ABC) Optimization Algorithm for Solving Constrained Optimization Problems
1,392 Citations2007Derviş Karaboğa, Bahriye Akay
The ABC algorithm has been extended for solving constrained optimization problems and applied to a set of constrained problems to show superior performance on these kind of problems.
Artificial Intelligence ReviewA survey: algorithms simulating bee swarm intelligence
645 Citations2009Derviş Karaboğa, Bahriye Akay
This work presents a survey of the algorithms described based on the intelligence in bee swarms and their applications, and presents a list of winners and losers.
Information SciencesA discrete artificial bee colony algorithm for the lot-streaming flow shop scheduling problem
577 Citations2010Quan-Ke Pan, M. Fatih Tasgetiren +2 more
A discrete artificial bee colony algorithm is proposed to solve the lot-streaming flow shop scheduling problem with the criterion of total weighted earliness and tardiness penalties under both the idling and no-idling cases.
Applied Soft ComputingAn artificial bee colony algorithm for the leaf-constrained minimum spanning tree problem
427 Citations2008Alok Singh
The proposed ABC algorithm is a new metaheuristic approach inspired by intelligent foraging behavior of honeybee swarm that obtained better quality solutions in shorter time and was compared against the best approaches reported in the literature.
IEEE Transactions on Evolutionary ComputationEdge sets: an effective evolutionary coding of spanning trees
280 Citations2003Günther R. Raidl, Bryant A. Julstrom
This work proposes representing spanning trees in EAs for network design problems directly as sets of their edges and describes initialization, recombination, and mutation operators for this representation, and demonstrates the usefulness of the edge-set encoding in an EA for the NP-hard degree-constrained minimum spanning-tree problem.
Naval Research Logistics (NRL)The quadratic minimum spanning tree problem
75 Citations1992Arjang A. Assad, Weixuan Xu
A technique for generating lower bounds for this quadratic minimum spanning tree problem is discussed and incorporated into branch-and-bound schemes for obtaining exact solutions.
Computers & Operations ResearchAn effective genetic algorithm approach to the quadratic minimum spanning tree problem
72 Citations1998Gengui Zhout, Mitsuo Gen
This paper presents a new approach to solve the q-MST problem by using a genetic algorithm, and a skillful encoding for trees, denoted by Prufer number, is adopted for GA operation.
IEEE Transactions on Evolutionary ComputationThe edge-window-decoder representation for tree-based problems
56 Citations2006Sang-Moon Soak, David Corne +1 more
Experiments show that EWD strategies using one particular biased operator are able to apply a consistent intermediate level of bias "pressure" over time, thus allowing the search to range more freely in the early stages over the less represented areas of the landscape, rather than becoming committed to MST-like regions.