Memetic algorithms for inexact graph matching

13 years 11 days ago
Memetic algorithms for inexact graph matching
—The noise-robust matching of two graphs is a hard combinatorial problem with practical importance in several domains. In practical applications, a unique solution for a given instance can not be defined, i.e. the actual solution may be outscored by some other due to noise effects arising during feature extraction. Soft computing approaches in general provide fast but not necessarily globally optimal solutions. In this case, the lack of guarantee of the global optimum is not a real drawback, since the uncertainty already arises in the problem definition. This paper discusses the application of memetic algorithms on the error-correcting graph isomorphism problem. We show that permutation encoding is robust enough to allow addressing both, the matching problem for graphs of the same size, and the subgraph matching problem. Since gene order information is meaningless in this particular case, a strict position based crossover is applied providing better performance than the popular PMX...
Thomas Bärecke, Marcin Detyniecki
Added 02 Jun 2010
Updated 02 Jun 2010
Type Conference
Year 2007
Where CEC
Authors Thomas Bärecke, Marcin Detyniecki
Comments (0)