Evolving Better Representations through Selective Genome Growth

Lee Altenberg

In Proceedings of the IEEE World Congress on Computational Intelligence, pp. 182-187. 1994.

Abstract
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 a 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 constructional 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 generic maps would be. They have 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 random fitness functions, and achieve fitnesses many standard deviations above generic NK landscapes with the same \gp\ maps. The evolved maps create adaptive landscapes that are much smoother than generic NK landscapes ever are. Thus a caveat should be made when making arguments about the applicability of generic properties of complex systems to evolved systems. This method may help to solve the problem of choice of representations in genetic algorithms.