Improving the Locality Properties of Binary Representations

Adrian Grajdeanu and Kenneth De Jong

Abstract. Choosing representations and operators that preserve locality between genotype and phenotype space is an important goal in EA design. In the GA literature there has been considerable discussion of this issue with respect to the choice between standard binary encoding and Gray codes. In this paper we argue that an important and unappreciated aspect of such discussions is the degree to which locality preservation is isotropic in phenotype space (i.e., independent of location in phenospace). We show that using a traditional bit-flip mutation operator with either of these two representations results in rather weak isotropic locality. These insights lead to the design of a new binary mutation operator that increases isotropic locality. The results from an initial set of experiments supports the hypothesis that this improvement in isotropic locality leads to improvements in GA performance as well.

LNCS 3102, p. 1186 ff.

Full article in PDF

lncs@springer.de
© Springer-Verlag Berlin Heidelberg 2004