Evolving Better Representations Through Selective Genome Growth

The choice of how to represent the search space for a genetic algorithm (GA) is critical to the GA's performance. Representations are usually engineered by hand and fixed for the duration of the GA run. Here a new method is described in which the degrees of freedom of the representation---i.e. the genes---are increased incrementally. The phenotypic effects of the new genes are randomly drawn from space of different functional effects. Only those genes that initially increase fitness are kept. The genotype-phenotype map that results from this selection during the construction of the genome allows better adaptation. This effect is illustrated with the NK landscape model. The resulting genotype-phenotype maps are much less epistatic than unselected maps would be, having extremely low values of ``K''---the number of fitness components affected by each gene. Moreover, these maps are exquisitely tuned to the specifics of the epistatic fitness function, creating adaptive landscapes that are much smoother than generic NK landscapes with the same genotype-phenotype maps, with fitness peaks many standard deviations higher. Thus a caveat should be made when making arguments about the applicability of genetic properties of complex systems to evolved systems. This method may help to solve the problem of choice of representations in genetic algorithms.