Supervision : Bernadette BOUCHON-MEUNIER Co-supervision : DETYNIECKI Marcin
Evolutionary Optimisation for Inexact Graph Isomorphism
The solution to the inexact graph matching problem is the key for defining any type of graph distance. It is even more complex than the exact graph isomorphism problem. On the one hand, inexact graph matching is a combinatorial optimization problem in NP taking into account perturbations inherent in noisy real world environments. Exact graph matching, on the other hand, is a decision problem for which it has not yet been shown if its complexity class is P and which applies only to exactly identical graphs.
In this thesis, we study an approach based on genetic algorithms addressing both exact and inexact isomorphisms. We introduce several new crossover operators, some more general for use with any kind of permutation encoding, some specialized which include a greedy heuristic specific to graph matching. We conduct an exhaustive study in order to compare these operators with the existing ones, underlining their respective characteristics, advantages and disadvantages.
Furthermore, we examine several aspects for enhancing the algorithm, both theoretical and practical ones, leading to faster execution, better precision or even the assurance of finding the global optimum. We combine the genetic algorithm with generalized black-box heuristics, such as local search, specialized heuristics such as the A* algorithm or practical tools like parallelization techniques. Our final aim is to present a method addressing all different types of graph matching problems, i.e. exact and inexact, isomorphisms of graphs having the same size and sub-graph isomorphisms. We illustrate the generality of our approach with three applications with very distinct properties which cover the different problem types.
Defence : 10/22/2009 - 14h30 - Site Passy-Kennedy - salle 549 Jury members : Mme Bernadette Bouchon-Meunier
M Marcin Detyniecki
M Patrick Gallinari
Mme Evelyne Lutton [Rapporteur]
Mme Michèle Sebag [Rapporteur]
M El-Ghazali Talbi
Th. Bärecke, B. Bouchon‑Meunier, M. Detyniecki : “Fuzzy Present Value”, IEEE Symposium on Computational Intelligence for Financial Engineering & Economics (IEEE CIFEr), Paris, France, pp. 75-80, (IEEE) (2011)
Th. Bärecke, M.‑J. Lesot, H. Akdag, B. Bouchon‑Meunier : “Prise en compte du réseau de sources pour la fusion d’informations”, Atelier Fouille de données complexes, Journées Francophones Extraction et Gestion des Connaissances, EGC'11, vol. RNTI-E-20, Revue des Nouvelles Technologies de l'Information, Brest, France, pp. 323-324 (2011)
Th. Bärecke, M. Bendris, M. CAMPEDEL, M. Detyniecki, D. Marraud : “Traitement des modalités image et vidéo”, chapitre de Sémantique et multimodalité en analyse de l'information, pp. 97-142, (Hermes) (2011)
Th. Bärecke, E. Kijak, M. Detyniecki, A. Nürnberger : “Organizing Multimedia Information with Maps”, chapter in Recent Advances in Computational Intelligence in Multimedia Processing, vol. 96, Studies in Computational Intelligence, pp. 493-509, (Springer) (2008)
Th. Bärecke, E. Kijak, A. Nürnberger, M. Detyniecki : “Using Self-Organizing Maps to Support Video Navigation”, Proc. of 16th Intl. Conf. on Artificial Neural Networks (ICANN 2006), vol. 4131, Lecture Notes in Computer Science, Athens, Greece, pp. 396-405, (Springer) (2006)
Th. Bärecke, E. Kijak, A. Nürnberger, M. Detyniecki : “Video Navigation based on Self-Organizing Maps”, Proc. of the International Conference on Image and Video Retrieval (CIVR), vol. 4071, Lecture Notes in Computer Science, Tempa, Arizona, United States, pp. 340-349, (Springer) (2006)
Th. Bärecke, E. Kijak, A. Nürnberger, M. Detyniecki : “VideoSOM: A SOM-based Interface for Video Browsing”, Proc. of the International Conference on Image and Video Retrieval (CIVR), vol. 4071, Lecture Notes in Computer Science, Tempa, Arizona, United States, pp. 506-509, (Springer) (2006)