A Genetic Algorithm for the Constrained Forest Problem
ACEEE International Journal on Information Technology
ISSN or ISBN
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.
Laszlo, Michael J. and Mukherjee, Sumitra, "A Genetic Algorithm for the Constrained Forest Problem" (2011). CEC Faculty Articles. 525.