Suppose a crate for a Mars mission has a weight limit, and each available food contributes calories. A candidate packing plan must say which foods to take. In a genetic algorithm, that plan is an individual's chromosome: an array of genes whose values encode one candidate solution. A population holds many such individuals so their solutions can evolve together. section 18.1.2 section 18.1.3
For this 0–1 knapsack problem, give each food one gene: 1 means pack it; 0 means leave it behind. The bit string is the genotype, while the selected goods are the phenotype. Here the mapping is one-to-one: identical chromosomes select identical goods and receive the same fitness. A bit string can still exceed the weight limit, so representation alone does not guarantee a valid solution. section 18.1.2 section 18.1.3
Figure 18.4 Examples of encoding chromosomes for the knapsack problem (the specific instance described in section 1.4). Two figures are shown: the differences in the genotypes (the two strings) are reflected in the phenotypes (the goods taken to Mars: wheat flour and tomatoes versus wheat flour, rice, and beans). The latter chromosome encodes the best solution for the instance of the problem summed up in table 18.1.
Compare the two bit strings with the goods they select to see how changing genes changes the packing plan. section 18.1.2
Once the encoding is chosen, the operators must respect it:
- Initialize a population by generating a chromosome for each individual. Random bits provide diversity; reject overweight plans during generation or give them low fitness later. section 18.1.3
- Recombine parents with crossover. For bit strings, cut both at one randomly chosen position and join opposite portions; a different cut can improve or worsen the child. section 18.1.7
- Mutate genes to recover choices absent from the population. For bit strings, independently flip each bit with a small probability; too much mutation can disrupt convergence. section 18.1.8
Not every problem fits bits. A traveling-salesperson tour is a permutation of vertex indices: each gene holds an integer, and no vertex may appear twice. Its crossover can copy a prefix from one parent, then scan the other parent and append only vertices not already copied. Simply joining two segments, as in knapsack, could repeat vertices. section 18.2.1 section 18.2.3
Listing 18.12 TSP: crossover
function tspCossover(chromosome1, chromosome2) #1
i ← randomInt(1, |chromosome1|-1) #2
newChromosome ← chromosome1[0:i] #3
genesFromChromosome1 ← new Set(newChromosome) #4
for j in {0,..,|chromosome2|-1} do #5
if not chromosome2[j] in genesFromChromosome1 then #6
newChromosome.add(chromosome2[j])
return newChromosome
The crossover pseudocode shows the copied prefix and the set used to exclude duplicate vertices. section 18.2.3
Encoding also determines which constraints need a fitness penalty or a specialized operator. A vertex-cover chromosome can reuse knapsack's bits and operators, but its fitness must account for uncovered edges. For maximum flow, one gene per edge can keep values within edge capacity; flow conservation still needs checking or a fitness adjustment. Genes may interact, too: choosing a vertex in a tour restricts every other position. section 18.3.2 section 18.4.1 section 18.1.10
For an n-gene bit string, initialization, a full mutation pass, and single-point copying each take O(n) time; storing P such chromosomes takes O(Pn) space. The practical trade-off is validity: simple encodings make operators easy to reuse, while constrained encodings require more careful generation, recombination, or fitness evaluation. section 18.1.3 section 18.1.7 section 18.1.8 section 18.2.1
