More distance functions for order-based encodings

Abstract

Distance functions are useful tools in the field of Genetic Algorithms as many diversity-prevention algorithms rely on an accurate measure of genotypic or phenotypic similarly when comparing two individuals in a population. Distance functions have been reported for binary-based and parameter based encodings however distance functions for order-based encodings have been limited to adjacency-based measures. Distance functions in the order-based domain require radically different calculation methods from traditional numerical and binary domain distance functions. This paper presents two new distance functions for order-based encodings, the exact match and the deviation distance functions. The exact match distance function considers exact matches in gene position and values to be a component of similarity between two individuals. The deviation distance function considers small degrees of positional deviation between matching gene values between two genotypes to be a component of similarity. A rigorous examination is made of both distance function with respect to the metric axioms and maximal and minimal values.