Suppose a crate for Mars has a weight limit, and you want to pack the most valuable combination of foods. A genetic algorithm searches for a good combination by evolving a population of candidate solutions rather than improving just one. Keeping several candidates lets the search explore different parts of the solution space; crossover can combine useful features from different candidates. section 18.1.1 section 18.1.2
Design the search around the problem’s constraints:
- Encode each candidate as a chromosome. For 0–1 knapsack, one bit per item says whether to pack it. For the traveling salesman problem (TSP), use a permutation of vertices: no vertex may appear twice. section 18.1.2 section 18.2.1
- Initialize a population, commonly at random. Either prevent invalid chromosomes during generation or account for constraint violations when evaluating them. section 18.1.3
- Define fitness from the objective. Knapsack rewards valuable contents; TSP minimizes total tour distance. Select parents using fitness, preserve selected individuals through elitism, create offspring by crossover, and apply mutations. section 18.1.5 section 18.2.1
Listing 18.4 Natural selection
function naturalSelection(
➥ population, elitism, selectForMating, crossover, mutations) #1
newPopulation ← elitism(population) #2
while |newPopulation| < |population| do #3
p1 ← selectForMating(population) #4
p2 ← selectForMating(population)
newIndividual ← crossover.apply(p1, p2) #5
for mutation in mutations do
mutation.apply(newIndividual) #6
newPopulation.add(newIndividual) #7
return newPopulation
The natural-selection pseudocode shows the generation loop: retain elites, select two parents, cross them, mutate the offspring, and repeat until the new population is full. section 18.1.5
Routing deliveries
For TSP, initialize tours as random permutations and use swaps of adjacent or randomly chosen vertices as mutations. A test with 10 candidates and a crossover chance of 0.7 reached the example’s best tour in about 10 generations on average. Comparing work fairly means counting candidates evaluated: 10 generations of 10 candidates are roughly 100 candidate-iterations, versus about 600 iterations reported for simulated annealing. These are test results, not a guarantee of the best tour on every run. section 18.2.1 section 18.2.2 section 18.2.4
Operators must respect the encoding: arbitrary changes to a permutation could violate its no-duplicates constraint. Tuning matters, too. In the TSP tests, crossover alone could plateau, while mutation helped explore new candidates; results varied with population size and operator probabilities. Highly dependent variables—high epistasis—can favor simulated annealing instead, so compare methods on smaller instances. Runtime work grows with the population and number of generations, while fitness evaluation is problem-specific. Expect a near-optimal answer, not proof of an optimum. section 18.1.2 section 18.2.4 section 18.5 section 18.2
Constraint handling can be part of fitness rather than a strict filter. For minimum vertex cover, a fitness function counts selected vertices and penalizes uncovered edges, allowing promising but invalid candidates to remain in the search. Validate the final candidate before returning it. section 18.3.2
