Richard Preen Richard2.Preen@uwe.ac.uk
Senior Research Fellow
Evolutionary n-level hypergraph partitioning with adaptive coarsening
Preen, Richard; Smith, Jim
Authors
Jim Smith James.Smith@uwe.ac.uk
Professor in Interactive Artificial Intelligence
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.
Citation
Preen, R., & Smith, J. (2019). Evolutionary n-level hypergraph partitioning with adaptive coarsening. IEEE Transactions on Evolutionary Computation, 23(6), 962-971. https://doi.org/10.1109/TEVC.2019.2896951
Journal Article Type | Article |
---|---|
Acceptance Date | Jan 26, 2019 |
Online Publication Date | Feb 4, 2019 |
Publication Date | 2019-12 |
Deposit Date | Jan 26, 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. |
Files
main.pdf
(765 Kb)
PDF
You might also like
Exploiting antipheromone in ant colony optimisation for interactive search-based software design and refactoring
(2016)
Presentation / Conference
Evolving atomic aesthetics and dynamics
(2016)
Journal Article
Sphere: A novel platform for increasing safety & security on unmanned systems
(2015)
Presentation / Conference
From evolutionary computation to the evolution of things
(2015)
Journal Article