GA: Representation & Encoding

Source: Unit 5 §3

GAs do not work with solutions directly; they work with an encoded representation of them. Bit strings are the most common choice because crossover and mutation are trivial to apply to them. The available options are binary strings, real-number coding, integer coding, permutations, random keys, and trees or lists.

Binary encoding and decoding

An $n$-bit string represents an integer from $0$ to $2^n - 1$, which is $2^n$ distinct values. To map it onto a real interval $[X_i^l, X_i^u]$:

$$X_i = X_i^l + \frac{X_i^u - X_i^l}{2^n - 1} \times (\text{decoded value of the string})$$

Decoding 1010 with n = 4 over the range [4, 25]. The bit string is read as an integer first, then stretched onto the real interval.

To go the other way and choose a string length for a required precision $p$:

$$S_l = \log_2\left(\frac{X^u - X^l}{p}\right)$$

≡FactsThe knapsack encoding

Items have a value and a size, and the knapsack has a capacity. Each bit says whether the corresponding item is in the knapsack, so the chromosome is exactly as long as the item list, and fitness maximises total value subject to not exceeding capacity.

The other representations

Representation	Use and example
Real-valued	Continuous genes, with precision limited only by the machine.
Integer	Discrete non-binary genes, e.g. the directions {N,S,E,W} coded as {1,2,3,4}.
Permutation (path/order)	An 8-city TSP tour 3-5-8-1-4-2-6-7 becomes the chromosome [3 5 8 1 4 2 6 7].
Random keys	Encode with random numbers in (0,1) and sort to recover the permutation: [0.45 0.68 0.91 0.11 …] → 3-5-8-1-…. Used in machine scheduling, vehicle routing and quadratic assignment.
Tree	The chromosome is a tree, encoded by edge, by vertex, or by both.

⚠GotchaA permutation cannot use ordinary crossover

Cutting two tours at a point and swapping the tails will usually produce a chromosome that visits one city twice and another never. Permutation encodings need their own operators - order crossover and position-based crossover, both covered under genetic operators - which is exactly why the encoding choice and the operator choice cannot be made independently.

Prüfer code

A Prüfer code is a vertex encoding that represents a tree uniquely, with length $n - 2$ for $n$ nodes.

→StepsBuilding the code

1. Find the leaf with the smallest label.
2. Record its neighbour in the Prüfer code.
3. Remove that leaf.
4. Repeat until only two nodes remain.

For a six-node tree this yields a code of length $6 - 2 = 4$, for example 3 3 1 5.

Representing hypotheses as bit strings

Hypotheses, meaning if-then rules, are also encoded as bit strings. For Play Tennis, use one bit per possible value of each attribute, where a 1 means that value is allowed.

≡FactsReading the bits

• Outlook has 3 values, so 3 bits. 001 means Outlook = Overcast; 011 means Outlook = Rainy or Overcast; 111 means don't care, i.e. any value.
• Wind has 2 values, so 2 bits. 10 means Strong.
• PlayTennis, the postcondition, has 2 values. 10 means Yes.

Concatenating gives conjunctions and then whole rules:

(Outlook = Overcast ∨ Rain) ∧ (Wind = Strong) → 101 10 (precondition)

 

IF Wind = Strong THEN PlayTennis = Yes → 111 10 10

└ 111 = don't care on Outlook ┘ └ Wind = Strong ┘ └ Play = Yes ┘

⚠GotchaBit orderings differ between examples

The slides use slightly different bit orderings for Outlook in different places (elsewhere 100 is Rainy). The principle is what is being examined: one bit per value, 1 means allowed, all-ones means don't care. Note also that a set of rules is the concatenation of single rules, so it need not be a fixed-length chromosome.