Application of the "descent with mutations" metaheuristic to a clique partitioning problem

We study here the application of a metaheuristic, issued from the noising methods and that we call "descent with mutations", to a problem arising in the field of the aggregation of symmetric relations: the clique partitioning of a weighted graph. This local search metaheuristic, of which the design is very simple, is compared with another very efficient metaheuristic, which is a simulated annealing improved by the addition of some ingredients coming from the noising methods. These experiments show that the descent with mutations is at least as efficient for the studied problem as this improved simulated annealing, usually a little better, while, above all, it is much easier to design and to apply.