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

Sébastien Sorlin 1 Olfa Sammoud 1, 2 Christine Solnon 1 Khaled Ghédira 2
1 LIRIS - Laboratoire d'InfoRmatique en Image et Systèmes d'information
2 SOIE - Stratégies d’Optimisation et Informatique intelligentE
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 : mercredi 31 octobre 2018 - 12:24:06
Document(s) archivé(s) le : lundi 5 avril 2010 - 21:47:01

Fichier

32.pdf

Identifiants

  • HAL Id : inria-00085800, version 1

Collections

JFPC06 | INSA-LYON | EC-LYON | LIRIS | UNIV-LYON1

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〉

Exporter

BibTeX TEI DC DCterms EndNote

Partager

Métriques

Consultations de la notice

250

Téléchargements de fichiers

507

Contact


archive-ouverte@inria.fr