An efficient memetic algorithm for the graph partitioning problem

An efficient memetic algorithm for the graph partitioning problem

0.00 Avg rating0 Votes
Article ID: iaor201111684
Volume: 191
Issue: 1
Start Page Number: 1
End Page Number: 22
Publication Date: Nov 2011
Journal: Annals of Operations Research
Authors: , ,
Keywords: optimization, heuristics: tabu search
Abstract:

Given a graph and an integer k, the goal of the graph partitioning problem is to find a partition of the vertex set in k classes, while minimizing the number of cut edges, and respecting a balance constraint between the classes. In this paper, we present a new memetic algorithm for the solution of the problem which uses both a tabu operator and a specialized crossover operator. The algorithm is tested by using the benchmarks of the graph partitioning archive. Our experiments show our memetic algorithm to outperform state‐of‐the‐art algorithms proposed so far for the problem and to reach new records for a majority of the tested benchmarks instances.

Reviews

Required fields are marked *. Your email address will not be published.