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.
No Reference information available - sign in for access.
No Citation information available - sign in for access.
No Supplementary Data.
No Article Media
Ant colony optimization;
generalized minimum spanning tree problem.;
Document Type: Research Article
Department of Computer Science and Information Engineering, Ming Chuan University, Tao-Yuan 333, Taiwan
Department of Information Management, National Chi Nan University, Nan-Tou 545, Taiwan
Ecole Polytechnique de Tunisie, LEGI BP 743, 2078 La Marsa, Tunisia
Publication date: January 1, 2003
More about this publication?