Epistasis Variance: Suitability of a Representation to Genetic Algorithms
Yuval Davidor · 1990
Abstract. The most problematic aspect in the application of a ge-netic 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 representa-tion and considerably affects the efficiency of a GA search. Both too much and too little nonlinearity detract from the relative efficiency of aGA. 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. 1. Background The schema theory [6,12J implicitly lists prerequisite features that a repre-sentation should exhibit in order to utilize a GA search, namely that with an above average probability, short, low-order schemata will combine and form a higher-order co-adapted schemata. The schema theorem shows that above average schemata will proliferate, but it does not indicate whether this proliferation will occur at the optimum rate. In that respect, it is self-evident that the representation is the primary aspect of a GA application and determines its performance. The importance of the representation was recognized, attention was given to the issue of building blocks (their size and number), but the effect of interdependency among the representation elements did not receive sufficient attention [3,5,8]. Only certain degrees of