Genetic algorithms for ambiguous labelling problems

✍ Scribed by Richard Myers; Edwin R. Hancock

• Publisher: Elsevier Science
• Year: 2000
• Tongue: English
• Weight: 684 KB
• Volume: 33
• Category: Article
• ISSN: 0031-3203
• DOI: 10.1016/s0031-3203(99)00080-1

✦ Synopsis

Consistent labelling problems frequently have more than one solution. Most work in the "eld has aimed at disambiguating early in the interpretation process, using only local evidence. This paper starts with a review of the literature on labelling problems and ambiguity. Based on this review, we propose a strategy for simultaneously extracting multiple related solutions to the consistent labelling problem. In a preliminary experimental study, we show that an appropriately modi"ed genetic algorithm is a robust tool for "nding multiple solutions to the consistent labelling problem. These solutions are related by common labellings of the most strongly constrained junctions. We have proposed three run-time measures of algorithm performance: the maximum "tness of the genetic algorithm's population, its Shannon entropy, and the total Hamming distance between its distinct members. The results to date indicate that when the Shannon entropy falls below a certain threshold, new solutions are unlikely to emerge and that most of the diversity in the population disappears within the "rst few generations.