A Genetic Algorithm for the Constrained Forest
Problem
International Journal on Information Technology, 1 (3):
5 (December 2011)Abstract
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.