Genetic Representation and Encoding: Worked Examples and Exam Traps

A genetic algorithm searches chromosomes, but the problem is defined over candidate solutions. The chromosome 10110, the value 22 it decodes to, and the fitness 484 that value scores are three distinct layers, and collapsing them into a single number is what makes an otherwise easy question confusing. A poor encoding weakens the search before selection even begins, either by leaving valid solutions unreachable or by turning a one-step change in the solution into a five-bit change in the chromosome.

Genetic representation and encoding: the three-layer model

Representation specifies the chromosome's data structure and alphabet. Encoding maps a candidate solution to that chromosome, while decoding performs the reverse mapping before evaluation.

The full pipeline is:

genotype (chromosome) -> decoder -> phenotype (candidate solution) -> objective or fitness value

Fitness is an evaluation, not part of the encoding. In chromosome 10110, each bit is a gene. Its position is a locus, and a permitted value at that position is an allele. For example, the third locus from the left contains allele 1. One encoded candidate is a chromosome; a set of chromosomes is a population.

A good representation can express every useful candidate, decodes as unambiguously as possible, and makes nearby genetic changes produce manageable changes in the phenotype. Its mutation and crossover operators should also preserve feasibility or apply a clear repair rule.

Choose the encoding to match the solution space

Binary strings are convenient, but not universal.

Real-valued weights should not be forced through long binary strings without a reason. A tour or schedule naturally needs a permutation because every item must occur exactly once. The test is whether every legal solution has at least one chromosome, and whether the operators you intend to use can move between chromosomes without leaving the legal set.

Worked example: decode, evaluate, cross and mutate

Maximise f(x) = x^2 for integer x in [0, 31]. Use five unsigned bits b4 b3 b2 b1 b0, with weights 16, 8, 4, 2, 1.

• P1 = 10110 decodes to 16 + 0 + 4 + 2 + 0 = 22, so f(P1) = 22^2 = 484.

• P2 = 01101 decodes to 0 + 8 + 4 + 0 + 1 = 13, so f(P2) = 13^2 = 169.

Assume these parents have already been selected; the selection step that produces them is worked out in Genetic Algorithms in AI: A Worked One-Generation Example. One-point crossover after the third bit gives P1 = 101|10 and P2 = 011|01. The children are:

• C1 = 10101, which decodes to 21 and has fitness 21^2 = 441.

• C2 = 01110, which decodes to 14 and has fitness 14^2 = 196.

Now flip locus b1 of C1: 10101 -> 10111. The mutant decodes as 16 + 0 + 4 + 2 + 1 = 23, giving f(23) = 529. This improvement is incidental. Mutation is not directed and another flipped locus could reduce fitness.

Feasibility, redundancy and locality change the search

Restrict the domain to x in {0, 1, ..., 20}. There are 21 values, so ceil(log2 21) = 5 bits are required. Five bits provide 32 strings, leaving 32 - 21 = 11 invalid genotypes, codes 21 through 31.

An algorithm can reject or resample invalid offspring, penalise them, or repair them. Clamping every decoded value above 20 to 20 creates bias. The valid code 10100 and all 11 invalid codes from 10101 through 11111 map to 20, so phenotype 20 has 12 preimages.

Modulo decoding also creates redundancy. With x = unsigned_value mod 21, values 0 through 10 each have two preimages among 0 through 31. Values 11 through 20 have one. Uniform bit strings therefore give each value in the first group probability 2/32, but each value in the second group only 1/32. Direct bounded-integer encoding is cleaner when compatible operators are available.

Locality asks whether nearby genotypes produce nearby phenotypes. Adjacent values 15 = 01111 and 16 = 10000 differ in all five bits. Reflected Gray codes g(15) = 01000 and g(16) = 11000 differ in one bit. Gray code improves adjacency at this boundary, but does not make every crossover meaningful.

Genetic operators must respect the representation

Match the operator to the chromosome:

• Use bit flips and bit-level crossover for binary strings.

• Use bounded reset or creep mutation for integer genes.

• Use Gaussian mutation and arithmetic or blend crossover for real vectors.

• Use swap, insertion or inversion mutation with order-preserving crossover for permutations.

• Use subtree mutation and crossover for trees.

For example, let P1 = [A, B, C, D, E] and P2 = [C, E, B, A, D]. Cutting after position 3 and naively joining the P1 prefix to the P2 suffix gives [A, B, C, A, D]. It duplicates A and omits E.

Order crossover (OX) avoids that defect. Copy positions 2 and 3 from P1, [B, C], into the child. Scan P2 cyclically from position 4 as A, D, C, E, B, discard B and C, then fill child positions 4, 5 and 1 with A, D, E. The result is [E, B, C, A, D], containing every item once.

How exams turn encoding into short problems

Common tasks ask you to calculate chromosome length using ceil(log2 N), decode with an offset, trace crossover and mutation, count unused codewords, compare Hamming distances, or spot an operator that violates constraints.

Try two rapid checks:

1. For x in {5, ..., 20}, there are 16 values, so four bits suffice with x = 5 + unsigned_value. Code 1011 has unsigned value 11 and decodes to 5 + 11 = 16.

2. Six independent variables with four states each need two bits per variable, giving 6 x 2 = 12 bits.

Practise these under timed conditions in the GATE Test Series.

Traps to catch before choosing an answer

• Do not treat genotype, phenotype and fitness as one number. Here, 10110 is the genotype, 22 is the phenotype, and 484 is its fitness.

• Do not use floor(log2 N) or forget inclusive endpoints. Count candidates, apply ceil(log2 N), then account for unused strings.

• Do not assume mutation must improve, Gray code solves every locality problem, or ordinary one-point crossover preserves permutations.

Variation proposes candidates. Representation, decoding, feasibility rules and fitness decide what they mean. Where a genetic algorithm samples encodings and keeps what scores well, Dynamic Programming Explained with a Worked 0/1 Knapsack fills an exact table and returns a proven optimum, which is why an exact method wins whenever the state space is small enough to enumerate.

The short version and next step

Define the phenotype and constraints first. Choose a chromosome that covers the solution space with little ambiguity, pair it with feasibility-preserving operators, and test locality on exact neighbouring cases. Remember the main chain: 10110 -> 22 -> 484.

For the wider subject sequence, follow GATE Guidance by Sanchit Sir, and the GATE CS Exam Preparation Courses & Test Series category lists the broader course and test-series path.