A Hybrid Evolutionary Algorithm for the Clique Partitioning Problem.

Area of Science:

• Computational mathematics
• Graph theory
• Optimization algorithms

Background:

• The clique partitioning problem (CPP) involves partitioning graph vertices into subsets to maximize intra-subset edge weights.
• CPP is computationally challenging (NP-hard) despite applications in data mining, engineering, and bioinformatics.

Purpose of the Study:

• To develop an effective evolutionary algorithm for solving the NP-hard clique partitioning problem.
• To improve upon existing methods for finding high-quality solutions to CPP.

Main Methods:

• Proposed a novel evolutionary algorithm integrating a merge-divide crossover operator.
• Incorporated a simulated annealing-based local search for refining solutions.
• Evaluated performance on 94 benchmark instances, including classical and large-scale datasets.

Main Results:

• The proposed evolutionary algorithm demonstrated remarkable performance.
• Achieved superior results compared to state-of-the-art methods on benchmark instances.
• Analysis identified key algorithmic components contributing to performance.

Conclusions:

• The developed evolutionary algorithm offers an effective solution for the clique partitioning problem.
• The algorithm and its source code can aid researchers and practitioners in CPP-related fields.