A chromosome is an encoded candidate solution in an evolutionary algorithm. It contains a fixed number of genes, each storing an allele, or actual gene value. A collection of chromosomes forms a population. The genotype is the encoded representation; the phenotype is the resulting real-world solution. section 4.4 section 5.22
Choose an encoding that matches the structure of the problem:
- Use binary encoding when each decision is discrete, such as yes/no or included/excluded; represent each gene with 0 or 1. section 4.5
- Use real-value or permutation encodings when precise decimal values or ordered sequences matter; binary encoding can make those solutions harder to find. section 4.5
- Keep chromosomes valid during population initialization, using constraints, penalties, or a repair function to correct invalid solutions. section 4.6
- Modify chromosomes through evolutionary operators: crossover combines parent parts, while mutation changes selected gene values. section 4.13 section 4.15
Knapsack encoding
For 26 available items, create a 26-character chromosome. Gene index 3 contains 1 when item 3 is included and 0 when it is excluded. The complete string therefore describes one possible knapsack, while the population contains many such candidate solutions. Solutions exceeding the weight limit must be penalized, repaired, or excluded. section 4.4 section 4.6
Figure 4.11 Binary-encoding the Knapsack Problem
Visualizes how a chromosome encodes item inclusion and exclusion for the Knapsack Problem. section 4.4
