.png){kind=icon}
.png){kind=icon}
Return
A Hybrid Evolutionary Algorithm for the Clique Partitioning Problem
.png){kind=icon}
PRE
AI
DOI：10.1109/TCYB.2021.3051243.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
The clique partitioning problem (CPP) of an edge-weighted complete graph is to partition the vertex set V into k disjoint subsets such that the sum of the edge weights within all cliques induced by the subsets is as large as possible. The problem has a number of practical applications in areas, such as data mining, engineering, and bioinformatics, and is, however, computationally challenging. To solve this NP-hard problem, we propose the first evolutionary algorithm that combines a dedicated merge-divide crossover operator to generate offspring solutions and an effective simulated annealing-based local optimization procedure to find high-quality local optima. The extensive experiments on three sets of 94 benchmark instances (including two sets of 63 classical benchmark instances and one new set of 31 large benchmark) show a remarkable performance of the proposed approach compared to the state-of-the-art methods. We analyze the key algorithmic ingredients to shed light on their impacts on the performance of the algorithm. The algorithm and its available source code can benefit people working on practical problems related to CPP.
Keywords:
Partitioning algorithms
Statistics
Sociology
Optimization
Search problems
Evolutionary computation
Benchmark testing
Clique partitioning
crossover
hybrid evolutionary search method
local optimization
AI Summary
Key information extracted from the uploaded paper, including a brief overview, abstract, background, key highlights, visual analysis, and future outlook.
Journal
IF:
10.5
Papers:
1.1W
Citations:
5.0W
Organization
No organization information available