Definition of a crossover based distance for genetic algorithms

The importance of operator-based metrics to characterize Evolutionary Algorithms is nowadays a clear and widely accepted fact. Defining a distance measure, or a measure of similarity, that is, in some sense “consistent” with (or “bound” to, or “based” on) the genetic operator(s) informally means that if two individuals are close to each other, or similar, one can be transformed into the other in a few applications of the operator(s). We propose a new crossover-based distance measure for GAs that quantifies the minimum number of crossover operations that have to be applied to transform an individual into another. For doing this, we need to consider all the possible next populations, which is a difficult task. We propose a solution to overcome this difficulty using schema theory. In particular, we show how it is possible to define a lattice structure over some sets of schemata represented in a GA population, and, exploiting some well known properties of lattices and of discrete dynamic systems, we define a distance between populations. We finally define a family of distances between GA individuals using the distance between populations defined beforehand.