LIP6 2009/001
- Thesis
Isomorphisme inexact de graphes par optimisation évolutionnaire - T. Baerecke
- 285 pages - 10/22/2009- document en - http://www.lip6.fr/lip6/reports/2009/lip6-2009-001.pdf
- Contact : Thomas.Baerecke (at) nulllip6.fr
- Team : MALIRE
- Keywords : inexact graph matching, graph distance, evolutionary algorithm, local search, memetic algorithm, combinatorial optimization, crossover operators, hybrid method, parallelization, metaheuristic.
- Publisher : Thierry.Lanfroy (at) nulllip6.fr
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.
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.