Graph Matching with Distance-Preserving Crossover
Thomas Bärecke
Marcin Detyniecki
Databases and Machine Learning Department
Laboratoire d’Informatique de Paris 6
University Pierre and Marie Curie, Paris, 75005 France
marcin.detyniecki@lip6.fr
Abstract
Graph models are fundamental to any kind of application on structured real-world problems. Any comparison between graphs by a graph distance measure requires the solution of the inexact graph matching problem, which constitutes a hard combinatorial optimization problem. An inexact matching problem includes in its formulation robustness to any type of perturbation, such as, for instance, noise, inherently present in real-world environments. In this paper, we introduce the concept of distance-preserving crossover operators for genetic algorithms for this task. For large graphs, our algorithm outperforms any state-of-the-art approximate algorithm—in particular, genetic algorithms with alternative crossover operators, which are to the best of our knowledge currently limited to no more than 50 nodes. We use a two-level local search heuristic to further enhance the results, pushing the limits to up to 300 nodes: a first local search step is directly integrated into the crossover operator; another one is applied independently during offspring generation.
Keywords: graph distance; evolutionary computation; genetic algorithm; inexact graph isomorphism; permutation encoding; crossover operator with local search
Cite this publication as:
T. Bärecke and M. Detyniecki, “The Effects of Interaction Functions between Two Cellular Automata,” Complex Systems, 31(2), 2022 pp. 219–246.
https://doi.org/10.25088/ComplexSystems.31.2.219
