Convergence of a hill-climbing genetic algorithm for graph matching

Citation
Adj. Cross et al., Convergence of a hill-climbing genetic algorithm for graph matching, PATT RECOG, 33(11), 2000, pp. 1863-1880
Citations number
32
Categorie Soggetti
AI Robotics and Automatic Control
Journal title
PATTERN RECOGNITION
ISSN journal
00313203 → ACNP
Volume
33
Issue
11
Year of publication
2000
Pages
1863 - 1880
Database
ISI
SICI code
0031-3203(200011)33:11<1863:COAHGA>2.0.ZU;2-K
Abstract
This paper presents a convergence analysis for the problem of consistent la belling using genetic search. The work builds on a recent empirical study o f graph matching where we showed that a Bayesian consistency measure could be efficiently optimised using a hybrid genetic search procedure which inco rporated a hill-climbing step. In the present study we return to the algori thm and provide some theoretical justification for its observed convergence behaviour. The novelty of the analysis is to demonstrate analytically that the hill-climbing step significantly accelerates convergence, and that the convergence rate is polynomial in the size of the node-set of the graphs b eing matched. (C) 2000 Pattern Recognition Society. Published by Elsevier S cience Ltd. All rights reserved.