Skip to content
Tutorials Center
My learning

Topics

Lesson 5 of 36 ยท Representation and Fitness

Binary and Gray Encoding

Learn how to encode numbers and choices as bit strings for a genetic algorithm, decode them, and why Gray code fixes the Hamming cliff of plain binary encoding.

Before a genetic algorithm can evolve anything, you must answer one question: how do I write a solution down as a chromosome? That choice is called the representation or encoding, and it decides which operators make sense, how large the search space is, and whether small changes to a chromosome produce small changes in the solution. Classic genetic algorithms use bit strings, and they are still the best place to start.

This lesson shows three common uses of bit strings: yes/no choices, whole numbers, and real numbers in a range. Then it tackles a subtle trap of plain binary numbers and the fix called Gray code.

Bits as choices

The simplest encoding has one bit per decision. In the knapsack problem you have items with weights and values and a bag with a weight limit. A chromosome of n bits says, for each item, "take it" (1) or "leave it" (0).

Python Knapsack as a bit string

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

There are only 2^6 = 64 bags here, but the same encoding handles 6,000 items just as well. The mapping is direct: gene i is the decision about item i. Mutation (flip a bit) means "change my mind about one item", which is a natural small change.

Bits as whole numbers

To evolve an integer, treat the bits as digits of a binary number. With L bits you can represent the integers 0 to 2^L - 1. Choose L so that the range is large enough.

Python
def bits_to_int(bits):
    n = 0
    for b in bits:
        n = n * 2 + b        # shift left, add the next bit
    return n

print(bits_to_int([1, 0, 1, 1]))   # 11

Bits as real numbers

A genetic algorithm can also tune a decimal parameter by scaling a binary integer into an interval [low, high]:

x = low + (high - low) * integer / (2^L - 1)

More bits mean finer precision: the smallest step is (high - low) / (2^L - 1). If you need accuracy of 0.001 over a range of length 10, you need L with 2^L > 10 / 0.001 = 10000, so L = 14.

For several variables you concatenate their bit blocks into one chromosome: for example 14 bits for x followed by 14 bits for y.

Python Decode a chromosome into two real numbers

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The Hamming cliff

Plain binary has a hidden flaw. The difference between two bit strings is their Hamming distance: how many positions disagree. In a good encoding, numbers that are close should have strings that are close. Plain binary does not guarantee that:

Number Binary Number Binary
7 0111 8 1000

The numbers 7 and 8 are neighbors, but their codes differ in all four bits. To move from 7 to 8 by mutation, the algorithm would have to flip four specific bits at once, which is extremely unlikely. Such places are Hamming cliffs. The fitness landscape has a smooth slope in numbers but a steep wall in bit space.

Gray code

Gray code reorders the bit patterns so that consecutive numbers always differ by exactly one bit. A binary number b converts to Gray with g = b XOR (b >> 1), and back by cumulatively XOR-ing the bits.

Python Binary versus Gray code

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

With Gray code, one mutation can move you to the next or previous number. A mutation can still produce a big change (flip the top bit), but small steps are always available, which makes the landscape much friendlier for hill-climbing and fine tuning.

If a numeric parameter encoded in plain binary seems to stall near a boundary like 127/128 or 255/256, try Gray code before changing anything else. Only the decoder changes: convert Gray to binary first, then to a number.

Strengths and weaknesses of binary encoding

Strengths

  • Simple, uniform genes, so one set of operators works for every problem.
  • Fits yes/no decisions perfectly (knapsack, feature selection, scheduling flags).
  • Easy to analyse theoretically.

Weaknesses

  • Real numbers cost many bits, and long chromosomes slow the search.
  • The precision is fixed by the bit count, and the range must be known in advance.
  • Mutating a high bit makes a huge jump, a low bit a tiny one, so genes are unequal in importance (Gray code softens, but does not remove, this).

For continuous problems, real-valued encoding usually works better. For orderings, use permutation encoding.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. How many bits per variable are needed for precision 0.01 on the range [0, 10]?

    The range needs 10 / 0.01 + 1 = 1001 values, and 2^10 = 1024 is the smallest power of two that covers them.
  2. 2. What is a Hamming cliff?

    In plain binary, 7 (0111) and 8 (1000) differ in all four bits, so a single mutation cannot step between them.
  3. 3. In Gray code, consecutive integers differ by

    That is the defining property of Gray code, and it removes Hamming cliffs between neighbors.
  4. 4. Which problem is the most natural fit for plain bit-string encoding?

    One bit per feature is a direct yes/no mapping. Tours need permutations, expressions need trees, and extreme precision makes bit strings very long.

Summary

  • A bit-string chromosome can encode choices, integers or real numbers in a range.
  • Real values use x = low + (high - low) * integer / (2^L - 1), and precision grows with L.
  • Plain binary has Hamming cliffs: neighboring numbers may differ in many bits.
  • Gray code makes neighbors differ by one bit; convert with n ^ (n >> 1).
  • Bit strings suit decisions and combinatorial flags; other problems need other encodings.

Next: Real-Valued Encoding