J'ai le plaisir de vous inviter à ma soutenance de thèse intitulée :
Isomorphisme inexact de graphes par optimisation évolutionnaire
qui aura lieu le jeudi 22 octobre à 14h30 au LIP6, salle 549.
---------------------
Résumé
---------------------
L'isomorphisme inexact de graphes est un problème crucial pour la
définition d'une distance entre graphes, préalable nécessaire à une
multitude d'applications allant de l'analyse d'images à des applications
biomédicales en passant par la reconnaissance optique de caractères. Ce
problème est encore plus complexe que celui de l'isomorphisme exact.
Alors que ce dernier est un problème de décision de complexité au moins
de classe P et qui ne s'applique qu'à des graphes exactement identiques,
l'isomorphisme inexact est un problème combinatoire de complexité de
classe NP qui permet de prendre en compte des perturbations dues au
bruit, qui apparaissent fréquemment dans les applications réelles.
Dans ce cadre, nous choisissons d'étudier une solution basée sur les
algorithmes génétiques pouvant être appliquée à l'isomorphisme exact et
inexact. Nous proposons des opérateurs de croisement généraux pour tout
problème représenté par un codage de permutation, ainsi que des
opérateurs spécifiques à l'isomorphisme de graphes qui exploitent une
heuristique gloutonne. Nous réalisons une étude exhaustive pour comparer
ces opérateurs avec les opérateurs existants, soulignant leurs
propriétés, avantages et inconvénients respectifs.
Nous étudions par ailleurs plusieurs pistes d'amélioration de
l'algorithme, en théorie ou en pratique, considérant successivement les
objectifs d'accélération de l'exécution, d'augmentation de la précision
et de garantie de résultat optimal. Nous proposons pour cela de combiner
l'approche proposée avec d'autres techniques telles que des heuristiques
générales comme la recherche locale, des heuristiques dédiées comme
l'algorithme A*, et des outils pratiques comme la parallélisation.
Ces travaux conduisent à la définition d'une méthode générique pour la
résolution de tous les problèmes d'isomorphismes de graphes, qu'il
s'agisse d'isomorphismes exact ou inexact, d'isomorphismes de graphes de
même taille ou d'isomorphismes de sous-graphes. Nous illustrons enfin la
validité de cette solution générale par trois applications concrètes
issues de domaines différents, la recherche d'images et la chimie, qui
présentent chacune des caractéristiques spécifiques, utilisant des
graphes attribués ou non, soumis aux perturbations plutôt structurelles
ou au niveau d'attributs.
---------------------
Composition du Jury
---------------------
Mme Bernadette Bouchon-Meunier, Directeur de recherche, CNRS (Directeur)
M Marcin Detyniecki, Chargé de recherche, CNRS, HDR (Encadrant)
M Patrick Gallinari, Professeur à l'Université Paris VI (Examinateur)
Mme Evelyne Lutton, Directeur de recherche, INRIA (Rapporteur)
Mme Michèle Sebag, Directeur de recherche, CNRS (Rapporteur)
M El-Ghazali Talbi, Professeur à l'Université de Lille I (Examinateur)
La soutenance sera suivie d'un pot "germanique" auquel vous êtes
cordialement invités.
Bien cordialement,
Thomas Baerecke
Bureau 623
Laboratoire d'Informatique de Paris 6
104 avenue du Président Kennedy
75016 Paris
Tel : 01 44 27 88 03
Fax : 01 44 27 70 00
Plan d'accès : http://www.lip6.fr/informations/comment.php
