This paper describes a novel framework for performing relational graph matching using genetic search. The fitness measure is the recently reported global consistency measure of Wilson and Hancock. The basic measure of relational distance underpinning the technique is Hamming distance. Our standpoint is that genetic search provides a more attractive means of performing stochastic discrete optimisation on the global consistency measure than alternatives such as simulated annealing. Moreover, the action of the optimisation process is easily understood in terms of its action in the Hamming distance domain. We provide some experimental evaluation of the method in the matching of aerial stereograms.