Representation and Hidden Bias: Gray vs. Binary Coding for Genetic Algorithms

Experimental results are presented that indicate Gray coding is generally superior to binary coding for function optimization using the genetic algorithm and suggests that Gray coding eliminates the “Hamming cliff” problem that makes some transitions difficult when using a binary representation.

Abstract

Experimental results are presented that indicate Gray coding is generally superior to binary coding for function optimization using the genetic algorithm. Analysis suggests that Gray coding eliminates the "Hamming cliff" problem that makes some transitions difficult when using a binary representation. We argue that the "Hamming cliff" is but one instance of hidden bias emerging from an interaction between search control heuristics and the knowledge representation.