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.