1994 · 35 citations · 11 references
ComputingComputer ScienceAlgorithmsCombinatoricsComputer NetworksCommunication NetworksEvolutionary ComputationGenetic AlgorithmsGraph AlgorithmsMinimum Spanning Tree AlgorithmsMinimum Spanning Tree ProblemTelecommunications NetworksTree Algorithms
In this paper we investigate genetic algorithms (GA) as a .heuristic technique for obtaining near optimal solutions to the probabilistic minimum spanning tree (PMST) problem. The PMST problem is a natural generalization of the classical minimum spanning tree (MST) problem and is frequently a more realistic model. The PMST problem addresses the circumstances that arise when not all nodes are deterministically present but, rather, nodes are present with known probabilities. Although there are some special cases that are solvable in polynomial time, it is known that the PMST problem is NP-complete.
11
Genetic algorithms in search, optimization, and machine learning
Choice Reviews Online · 1989 · 49.3K citations
D. E. Goldberg · Medical Entomology and Zoology · 1989 · 10.1K citations
Foundations of genetic algorithms. 2
Lashon B. Booker · Biosystems · 1994 · 1K citations
Using Genetic Algorithms to Solve NP-Complete Problems
Kenneth De Jong, William M. Spears · 1989 · 363 citations