✦ LIBER ✦

Convergence of a hill-climbing genetic algorithm for graph matching

✍ Scribed by Andrew D.J. Cross; Richard Myers; Edwin R. Hancock

Publisher: Elsevier Science
Year: 2000
Tongue: English
Weight: 793 KB
Volume: 33
Category: Article
ISSN: 0031-3203
DOI: 10.1016/s0031-3203(99)00171-5

No coin nor oath required. For personal study only.

✦ Synopsis

This paper presents a convergence analysis for the problem of consistent labelling using genetic search. The work builds on a recent empirical study of graph matching where we showed that a Bayesian consistency measure could be e$ciently optimised using a hybrid genetic search procedure which incorporated a hill-climbing step. In the present study we return to the algorithm and provide some theoretical justi"cation for its observed convergence behaviour. The novelty of the analysis is to demonstrate analytically that the hill-climbing step signi"cantly accelerates convergence, and that the convergence rate is polynomial in the size of the node-set of the graphs being matched.

📜 SIMILAR VOLUMES

Use of a novel Hill-climbing genetic alg

Use of a novel Hill-climbing genetic algorithm in protein folding simulations

✍ Lee R Cooper; David W Corne; M.James C Crabbe 📂 Article 📅 2003 🏛 Elsevier Science 🌐 English ⚖ 280 KB

We have developed a novel Hill-climbing genetic algorithm (GA) for simulation of protein folding. The program (written in C) builds a set of Cartesian points to represent an unfolded polypeptide's backbone. The dihedral angles determining the chain's configuration are stored in an array of chromosom

Performance of a genetic algorithm for t

Performance of a genetic algorithm for the graph partitioning problem

✍ Keiko Kohmoto; Kengo Katayama; Hiroyuki Narihisa 📂 Article 📅 2003 🏛 Elsevier Science 🌐 English ⚖ 653 KB

MATHEMATICAL l OWl"lD ." \*ClaNCC d COMPUTER DIRmCT\* MODELLING Mathematical and Computer Modelling 38 (2003)