A binary string is a finite sequence of zeros and ones used as a chromosome to encode a candidate solution. Each position, or gene, represents a binary choice; in a 0–1 knapsack problem, 0 excludes an item and 1 includes it. The encoding gives a direct mapping between genotype and phenotype when each string uniquely identifies one solution. section 18.1.2
Use binary strings when the solution naturally consists of independent yes-or-no decisions:
- Initialize chromosomes randomly to create population diversity, or impose constraints during generation to avoid invalid solutions. section 18.1.3
- Reuse binary-string crossover and mutation operators across subset-selection problems with compatible constraints. section 18.3.2
- Replace the representation when solutions require values such as real numbers or permutations, then adjust operators to preserve constraints. section 18.1.2 section 18.2.1
Knapsack chromosome
For a shipment to Mars, a string such as 1010 selects the first and third items while excluding the second and fourth. In a vertex-cover optimizer, the same pattern selects vertices; fitness combines selected-vertex count with penalties for uncovered edges so promising near-solutions remain available. section 18.1.2 section 18.3.2
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 two knapsack chromosomes and see how differing bits produce different selected-item sets and solution quality. section 18.1.2
