NTRS - NASA Technical Reports Server

Back to Results
At-Least Version of the Generalized Minimum Spanning Tree Problem: Optimization Through Ant Colony System and Genetic AlgorithmsThe At-Least version of the Generalized Minimum Spanning Tree Problem (L-GMST) is a problem in which the optimal solution connects all defined clusters of nodes in a given network at a minimum cost. The L-GMST is NPHard; therefore, metaheuristic algorithms have been used to find reasonable solutions to the problem as opposed to computationally feasible exact algorithms, which many believe do not exist for such a problem. One such metaheuristic uses a swarm-intelligent Ant Colony System (ACS) algorithm, in which agents converge on a solution through the weighing of local heuristics, such as the shortest available path and the number of agents that recently used a given path. However, in a network using a solution derived from the ACS algorithm, some nodes may move around to different clusters and cause small changes in the network makeup. Rerunning the algorithm from the start would be somewhat inefficient due to the significance of the changes, so a genetic algorithm based on the top few solutions found in the ACS algorithm is proposed to quickly and efficiently adapt the network to these small changes.
Document ID
Acquisition Source
Jet Propulsion Laboratory
Document Type
Janich, Karl W.
(Harvey Mudd Coll. CA, United States)
Date Acquired
August 23, 2013
Publication Date
August 1, 2005
Publication Information
Publication: Summer Student Research Presentations
Subject Category
Mathematical And Computer Sciences (General)
Distribution Limits
Work of the US Gov. Public Use Permitted.

Available Downloads

There are no available downloads for this record.
No Preview Available