Introduction

Proper representations of the search space are crucial to the performance of genetic algorithms (GAs). For a genetic algorithm to perform better than random search, the representation and genetic operators combined must contain ``knowledge'' about the fitness function, in the form of correlations between parental fitnesses and offspring fitness distributions, which allows the genetic operator to take fitter individuals and produce still fitter offspring with non-vanishing probability [1]. This knowledge may be implicit, fortuitous, or by design in the choice of representation. A representation that facilitates the production of fitter variants can be said to yield evolvability.

In traditional fixed-length GAs, the representation is created in its entirety at the outset, Athena-like from the head of the designer. Its evolvability is predetermined. One hope in genetic algorithm research has been that good representations themselves could be produced through an evolutionary approach [2,3,4,5]. Here I discuss a method modeled after biological evolution for evolving representations with high evolvability.

In biological evolution, the genome has been built up incrementally by the acquisition of new genes. Many random gene additions occur through various genetic mechanisms. However, only those genes that produce an increase in fitness become stably incorporated in the genome. The nature of the gene's effect on the phenotype determines the chance that it will produce a fitness increase. Genes that disturb highly adapted organismal functions are most likely deleterious. Genes that preserve highly adapted functions while exploring novel functions have the best chance of producing a fitness increase, and thence being incorporated in the genome. Thus newly incorporated genes would tend to be modular in effect, with less deleterious side-effects (i.e. less pleiotropy). Modularity in the genotype-phenotype map would increase its evolvability[6].

In this paper, I develop an algorithm modeled after biological genome evolution as a strategy for evolving representations with high evolvability. The method is illustrated using Kauffman's NK adaptive landscape model, in which the structure of the genotype-phenotype map can be seen explicitly. The resulting adaptive landscapes are highly non-generic in their statistical properties, being much smoother than can be accounted for by their structure, allowing higher fitnesses to be reached that would be obtained through unselective generation of representations.