TY - GEN
T1 - Application of the "descent with mutations" metaheuristic to a clique partitioning problem
AU - Charon, I.
AU - Hudry, O.
PY - 2007/6/26
Y1 - 2007/6/26
N2 - 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.
AB - 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.
KW - Aggregation of symmetric relations into equivalence relations
KW - Clique partitioning of a graph
KW - Combinatorial optimization
KW - Metaheuristics
KW - Noising methods
KW - Simulated annealing
UR - https://www.scopus.com/pages/publications/34250747346
U2 - 10.1109/RIVF.2007.369132
DO - 10.1109/RIVF.2007.369132
M3 - Conference contribution
AN - SCOPUS:34250747346
SN - 1424406943
SN - 9781424406944
T3 - 2007 IEEE International Conference on Research, Innovation and Vision for the Future, RIVF 2007
SP - 29
EP - 35
BT - 2007 IEEE International Conference on Research, Innovation and Vision for the Future, RIVF 2007
T2 - 2007 IEEE International Conference on Research, Innovation and Vision for the Future, RIVF 2007
Y2 - 5 March 2007 through 9 March 2007
ER -