Complex Systems

Epistasis Variance: Suitability of a Representation to Genetic Algorithms Download PDF

Yuval Davidor
Department of Applied Mathematics and Computer Science,
Weizmann Institute of Science, Rehovot 76100, Israel


The most problematic aspect in the application of a genetic algorithm (GA) is the coding of the problem. In superficial applications, choosing a representation may appear simple. Yet it is really an art because the theory provides only partial directives and is not always fully applicable. Different representations incorporate varying degrees of nonlinearity among the representation elements. This interwoven nonlinearity is directly coupled with the representation and considerably affects the efficiency of a GA search. Both too much and too little nonlinearity detract from the relative efficiency of a GA.

This paper suggests that measures to qualify the suitability of a representation to a GA search can be developed with the concept of epistasis (a biological term that states the amount of intrachromosome gene interaction). By viewing the representation as a whole, being more than the sum of its composing parts, the discussion on epistasis in GAs reveals several fundamental features of GAs and leads to a unique mechanism for "spying'' on the suitability of a representation to a GA.