Locality, Distance Distortion,and Binary Representations of Integers

This paper investigates how the performance of evolutionary search is inuenced by thelocality and distance distortion of the used representation. The locality of a representationdescribes how well neighboring phenotypes correspond to neighboring genotypes. The distancedistortion measures whether the distances between individuals are preserved when mapping thephenotypes onto the genotypes. When using mutation as the main search operator, perfectlocality ensures that the difficulty of the problem is not changed by the representation. Inanalogy, representations that preserve the distances between individuals guarantee that thedifficulty of the problem remains unchanged for crossover-based search.[...]