On the Locality of Representations

摘要

It is well known that using high-locality representations is important for efficient evolutionary search. This paper discusses how the locality of a representation influences the difficulty of a problem when using mutation-based search approaches. The results show that high-locality representations do not change problem difficulty. In contrast, low-locality representations randomize the search process and make problems that are phenotypically easy for mutation-based search more difficult and phenotypically difficult problems more easy.