A genetic algorithm keeps a population: a pool of candidate solutions that evolves from one generation to the next. Each individual carries a chromosome encoding one solution. This differs from simulated annealing, which keeps and adjusts a single solution at a time. section 18.1.1 section 18.1.3
Start by choosing a population size and a chromosome initializer appropriate to the problem. Call the initializer once per individual. Random initialization is a common way to obtain diversity, but generated chromosomes may violate problem constraints. Either prevent invalid chromosomes during initialization or assign them low fitness. An existing set of solutions can also serve as the initial population. section 18.1.3
A knapsack population
For a 0–1 knapsack problem, a chromosome can be a bit string: each bit indicates whether an item is included. Generate bits randomly to create individuals, then check the weight constraint or penalize overweight solutions through fitness. A population contains multiple such strings, not just the current best one. section 18.1.3
To produce the next generation, evaluate individual fitness and select candidates for mating. Elitism can copy strong individuals unchanged; thresholding can exclude weak ones. Select parents, apply crossover to create offspring, then apply mutations until the new population reaches the original size. Tournament selection, for example, samples k population members and returns the fittest sampled member. These choices affect which existing features survive and which new solutions are explored. section 18.1.5 section 18.1.6
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 pseudocode shows the population-to-population operation: preserve any elite individuals, then repeatedly select parents and add crossed-over, mutated offspring until the target size is restored. section 18.1.5
Population size is both an exploration choice and a workload choice. Initializing N individuals requires N initializer calls and storage for N individuals and their chromosomes; later generations likewise create a full population, with additional costs determined by fitness evaluation and the chosen operators. Compare runs by accounting for population size as well as generation count. In traveling-salesperson tests, 10 individuals converged in about 10 generations, while larger populations improved average results under some settings. Neither a larger population nor a genetic algorithm guarantees the optimum. section 18.1.3 section 18.2.4
