CCE Faculty Articles

A Genetic Algorithm for the Constrained Forest Problem

Document Type

Article

Publication Title

ACEEE International Journal on Information Technology

ISSN

2158-012X

Publication Date

12-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.

DOI

01.IJIT.01.03.8

Volume

1

Issue

3

First Page

47

Last Page

51

This document is currently not available here.

Find in your library

Share

COinS