A genetic algorithm is run for 100 generations on a combinatorial optimization problem. By generation 50, all individuals in the population are nearly identical and the best fitness value has not improved in 30 generations. What has most likely caused this?
AThe fitness function is poorly designed and does not distinguish good solutions from bad ones
BSelection pressure was too strong, causing premature convergence — the population lost diversity before exploring the search space adequately
CThe mutation rate was too high, continuously destroying good solutions
DThe crossover rate was too low, preventing offspring from inheriting useful traits
When all individuals become nearly identical, the population has converged — diversity is gone. Crossover between identical individuals produces no new information, and without diversity there is no way to escape the local optimum. This premature convergence is the signature failure mode of overly aggressive selection, where high-fitness individuals reproduce so dominantly that the population rapidly homogenizes. Option C (high mutation) would cause the opposite problem — fitness values would be erratic rather than stagnant. The fix involves reducing selection pressure, reintroducing diversity through higher mutation or migration, or using diversity-preserving mechanisms like niching.
Question 2 Multiple Choice
Why are genetic algorithms well-suited for optimization problems where the landscape has many local optima, while gradient-based methods struggle?
AGenetic algorithms can compute gradients by comparing fitness values of adjacent solutions, giving them better directional information
BGenetic algorithms maintain a population exploring multiple regions simultaneously, and crossover can jump across valleys between local optima rather than being trapped by local gradient descent
CGenetic algorithms always converge to the global optimum, whereas gradient methods can only find local optima
DGenetic algorithms work faster because they evaluate fewer candidate solutions per iteration
Gradient methods follow the gradient downhill (or uphill for maximization) from a single point — once they reach a local optimum, they stop. A GA's population explores many points concurrently, and crossover can recombine partial solutions from different peaks, potentially creating offspring that 'jump' across the valley between local optima. Note that option C is wrong: GAs are not guaranteed to find the global optimum — they are heuristics with no such guarantee. Option D is also wrong: GAs typically require far more fitness evaluations than gradient methods on smooth problems, making them less efficient when gradients are available.
Question 3 True / False
Maintaining high population diversity in a genetic algorithm helps prevent premature convergence by ensuring multiple distinct regions of the search space are explored simultaneously.
TTrue
FFalse
Answer: True
This is the core reason population-based search outperforms single-point methods on multimodal landscapes. Each individual in the population represents a different candidate solution in a different region of the search space. When crossover combines two diverse individuals, the offspring may land in a new region not yet explored by either parent. If the population converges to near-identical individuals, crossover becomes ineffective (copies crossed with copies produce copies), and only mutation provides any exploration — which at low mutation rates is very slow.
Question 4 True / False
A higher mutation rate usually improves genetic algorithm performance by continuously introducing new genetic material and preventing stagnation.
TTrue
FFalse
Answer: False
Mutation rate controls the exploration-exploitation tradeoff. A very low rate means the algorithm relies almost entirely on recombining existing material — useful for exploiting discovered structure, but slow to explore new regions. A very high rate means good solutions are constantly disrupted before they can be selected and propagated — the search degenerates toward random sampling. Typical effective mutation rates are 0.001–0.01 per gene. The right rate depends on chromosome length, fitness landscape ruggedness, and population size. 'More mutation is always better' is a common misconception.
Question 5 Short Answer
Explain the tension between exploitation and exploration in genetic algorithms, and describe how crossover and mutation each contribute to this balance.
Think about your answer, then reveal below.
Model answer: Exploitation means refining and building on solutions already known to be good — converging toward the best-discovered region. Exploration means searching new, unvisited regions — diversifying the population. Too much exploitation leads to premature convergence on a local optimum; too much exploration wastes evaluations on random regions and never refines good solutions. Crossover primarily drives exploitation: it recombines high-fitness parents to create offspring that inherit their good building blocks, concentrating search near already-promising regions. Mutation primarily drives exploration: by randomly flipping genes, it creates occasional novel individuals that extend the search into areas the population has not yet visited. The interplay between these two operators — controlled by crossover and mutation rates, along with selection pressure — determines whether the algorithm effectively navigates the tradeoff.
Recognizing the exploitation-exploration tradeoff is the central insight for using and tuning GAs effectively. It explains why neither 'always crossover' nor 'always mutate' is sufficient — and why elitism (preserving the best individual) helps exploitation without sacrificing the balance, since it guarantees the best-found solution is never discarded.