Suppose a crate for Mars has a weight limit, and each available food has a weight and a calorie value. A candidate packing plan is useful only if it respects the limit; among acceptable plans, more calories are better. Fitness turns those requirements into a score that a genetic algorithm can use to compare candidates. Each candidate is encoded as a chromosome and belongs to an individual in a population. section 18.1.1 section 18.1.2 section 18.1.4
An individual’s fitness method returns a value measuring solution quality. Choose the score’s direction before implementing selection: larger values suit maximization, while smaller values can represent a cost to minimize. “High fitness” means better performance in either case, not necessarily a numerically larger result. A cost can also be negated to change the optimization direction. section 18.1.4 section 18.1.5
Design the score around both the objective and the constraints:
- For 0–1 knapsack, sum the calories of selected foods and check their total weight. An over-limit plan can receive fitness 0; alternatively, initialization and modification operators can prevent such plans, though that may reduce population diversity. section 18.1.4
- For the traveling salesperson problem, encode a route as a permutation and minimize the sum of distances between adjacent vertices. section 18.2.1
- For minimum vertex cover, minimize selected vertices plus a penalty for uncovered edges. Keeping a nearly valid candidate in the population may be more useful than discarding it outright. section 18.3.2
- For maximum flow, a proposed score can reward flow while accounting for violations of flow conservation; this design is outlined rather than implemented. section 18.4.1
A knapsack score
The chromosome 0100100 selects rice and tomatoes, worth 1,359,000 calories. Fitness computation also checks weight: the all-ones chromosome exceeds the crate’s limit and can receive 0 rather than its calorie total. section 18.1.4
Listing 18.13 Vertex cover: fitness function
function vertexCoverFitness(graph, chromosome) #1
fitness ← 0 #2
for gene in chromosome do #3
if gene == 1 then #4
fitness ← fitness + 1
for edge in graph.edges do #5
if chromosome[edge.source] == 0
and chromosome[edge.destination] == 0 then #6
fitness ← fitness + 2
return fitness
The vertex-cover pseudocode shows a fitness method counting selected vertices, then adding 2 for each edge whose endpoints are both unselected. Its two passes make the scoring work proportional to the chromosome length plus the number of edges. section 18.3.2
Fitness also drives reproduction. Selection favors better-scoring individuals; elitism can carry the best forward unchanged, while thresholding excludes poor candidates from mating. Tournament selection compares sampled individuals, whereas a roulette wheel assigns shares according to fitness values. These choices affect exploration: a hard cutoff can remove candidates that might become good after mutation. section 18.1.5 section 18.1.6
