Genetic algorithms for network division problem

The network division problem (NDP), whereby a network (graph) of hosts (nodes) needs to be segmented into a given number of partitions with a penalty incurred for communication between partitions, is a fundamental problem in computer networks and distributed systems. The problem is a variation of a k-way graph partitioning problem and is thus NP-complete. The algorithmic methods for finding an optimal network segmentation are impractical due to the time required to find a solution. Other methods, possibly heuristic, are needed. Genetic algorithms (GAs) have been used in the past to find solutions to the k-way partitioning problem. Solving the NDP using GAs for networks with hundreds of nodes can still require large amounts of time, even for heuristic-based solutions. An improvement can be achieved via parallel implementation of a heuristic-based method. In this paper, we present a set of parallel genetic algorithms for the NDP. We contrast various selection methods for their effectiveness, practicality, and quality of results. Results are presented for an implementation on a 2048-processor DEC MPP12000Sx supercomputer