![](/images/graphics-bg.png)
Moving Clusters within a Memetic Algorithm for Graph Partitioning
Joint Authors
Yoon, Yourim
Kim, Yong-Hyuk
Hwang, Inwook
Source
Mathematical Problems in Engineering
Issue
Vol. 2015, Issue 2015 (31 Dec. 2015), pp.1-10, 10 p.
Publisher
Hindawi Publishing Corporation
Publication Date
2015-09-20
Country of Publication
Egypt
No. of Pages
10
Main Subjects
Abstract EN
Most memetic algorithms (MAs) for graph partitioning reduce the cut size of partitions using iterative improvement.
But this local process considers one vertex at a time and fails to move clusters between subsets when the movement of any single vertex increases cut size, even though moving the whole cluster would reduce it.
A new heuristic identifies clusters from the population of locally optimized random partitions that must anyway be created to seed the MA, and as the MA runs it makes beneficial cluster moves.
Results on standard benchmark graphs show significant reductions in cut size, in some cases improving on the best result in the literature.
American Psychological Association (APA)
Hwang, Inwook& Kim, Yong-Hyuk& Yoon, Yourim. 2015. Moving Clusters within a Memetic Algorithm for Graph Partitioning. Mathematical Problems in Engineering،Vol. 2015, no. 2015, pp.1-10.
https://search.emarefa.net/detail/BIM-1073290
Modern Language Association (MLA)
Hwang, Inwook…[et al.]. Moving Clusters within a Memetic Algorithm for Graph Partitioning. Mathematical Problems in Engineering No. 2015 (2015), pp.1-10.
https://search.emarefa.net/detail/BIM-1073290
American Medical Association (AMA)
Hwang, Inwook& Kim, Yong-Hyuk& Yoon, Yourim. Moving Clusters within a Memetic Algorithm for Graph Partitioning. Mathematical Problems in Engineering. 2015. Vol. 2015, no. 2015, pp.1-10.
https://search.emarefa.net/detail/BIM-1073290
Data Type
Journal Articles
Language
English
Notes
Includes bibliographical references
Record ID
BIM-1073290