BibTeX entry

@PHDTHESIS{199910Richard_Myers,
  AUTHOR={Richard Myers},
  TITLE={Genetic Algorithms for Ambiguous Labelling Problems},
  SCHOOL={University of York},
  MONTH=Oct,
  YEAR=1999,
  URL={http://www.bmva.org/theses/1999/1999-myers.pdf},
}

Abstract

This thesis develops an optimisation framework within which the principle of least com-mitment can be applied to the solution of ambiguous consistent labelling problems. Thenatural optimisation method for such an approach is a hybrid genetic algorithm. The start-ing point is the refinement of an existing Bayesian approach to inexact labelling problems.Two criteria are presented which measure consistency in terms of the edit distance between labelled configurations and a dictionary of legal labellings. The new criteria havesignificantly lower time and space requirements than the original in the worst case.The genetic algorithm is applied to labelling problems, and its feasibility for ambiguouslabelling is demonstrated. The behaviour of the algorithm when labelling ambiguousand impossible line drawings is studied. Adapting the algorithm for ambiguous graphmatching problems necessitates a reformulation of the posterior measurement probability to take measurement ambiguity into account. The hybrid genetic algorithm with a gradientascent step is found to offer the best combination of optimisation performance and solutionyield. The hybrid algorithm is a significantly better optimiser than gradient ascent or thestandard genetic algorithm alone. The hybrid offers higher solution yields than otherevolutionary algorithms.The setting of the several parameters which control the genetic algorithm is studied using sets of factorial experiments. Empirical models for both labelling problems are derived.These models are used to find optimal conditions for the algorithm, and are found to bestable under extrapolation to problems up to three times as large as those in the originaltest set. The smaller than expected population size required for successful optimisationsuggests that the gradient ascent step is responsible for the optimisation performanceof the algorithm, and that the genetic algorithm operators work to furnish good initial guesses for gradient ascent.Three measures of the algorithm’s population diversity are presented. They are the Shan-non entropy, the total inter-cluster Hamming distance and the size of the gene pool. Thesemeasures indicate that population diversity decreases rapidly over the first few iterations,and inexorably thereafter. It is shown that solution yield can be improved without the in-troduction of any new parameters to the algorithm. Since the gradient ascent step appears to be mainly responsible for the optimisation performance, selecting the next generationat random without replacement increases diversity without compromising search.