IEEE Trans Cybern. 2022 Sep;52(9):9391-9403. doi: 10.1109/TCYB.2021.3051243. Epub 2022 Aug 18.
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.
边权完全图的团划分问题（CPP）是将顶点集 V 划分为 k 个不相交的子集，使得由子集诱导的所有团的边权之和尽可能大。该问题在数据挖掘、工程和生物信息学等领域有许多实际应用，但在计算上具有挑战性。为了解决这个 NP 难问题，我们提出了第一个进化算法，该算法结合了专门的合并-分裂交叉算子来生成后代解，以及有效的基于模拟退火的局部优化过程来寻找高质量的局部最优解。在三组 94 个基准实例（包括两组 63 个经典基准实例和一组 31 个大型基准实例）上的广泛实验表明，与最先进的方法相比，所提出的方法具有显著的性能。我们分析了关键的算法成分，以了解它们对算法性能的影响。该算法及其可用的源代码可以使从事 CPP 相关实际问题的人们受益。
