Evolutionary n-level hypergraph partitioning with adaptive coarsening

Preen, Richard; Smith, Jim

Abstract

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.

• 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
• DOI: https://doi.org/10.1109/TEVC.2019.2896951
• 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: https://uwe-repository.worktribe.com/output/852530
• Publisher URL: http://dx.doi.org/10.1109/TEVC.2019.2896951
• 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.
• Contract Date: Jan 26, 2019