Quantitative Analysis of Genotype-to-phenotype Mappings in Evolutionary Algorithms

Abstract

The genotype-to-phenotype mapping is one of the definitive features of an evolutionary algorithm (EA). It determines how the genotypic variations can be translated to phenotypic improvements. Most genotype-to-phenotype mappings in EAs are redundant, i.e., multiple genotypes can map to the same phenotype. Phenotypes are accessible from one to another through point mutations. However, these mutational connections can be unevenly distributed among phenotypes. Quantitative analysis of such connections helps better characterize the genotype-to-phenotype mapping of an EA, and better understand the search ability of the algorithm. In this thesis, we quantitatively characterize how genotypes map to phenotypes and how mutational connections distribute among phenotypes in linear genetic programming algorithms. We propose two genotype-to-phenotype mapping mechanisms, where the execution and output of a linear genetic program are controlled by a regulator. We investigate how such regulatory mappings can alter the mutational connections among different phenotypes. We also compare the search ability of LGP using the conventional mapping versus the regulatory mappings, and observe that the regulatory mappings improve the efficiency in all three search scenarios, including random walk, hill climbing, and novelty search.