Improving locality in binary representation via redundancy

Abstract

Binary representation suffers from the problem of positional dependence, where the amplitude of phenotype variation is dependent on the position of the altered genotype bits. However, this is contrary to conventional variation operations that treat each genotype bit equally. Positional dependence can be attributed to the poor locality, which results in neighboring genotypes having low correlation in the phenotype space, reducing the effectiveness of systematic local search and evolutionary search based on small mutation steps. For this purpose, this paper will propose an alternative genotype-phenotype mapping for binary representation that introduces redundancy into the mapping and removes the exponential orderings between the alleles, hence improving the locality between the genotype and phenotype search space. Empirical study conducted based on distribution, locality, and mutation innovation revealed key algorithmic characteristics of the proposed code, and its practicality is validated by comparative studies based on different benchmark optimization problems. Possible approaches to resolve the overrepresentation problem due to redundancy will be suggested, exhibiting its flexibility and variability in implementation. © 2008 IEEE.