Optimal 2D Model Matching Using a Messy Genetic Algorithm

J. Ross Beveridge

A Messy Genetic Algorithm is customized to find optimal many-to-many matches for 2D line segment models. The Messy GA is a variant upon the Standard Genetic Algorithm in which chromosome length can vary. Consequently, population dynamics can be made to drive a relatively efficient and robust search for larger and better matches. Run-times for the Messy GA are as much as an order of magnitude smaller than for random starts local search. When compared to a faster Key-Feature Algorithm, the Messy Genetic Algorithm more reliably finds optimal matches. Empirical results are presented for both controlled synthetic and real world line matching problems.


This page is copyrighted by AAAI. All rights reserved. Your use of this site constitutes acceptance of all of AAAI's terms and conditions and privacy policy.