Genetic algorithms for ambiguous labelling problems

Consistent labelling problems frequently have more than one solution. Most work in the field has aimed at disambiguating early in the interpretation p rocess, using only local evidence. This paper starts with a review of the l iterature on labelling problems and ambiguity. Based on this review, we pro pose a strategy for simultaneously extracting multiple related solutions to the consistent labelling problem. In a preliminary experimental study, we show that an appropriately modified genetic algorithm is a robust tool for finding multiple solutions to the consistent labelling problem. These solut ions are related by common labellings of the most strongly constrained junc tions. We have proposed three run-time measures of algorithm performance: t he maximum fitness of the generic algorithm's population, its Shannon entro py, and the total Hamming distance between its distinct members. The result s to date indicate that when the Shannon entropy falls below a certain thre shold, new solutions are unlikely to emerge and that most of the diversity in the population disappears within the first few generations. (C) 2000 Pat tern Recognition Society. Published by Elsevier Science Ltd. All rights res erved.