Graph partitioning through a multi-objective evolutionary algorithm
Dilip Datta, José Rui Figueira, Carlos M. Fonseca, Fernando Tavares-Pereira · 2008
The graph partitioning problem has numerous applications in various scientific fields. It usually involves the effective partitioning of a graph into a number of disjoint sub-graphs/zones, and hence becomes a combinatorial optimization problem whose worst case complexity is NP-complete. The inadequacies of exact methods, like linear and integer programming approaches, to handle large-size instances of the combinatorial problems have motivated heuristic techniques to these problems. In the present work, a multi-objective evolutionary algorithm (MOEA), a kind of heuristic techniques, is developed for partitioning a graph under multiple objectives and constraints. The developed MOEA, which is a modified form of NSGA-II, is applied to four randomly generated graphs for partitioning them by optimizing three common objectives under five general constraints. The applications show that the MOEA is successful, in most of the cases, in achieving the expected results by partitioning a graph into a variable number of zones.