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 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 modified genetic algorithm is a robust tool for finding 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 fitness 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 first few generations.