Comparaison de l'optimisation par colonies de fourmis et d'une recherche réactive sur des problèmes d'appariement de graphes

Résumé : De nombreuses applications nécessitent de mesurer la similarité d'objets. Lorsque ces objets sont représentés par des graphes, la mesure de similarité se ramène à un problème d'appariement de graphes, i.e., à la recherche d'une meilleure mise en correspondance des sommets de deux graphes. Dans cet article, nous nous intéressons au calcul d'une similarité de graphes basée sur des appariements multivoques des sommets des graphes. Cette mesure a été montrée générique dans le sens où les autres mesures classiques de similarité de graphes peuvent être vues comme un cas particulier de celle-ci. Nous proposons deux algorithmes de calcul de cette similarité : un algorithme basé sur l'optimisation par colonies de fourmis et un algorithme de recherche locale taboue réactive. Nous comparons l'efficacité de ces deux algorithmes sur deux classes de problèmes d'appariements de graphes difficiles et nous montrons que ces algorithmes obtiennent des résultats complémentaires.
Type de document :
Communication dans un congrès
Deuxièmes Journées Francophones de Programmation par Contraintes (JFPC06), 2006, Nîmes - Ecole des Mines d'Alès / France, 2006
Liste complète des métadonnées

Littérature citée [20 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/inria-00085800
Contributeur : Laurent Henocque <>
Soumis le : vendredi 14 juillet 2006 - 13:49:38
Dernière modification le : mardi 16 janvier 2018 - 16:04:26
Document(s) archivé(s) le : lundi 5 avril 2010 - 21:47:01

Fichier

Identifiants

  • HAL Id : inria-00085800, version 1

Collections

Citation

Sébastien Sorlin, Olfa Sammoud, Christine Solnon, Khaled Ghédira. Comparaison de l'optimisation par colonies de fourmis et d'une recherche réactive sur des problèmes d'appariement de graphes. Deuxièmes Journées Francophones de Programmation par Contraintes (JFPC06), 2006, Nîmes - Ecole des Mines d'Alès / France, 2006. 〈inria-00085800〉

Partager

Métriques

Consultations de la notice

177

Téléchargements de fichiers

337