Application of genetic algorithms in graph matching
- 1 January 1994
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- Vol. 6, 3872-3876 vol.6
- https://doi.org/10.1109/icnn.1994.374829
Abstract
Genetic algorithms (GA) can be exploited for optimal graph matching. Graphs represent powerful method of a pattern formal description. Globally optimal graph matching is a NP-complete problem. Pattern distortions and noise increase an optimal search difficulty which could be tackled using GA. This paper describes results of simple GA applied on a graph matching problem. As a conclusion, the suitable GA for an optimal graph "isomorphism" and "monomorphism" is proposed. Used coding resembles the travelling salesman problem (TSP). Consequently, performance of ordering operators has been tested. In contrast to the TSP, the fitness function depends on chromosome value positioning not ordering. It results in differences between optimal GA configuration for graph matching and for TSP.<>Keywords
This publication has 3 references indexed in Scilit:
- An eigendecomposition approach to weighted graph matching problemsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1988
- Subgraph error-correcting isomorphisms for syntactic pattern recognitionIEEE Transactions on Systems, Man, and Cybernetics, 1983
- Relaxation Applied to Matching Quantitative Relational StructuresIEEE Transactions on Systems, Man, and Cybernetics, 1980