Skip to main content

Research Repository

Advanced Search

Evolutionary n-level hypergraph partitioning with adaptive coarsening

Preen, Richard; Smith, Jim

Evolutionary n-level hypergraph partitioning with adaptive coarsening Thumbnail


Richard Preen
Senior Research Fellow in Machine Learning

Profile Image

Jim Smith
Professor in Interactive Artificial Intelligence


Hypergraph partitioning is an NP-hard problem that occurs in many computer science applications where it is necessary to reduce large problems into a number of smaller, computationally tractable sub-problems. Current techniques use a multilevel approach wherein an initial partitioning is performed after compressing the hypergraph to a predetermined level. This level is typically chosen to produce very coarse hypergraphs in which heuristic algorithms are fast and effective. This article presents a novel memetic algorithm which remains effective on larger initial hypergraphs. This enables the exploitation of information that can be lost during coarsening and results in improved final solution quality. We use this algorithm to present an empirical analysis of the space of possible initial hypergraphs in terms of its searchability at different levels of coarsening. We find that the best results arise at coarsening levels unique to each hypergraph. Based on this, we introduce an adaptive scheme that stops coarsening when the rate of information loss in a hypergraph becomes non-linear and show that this produces further improvements. The results show that we have identified a valuable role for evolutionary algorithms within the current state-of-the-art hypergraph partitioning framework.


Preen, R., & Smith, J. (2019). Evolutionary n-level hypergraph partitioning with adaptive coarsening. IEEE Transactions on Evolutionary Computation, 23(6), 962-971.

Journal Article Type Article
Acceptance Date Jan 26, 2019
Online Publication Date Feb 4, 2019
Publication Date 2019-12
Deposit Date Jan 26, 2019
Publicly Available Date Feb 8, 2019
Journal IEEE Transactions on Evolutionary Computation
Print ISSN 1089-778X
Publisher Institute of Electrical and Electronics Engineers
Peer Reviewed Peer Reviewed
Volume 23
Issue 6
Pages 962-971
Keywords Partitioning algorithms , Memetics , Very large scale integration , Optimization , Frequency modulation , Computer science , Heuristic algorithms, evolutionary algorithms, hypergraph partitioning, memetic algorithms, multilevel algorithms
Public URL
Publisher URL
Additional Information Additional Information : (c) 2019 IEEE. Personal use of this material is permitted. Permission from IEEE must be obtained for all other users, including reprinting/ republishing this material for advertising or promotional purposes, creating new collective works for resale or redistribution to servers or lists, or reuse of any copyrighted components of this work in other works.


You might also like

Downloadable Citations