Ant-Tree: An ant colony optimization approach to the generalized minimum spanning tree problem

S. J. Shyu, P. Y. Yin, Bertrand M.T. Lin*, M. Haouari

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

25 Scopus citations

Abstract

The ant colony optimization is a meta-heuristic inspired by knowledge sharing amongst ants using pheromone, which serves as a kind of collective memory. Since the past few years, there have been several successful applications of this new approach for finding approximate solutions for computationally difficult problems in reasonable times. In this paper, we study the generalized minimum spanning tree problem that involves the design of a minimum weight connected network spanning at least one node out of every disjoint subset of the nodes in a graph. This problem has a wealth of pertinence to a wide range of applications in different areas. As the problem is known as computationally challenging, we adopt the ant colony optimization strategy and present a new solution method, called Ant-Tree, to develop approximate solutions. As an initial attempt, our study aims to provide an investigation of the ant colony optimization approach for coping with tree optimization problems. Through computational experiments, we compare the performances of our approach and the method available in the literature. Numerical results indicate that the proposed method is effective in producing quality approximate solutions.

Original languageEnglish
Pages (from-to)103-112
Number of pages10
JournalJournal of Experimental and Theoretical Artificial Intelligence
Volume15
Issue number1
DOIs
StatePublished - 1 Jan 2003

Keywords

  • Ant colony optimization
  • Collective memory
  • Generalized minimum spanning tree problem
  • Genetic algorithm
  • Meta-heuristic

Fingerprint Dive into the research topics of 'Ant-Tree: An ant colony optimization approach to the generalized minimum spanning tree problem'. Together they form a unique fingerprint.

Cite this