A Multilevel Memetic Approach for Improving Graph k-Partitions
- 29 September 2011
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Evolutionary Computation
- Vol. 15 (5), 624-642
- https://doi.org/10.1109/tevc.2011.2136346
Abstract
Graph partitioning is one of the most studied NP-complete problems. Given a graph G=(V, E) , the task is to partition the vertex set V into k disjoint subsets of about the same size, such that the number of edges with endpoints in different subsets is minimized. In this paper, we present a highly effective multilevel memetic algorithm, which integrates a new multiparent crossover operator and a powerful perturbation-based tabu search algorithm. The proposed crossover operator tends to preserve the backbone with respect to a certain number of parent individuals, i.e., the grouping of vertices which is common to all parent individuals. Extensive experimental studies on numerous benchmark instances from the graph partitioning archive show that the proposed approach, within a time limit ranging from several minutes to several hours, performs far better than any of the existing graph partitioning algorithms in terms of solution quality.Keywords
This publication has 33 references indexed in Scilit:
- An evolutionary approach with diversity guarantee and well-informed grouping recombination for graph coloringComputers & Operations Research, 2010
- A new diffusion-based multilevel algorithm for computing graph partitionsJournal of Parallel and Distributed Computing, 2009
- A PROBE-Based Heuristic for Graph PartitioningIEEE Transactions on Computers, 2007
- Partitioning of VLSI Circuits on Subcircuits with Minimal Number of Connections Using Evolutionary AlgorithmLecture Notes in Computer Science, 2006
- A Combined Evolutionary Search and Multilevel Optimisation Approach to Graph-PartitioningJournal of Global Optimization, 2004
- Finding balanced graph bi-partitions using a hybrid genetic algorithmPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- Fitness Landscapes, Memetic Algorithms, and Greedy Operators for Graph BipartitioningEvolutionary Computation, 2000
- Landscapes, operators and heuristic searchAnnals of Operations Research, 1999
- Genetic algorithm and graph partitioningIEEE Transactions on Computers, 1996
- Tabu search for graph partitioningAnnals of Operations Research, 1996