A Genetic Algorithm for the Constrained Forest Problem

Given a graph with positive edge weights and a positive integer m, the Constrained Forest Problem (CFP) problem seeks a minimum-weight spanning subgraph each of whose components contains at least m vertices. Such a subgraph is called an m-forest. We present a genetic algorithm (GA) for CFP, which is NP-hard for me”4. Our GA evolves good spanning trees, as determined by the weight of the m-forest into which it can be partitioned by a simple greedy algorithm. Genetic operators include mutation, which replaces a spanning tree edge by a different edge that connects the same pair of components, and recombination, which combines the edge sets of two spanning trees to produce two new spanning trees. The GA discovers m-forests that are significantly better than those identified by best-known approximation algorithms for CFP, and identifies optimal solutions in small problems