Appariement multivoque de graphes par la recherche locale

Authors: DEVILLE, Yves
NGUYEN, Thi Hong Hiep

Dans les applications de reconnaissance et de recherche d‟information, la mesure de similarité entre des objets joue un rôle clé. Lorsque les objets sont présentés sous forme de graphes, ce problème se transforme en mesure de similarité entre des graphes. En fait, à cause de la différence au niveau de modélisation des objets, chaque sommet d‟un graphe correspond peut-être à plusieurs sommets de l'autre graphe et inversement. Le matching multivoque de graphes peut résoudre ce problème en permettant de mettre en correspondance un sommet d'un graphe avec plusieurs sommets de l'autre. En utilisant une mesure de similarité pour formuler ce problème en problème d'optimisation dont la fonction objectif est cette mesure de similarité, le problème original de la recherche du meilleur appariement entre deux graphes se transforme en une recherche d'un appariement maximisant la fonction objectif. Malheureusement, l'appariement multivoque de graphes est un problème NP-complet impossible d'être résolu par un algorithme polynomial. Donc, la recherche locale est une approche alternative intéressante car permettant d'obtenir une solution approchée en temps polynomial. Elle ne garantit pas toujours le résultat globalement optimal mais donne des solutions acceptables. En explorant l'espace de recherche de voisin en voisin, les algorithmes de recherche locale permettent d'améliorer petit-à-petit la qualité de solution et dirige la recherche vers l'optimum global. Dans ce rapport, nous présentons trois algorithmes de recherche locale : la recherche gloutonne, la recherche taboue et la recherche taboue réactive où la fonction objectif est de maximiser la similarité entre les graphes. Ces trois algorithmes sont implémentées en COMET – un environnement développé pour la recherche locale et pour la programmation par contraintes. Dans la section résultats, nous comparons la qualité de ces trois algorithmes. Nous évaluons aussi l'efficacité de la recherche locale pour le problème d'appariement multivoque de graphes en montrant la qualité de la meilleure solution trouvée et le temps d'exécution...

Title:	Appariement multivoque de graphes par la recherche locale
Authors:	DEVILLE, Yves NGUYEN, Thi Hong Hiep
Issue Date:	2009

URI:	http://repository.vnu.edu.vn/handle/VNU_123/342
Appears in Collections:	IFI - Master Theses