What are the benefits of Gray code in evolutionary computation?

2.1k views Asked by At

Books and tutorials on genetic algorithms explain that encoding an integer in a binary genome using Gray code is often better than using standard base 2. The reason given is that a change of +1 or -1 in the encoded integer, requires only one bit flip for any number. In other words, neighboring integers are also neighboring in Gray code, and the optimization problem in Gray encoding has at most as many local optima as the original numeric problem.

Are there other benefits to using Gray code, compared to standard base 2?

1

There are 1 answers

2
NWS On

Gray Encoding is used to avoid the occurrences of Hamming Walls. As explained in this paper, Section 3.5.

Basically A Hamming wall is a point at which it becomes rare or highly unlikely that the GA will mutate in exactly the right way to produce the next step in fitness.

Due to the properties of Gray Coding, this is much less likely to happen.