A gene is one position in a genetic-algorithm chromosome. It holds a value for one optimization variable; the complete chromosome encodes a candidate solution. In a 0–1 knapsack problem, each gene corresponds to an item: 1 puts it in the crate, and 0 leaves it out. section 18.1.2
Choose gene values to match the problem. Knapsack genes are bits. For the traveling salesperson problem, each gene holds a vertex index, and the chromosome must contain each index exactly once. For maximum flow, one gene per edge holds a value from zero to that edge’s capacity; this range alone does not guarantee a valid flow. section 18.1.2 section 18.2.1 section 18.4.1
Operators must preserve the encoding’s constraints. Bit-string crossover can copy stretches of genes, but doing that to two vertex permutations may duplicate vertices. A permutation-safe crossover copies an initial stretch from one parent, then takes only unused vertices from the other. Mutation can change genes independently, allowing a population to reach values that crossover alone cannot produce when every parent agrees at a position. section 18.2.3 section 18.1.8
Listing 18.9 0-1 knapsack: Bit-wise mutation
function knapsackMutation(chromosome, mutationChance) #1
for i in {0,..,|chromosome|} do #2
if random() < mutationChance then
chromosome[i] ← 1 – chromosome[i] #3
return chromosome
Bit-wise knapsack mutation visits each gene and, with a given chance, replaces its value with 1 minus that value. section 18.1.8
Gene values may also constrain one another. Knapsack item choices are mostly independent, though a weight limit can create an indirect dependency. In a vertex permutation, assigning one index rules it out everywhere else. This interaction between variables is called epistasis. A bit-wise mutation pass visits every gene, so its running time grows with chromosome length; choosing the encoding also determines which constraint checks and repairs other operators need. section 18.1.10 section 18.1.8 section 18.1.2
