4

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?

Theelepel
  • 193
  • 6
  • Since the links in the question are not showing up, examples of Gray references: Xinjie, Tu and Mitsuo, Gen. Introduction to Evolutionary Algorithms. p42-43 (Springer, 2010) Whitley, Darrell. An Overview of Genetic Algorithms. Information and Software Technology, 43(14) (2001) – Theelepel Dec 20 '16 at 15:53

1 Answers1

5

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.

NWS
  • 3,080
  • 1
  • 19
  • 34
  • Thank you for your answer. But the question asks if there are _other_ benefits to Gray code. The minimal Hamming distance of neighboring integers is already mentioned in the questions and the references. – Theelepel Dec 23 '16 at 15:15
  • 1
    I didnt read your references as they werent linked.. and hamming walls werent mentioned directly in the q. – NWS Dec 23 '16 at 16:00