Redundant Representations in Evolutionary Computation

This paper investigates how the use of redundant representations influences the performance ofgenetic and evolutionary algorithms. Representations are redundant if the number of genotypesexceeds the number of phenotypes. A distinction is made between synonymously and nonsynonymouslyredundant representations. Representation are synonymously redundant if thegenotypes that represent the same phenotype are very similar to each other. Non-synonymouslyredundant representations do not allow genetic operators to work properly and result in a lowerperformance of evolutionary search. When using synonymously redundant representations, theperformance of selectorecombinative genetic algorithms (GAs) depends on the modification ofthe initial supply. Theoretical models are developed that show the necessary population size tosolve a problem and the number of generations goes with O(2kr /r), where kr is the order ofredundancy and r is the number of genotypic building blocks (BB) that represent the optimalphenotypic BB.[...]