Personal tools
Laboratoire d'InfoRmatique en Image et Systèmes d'information

Skip to content. | Skip to navigation

Laboratoire d'InfoRmatique en Image et Systèmes d'information
UMR 5205 CNRS / INSA Lyon / Université Claude Bernard Lyon 1 / Université Lumière Lyon 2 / École Centrale de Lyon
You are here: Home > publis

PhD thesis

Appariement de graphes et optimisation dynamique par colonies de fourmis
Olfa Sammoud [LIRIS]
5/2010
Établissement : Université de Lyon 1
Soutenue le May 21, 2010
Jury
Pr Deville Yves, Université catholique de Louvain, Belgique Rapporteur
Pr Korbaa Ouajdi, LI3, Tunisie Rapporteur
Pr Jolion Jean-Michel , LIRIS, Lyon Président
Mr Albert Patrick, Directeur Scientifique à IBM, Gentilly Examinateur
Mme Solnon Christine, LIRIS, Lyon Co-directeur
Pr; Ghédira Khaled, SOIE, Tunisie Co-directeur
Contact : olfa.sammoud@gmail.com

TEL : hal-01464744

Résumé

Cette thèse s'intéresse à une problématique ayant de nombreuses applications pratiques, à savoir la comparaison automatique d'objets et l'évaluation de la similarité. Lorsque les objets sont modélisés par des graphes, ce problème de comparaison automatique d'objet se ramène à un problème d'appariement de graphes, c-à-d, chercher une mise en correspondance entre les sommets des graphes permettant de retrouver le plus grand nombre de caractéristiques communes. Différentes classes d'appariements de graphes existent allant de la plus restrictive à la plus générale. Dans la plus restrictive isomorphisme de (sous-)graphes), il s'agit de chercher un appariement exact entre les sommets des graphes de manière à prouver que les deux graphes possèdent une structure identique ou que l'un d'eux est inclus dans l'autre, un sommet étant apparié avec au plus un sommet. Dans la plus générale (appariement multivoque}, l'objectif n'est plus de trouver un appariement exact mais le meilleur appariement, c-à-d, celui qui préserve un maximum de sommets et d'arcs, un sommet pouvant être apparié à un ensemble de sommets. Nous nous intéressons au problème de la recherche du meilleur appariement multivoque, ce problème étant plus général que les problèmes d'appariements restrictifs. Sa résolution est clairement un défi tant par la difficulté du problème que par l'importance de ses applications. Pour relever ce défi, nous proposons d'étudier les capacités de l'optimisation par colonies de fourmis (ACO). Notre étude est menée dans deux contextes : un contexte statique, où le problème est figé, et un contexte dynamique, où les graphes à comparer, les contraintes à respecter ainsi que les critères définissant la qualité des appariements changent régulièrement de sorte que la solution doit être dynamiquement adaptée. Un premier objectif, de cette thèse, est de proposer un algorithme ACO générique pour la résolution des problèmes d'appariement de graphes. Plusieurs points clés sont étudiés dans cet algorithme, à savoir : l'influence des paramètres sur la qualité des solutions construites, l'influence de la stratégie phéromonale et du facteur heuristique, et l'hybridation avec une technique de recherche locale. Un deuxième objectif est de proposer un algorithme ACO générique pour résoudre des problèmes d'optimisation dynamiques. L'algorithme proposé est appliqué et expérimenté à quelques problèmes dynamiques, à savoir : l'appariement de graphes, le problème du sac à dos multidimensionnel, et le voyageur de commerce.

Additional information

Thèse en co-tutelle avec ENSI/SOIE Tunisie

BibTex

Download

@PhDThesis{Liris-4709,
  title         = {{Appariement de graphes et optimisation dynamique par 
    colonies de fourmis}},
  author        = {Olfa {Sammoud}},
  year          = {2010},
  month         = may,
  school        = {Université de Lyon 1},
  type          = {Thèse de Doctorat en Informatique},
   language      = {fr},
  url           = {http://liris.cnrs.fr/publis/?id=4709},
  note          = {Thèse en co-tutelle avec ENSI/SOIE Tunisie}
}