Inhaltszusammenfassung

This paper discusses how the use of redundant representations influences the performance of genetic and evolutionary algorithms. Representations are redundant if the number of genotypes exceeds the number of phenotypes. A distinction is made between {synonymously} and {non-synonymously} redundant representations. Representation are synonymously redundant if the genotypes that represent the same phenotype are very similar to each other. Non-synonymously redundant representations do not allow g...This paper discusses how the use of redundant representations influences the performance of genetic and evolutionary algorithms. Representations are redundant if the number of genotypes exceeds the number of phenotypes. A distinction is made between {synonymously} and {non-synonymously} redundant representations. Representation are synonymously redundant if the genotypes that represent the same phenotype are very similar to each other. Non-synonymously redundant representations do not allow genetic operators to work properly and result in a lower performance of evolutionary search. When using synonymously redundant representations, the performance of selectorecombinative genetic algorithms (GAs) depends on the modification of the initial supply. Theoretical models for synonymously redundant representations are developed that show the necessary population size to solve a problem and the number of generations goes with O(2^{k_r}/{r}), where k_r is the order of redundancy and $r$ is the number of genotypic building blocks (BB) that represent the optimal phenotypic BB. As a result, uniformly redundant representations do not change the behavior of GAs. Only by increasing $r$, which means overrepresenting the optimal solution, does GA performance increase. Therefore, non-uniformly redundant representations can only be used advantageously if a-priori information exists regarding the optimal solution. The validity of the proposed theoretical concepts is illustrated for the binary trivial voting mapping and the real-valued link-biased encoding. The empirical investigations show that the developed population sizing and time to convergence models allow an accurate prediction of the empirical results.» weiterlesen» einklappen

Autoren

Klassifikation

DFG Fachgebiet:
Informatik

DDC Sachgruppe:
Informatik