Artifical bee colony algorithm using problem-specific neighborhood strategies for the tree t-spanner problem
| Autor: | Shyam Sundar, Kavita Singh |
|---|---|
| Rok vydání: | 2018 |
| Předmět: |
Spanning tree
K-ary tree Shortest-path tree Computer Science::Neural and Evolutionary Computation Prim's algorithm 0102 computer and information sciences 02 engineering and technology Minimum spanning tree 01 natural sciences Combinatorics 010201 computation theory & mathematics Kruskal's algorithm Euclidean minimum spanning tree 0202 electrical engineering electronic engineering information engineering Reverse-delete algorithm 020201 artificial intelligence & image processing Algorithm Software MathematicsofComputing_DISCRETEMATHEMATICS Mathematics |
| Zdroj: | Applied Soft Computing. 62:110-118 |
| ISSN: | 1568-4946 |
| DOI: | 10.1016/j.asoc.2017.10.022 |
| Popis: | A tree t-spanner is a spanning tree T in which the ratio of distance between every pair of vertices is at most t times their shortest distance in a connected graph, where t is a value called stretch factor of T. On a given connected, undirected, and weighted graph, this paper studies the tree t-spanner problem (Tree_t-SP) that aims to find a spanning tree whose stretch factor is minimum amongst all spanning trees of the graph. Being a N P -Hard for any fixed t > 1, this problem is under-studied in the domain of metaheuristic techniques. In literature, only genetic algorithm has been proposed for this problem. This paper presents an artificial bee colony (ABC) algorithm for this problem, where ABC algorithm is a swarm intelligence technique inspired by intelligent foraging behavior of honey bees. Neighborhood strategies of ABC algorithm particularly employ problem-specific knowledge that makes ABC algorithm highly effective in searching high quality solutions in less computational time. Computational experiments on a large set of randomly generated graph instances exhibit superior performance of ABC algorithm over the existing genetic algorithm for the Tree_t-SP. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full Text from ScienceDirect