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.