Moving clusters within a memetic algorithm for graph partitioning
type: Item
instance of: scholarly article
title: Moving clusters within a memetic algorithm for graph partitioning
zbMATH Open document ID: 1393.05250
DOI: 10.1155/2015/238529
author: Inwook Hwang
author: Yong-Hyuk Kim
author: Yourim Yoon
published in: Mathematical Problems in Engineering
publication date: 2018-08-27T00:00:00Z
review text: Summary: 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.
Mathematics Subject Classification ID: 05C85
Mathematics Subject Classification ID: 05C70
zbMATH DE Number: 6925829
Wikidata QID: Q59117687
MaRDI profile type: Publication
full work available at URL: https://doi.org/10.1155/2015/238529
OpenAlex ID: W2142570667
cites work: Q4198056
cites work: Finding good approximate vertex and edge partitions is NP-hard
cites work: An Efficient Heuristic Procedure for Partitioning Graphs
cites work: Optimization by Simulated Annealing: An Experimental Evaluation; Part I, Graph Partitioning
cites work: Genetic algorithm and graph partitioning
cites work: Tabu search for graph partitioning
cites work: Lock-gain based graph partitioning
cites work: Evolutionary optimization and the estimation of search distributions with applications to graph bipartitioning.
cites work: A combined evolutionary search and multilevel optimisation approach to graph-partitioning
cites work: Quotient geometric crossovers and redundant encodings
cites work: An Improved Min-Cut Algonthm for Partitioning VLSI Networks
cites work: Multiple-way network partitioning
cites work: Q4436911
cites work: Q4436940
cites work: A theoretical and empirical study on unbiased boundary-extended crossover for real-valued representation
Recommended article: An efficient memetic algorithm for the graph partitioning problem
Recommended article: Memetic Graph Clustering
Recommended article: Q3528951
Recommended article: A genetic algorithm for graph partitioning
Recommended article: Parameterized Algorithms for Partitioning Graphs into Highly Connected Clusters
Recommended article: A combined evolutionary search and multilevel optimisation approach to graph-partitioning
Recommended article: (Semi-)External Algorithms for Graph Partitioning and Clustering
description: scientific article; zbMATH DE number 6925829