We study here the application of the “descent with mutations” metaheuristic to a problem arising from the field of classification and cluster analysis (dealing more precisely with the aggregation of symmetric relations) and which can be represented as a clique partitioning of a weighted graph. In this problem, we deai with a complete undirected graphe G; the edges of G have weights which can be positive, negative or equal to 0; the aim is to partition the vertices of G into disjoint cliques (whose number depends on G in order to minimize the sum of the weights of the edges with their two extremities in a same clique; this problem is NP-hard. The “descent with mutations” is a local search metaheuristic, of which the design is very simple and is based on local transformation. It consists in randomly performing random elementary transformations, irrespective improvement or worsening with respect to the objective function. We compare it with another very efficient metaheuristic, which is a simulated annealing method improved by the addition of some ingredients coming from the noising methods. 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 it is much easier to design and to tune.
Accepté le :
DOI : 10.1051/ro/2018048
Mots-clés : Metaheuristics, noising methods, simulated annealing, clique partitioning of a graph, aggregation of symmetric relations into median partitions, median equivalence relations
@article{RO_2019__53_3_1083_0,
author = {Hudry, Olivier},
title = {Application of the {\textquotedblleft}descent with mutations{\textquotedblright} metaheuristic to a clique partitioning problem},
journal = {RAIRO - Operations Research - Recherche Op\'erationnelle},
pages = {1083--1095},
publisher = {EDP-Sciences},
volume = {53},
number = {3},
year = {2019},
doi = {10.1051/ro/2018048},
mrnumber = {3986366},
zbl = {1423.90277},
language = {en},
url = {http://www.numdam.org/articles/10.1051/ro/2018048/}
}
TY - JOUR AU - Hudry, Olivier TI - Application of the “descent with mutations” metaheuristic to a clique partitioning problem JO - RAIRO - Operations Research - Recherche Opérationnelle PY - 2019 SP - 1083 EP - 1095 VL - 53 IS - 3 PB - EDP-Sciences UR - http://www.numdam.org/articles/10.1051/ro/2018048/ DO - 10.1051/ro/2018048 LA - en ID - RO_2019__53_3_1083_0 ER -
%0 Journal Article %A Hudry, Olivier %T Application of the “descent with mutations” metaheuristic to a clique partitioning problem %J RAIRO - Operations Research - Recherche Opérationnelle %D 2019 %P 1083-1095 %V 53 %N 3 %I EDP-Sciences %U http://www.numdam.org/articles/10.1051/ro/2018048/ %R 10.1051/ro/2018048 %G en %F RO_2019__53_3_1083_0
Hudry, Olivier. Application of the “descent with mutations” metaheuristic to a clique partitioning problem. RAIRO - Operations Research - Recherche Opérationnelle, Tome 53 (2019) no. 3, pp. 1083-1095. doi : 10.1051/ro/2018048. http://www.numdam.org/articles/10.1051/ro/2018048/
[1] , and , Clustering and clique partitioning: simulated annealing and tabu search approaches. J. Classif. 9 (1992) 17–42. | MR
[2] , and , Clustering and Classification. World Scientific Publishers, Singapore and River Edge, NJ (1996). | MR | Zbl
[3] and , The median procedure for partitions. DIMACS Ser. Discrete Math. Theor. Comput. Sci. 19 (1995) 3–34. | MR | Zbl
[4] and , The median procedure in cluster analysis and social choice theory. Math. Soc. Sci. 1 (1981) 235–267. | MR | Zbl
[5] , Les éléments fondamentaux de la classification. In: Analyse des données, edited by . Hermès Lavoisier, Paris (2003).
[6] and , Éléments de classification. Hermès, Paris (2007). | Zbl
[7] and , The noising method: a new combinatorial optimization method. Oper. Res. Lett. 14 (1993) 133–137. | MR | Zbl
[8] and , Mixing different components of metaheuristics. In: Metaheuristics: Theory and Applications, edited by and . Kluwer Academic Publishers, Boston (1996) 589–603. | Zbl
[9] and , Lamarckian genetic algorithms applied to the aggregation of preferences. Ann. Oper. Res. 80 (1998) 281–297. | MR | Zbl
[10] and , Application of the noising methods to the Travelling Salesman Problem. Eur. J. Oper. Res. 125 (2000) 266–277. | MR | Zbl
[11] and , Self-tuning of the noising methods. Optimization 58 (2009) 1–21. | MR | Zbl
[12] and , The noising methods. In: Heuristics: Theory and Applications, edited by . Nova Publishers, New York, NY (2013) 1–30.
[13] , Simulated annealing. In: Modern Heuristic Techniques for Combinatorial Problems, edited by . McGraw-Hill, London (1995) 20–69. | MR
[14] , , and , Cluster Analysis. Wiley, Hoboken, NJ (2011). | MR | Zbl
[15] and , Handbook of Metaheuristics. Springer, Berlin (2010). | Zbl
[16] , NP-hardness of the computation of a median equivalence relation in classification (Régnier’s problem). Math. Soc. Sci. 197 (2012) 83–97. | MR | Zbl
[17] , Descent with mutations applied to the linear order problem. In: Book of Abstracts of the 5th International Symposium on Combinatorial Optimization, ISCO 2018 (2018) 86–87.
[18] and , NP-hard problems in hierarchical-tree clustering. Acta Inf. 23 (1986) 311–323. | MR | Zbl
[19] , Essentials of Metaheuristics. 2nd edition. Available at: http://cs.gmu.edu/sean/book/metaheuristics/. Lulu Press (2013).
[20] , Sur quelques aspects mathématiques des problèmes de classification automatique. ICC Bull. 4 (1965) 175. | Zbl
[21] , Cluster Analysis for Researchers. Lulu Press, Morrisville, NC (2004).
[22] (ed.), Metaheuristics. Springer, Berlin (2016). | MR | Zbl
[23] , Metaheuristics: From Design to Implementation. Wiley, Hoboken, NJ, 2009. | Zbl
[24] , Aggregation of binary relations: algorithmic and polyhedral investigations. Ph.D. thesis, Augsbourg (1986). | Zbl
[25] , The complexity of computing medians of relations. Resenhas 3 (1998) 323–349. | MR | Zbl
[26] , Approximating symmetric relations by equivalence relations. SIAM J. Appl. Math. 12 (1964) 840–847. | MR | Zbl
Cité par Sources :
