Quiz: Local Search
Methods of AI — SoSe 2026
Q1 — Local Search
Question: What is the key difference between Local Beam Search and running k independent Hill Climbing searches in parallel?
Answer
In k independent Hill Climbing runs, each search is completely isolated — states don’t communicate.
In Local Beam Search, all k states share their successors. At each step, all successors of all k states are pooled together, and only the globally best k are kept. This means the beams concentrate information toward promising regions of the search space. Local Beam Search is NOT the same as parallel HC.
Max’s answer: LBS creates k beams at random locations and the creates n children, where their distance to the parent beam is defined by the step size. then the algorithm takes all children from all aprents (k x n) and take the best k children, makes them to the new parents and starts the process over. parallel HC on the other hand, the beams do not talk to each other and only take the best children among their own. that leads to beams being stuck in a local minima.
Result:
Q2 — Local Search
Question: Hill Climbing never makes downhill moves. What is the consequence for its performance, and which variant addresses this?
Answer
Consequence: Hill Climbing can get stuck in local optima — states that are better than all neighbors but not globally optimal.
Simulated Annealing addresses this by allowing downhill moves with probabilityexp(Δ/T), where T is temperature. At high T, many downhill moves are accepted (exploration). As T decreases, fewer are accepted (exploitation). With a slow enough cooling schedule, SA is guaranteed to find the global optimum.
Max’s answer: the consequence is that HC often then converges in a local minimum of which it cannot escape. There are variants which try to avoid this issue:
Random Start HC: restarts HC once it converged. Therefore, there is a higher chance of finding the global minimum while maintaining relatively low computing cost.
Result:
Q3 — Local Search
Question: Explain the role of the three operators in a Genetic Algorithm: selection, crossover, and mutation.
Answer
- Selection: chromosomes are chosen for reproduction with probability proportional to fitness (fitness-proportionate selection). Better solutions reproduce more often.
- Crossover (Reproduction): two parent chromosomes are combined at a crossover point to produce offspring. This recombines good partial solutions. For permutations, naive crossover is invalid — use uniform-order crossover instead.
- Mutation: one gene is randomly changed with a small probability. This maintains diversity and allows exploration of areas not reachable by crossover alone. Without mutation, the population can converge too early.
Max’s answer:
Result:
Q4 — Local Search
Question: What is the tradeoff between small and large neighborhoods in Hill Climbing?
Answer
- Small neighborhood: faster to evaluate, but higher risk of getting stuck in local optima (can’t “jump” past bad states).
- Large neighborhood: slower to evaluate (more neighbors to check), but lower risk of local optima — the algorithm can reach more states in one step.
General rule: large neighborhoods are better for escaping local optima but cost more per step.
Max’s answer:
Result:
Q5 — Local Search
Question: How does Random-Restart Hill Climbing address the local optima problem, and what guarantee does it provide?
Answer
Random-restart HC runs n independent HC searches, each starting from a randomly generated initial state. When one run gets stuck in a local optimum, simply restart from a new random state.
Guarantee: as the number of restarts n → ∞, the probability of finding the global optimum → 1. With finite restarts, there’s no hard guarantee, but the probability grows with each run.
This is simple but often highly effective in practice.
Max’s answer:
Result:
Q6 — Local Search
Question: In Simulated Annealing, when is a downhill neighbor accepted? Write the formula.
Answer
A downhill move (Δ = value(neighbor) − value(current) < 0) is accepted with probability:
P = exp(Δ / T)
where T is the current temperature.
- When T is large: Δ/T is close to 0 → exp(0) = 1 → high acceptance probability.
- When T is small: Δ/T is very negative → exp → 0 → low acceptance probability.
Uphill moves (Δ > 0) are always accepted (probability > 1, so always take them).
Max’s answer: wenn delta < 0, und T > 1, dann P = exp (delta/T) ist die formel
Result:
Q7 — Local Search
Question: Why does the uniform-order crossover exist, and when is it needed?
Answer
Problem: when chromosomes represent permutations (e.g., in TSP — visiting each city exactly once), naive 1-point crossover produces invalid offspring with duplicate or missing genes.
Uniform-order crossover fixes this: take a random binary template; copy genes from parent 1 at positions marked “1”; fill remaining positions in the order they appear in parent 2. Result is always a valid permutation.
It’s needed whenever the chromosome must be a permutation — TSP, scheduling, etc.
Max’s answer:
Result:
Beyond the lecture (optional)
These questions go beyond the SoSe 2026 lecture slides (textbook / external additions). Kept for depth, not exam-critical.
Q8 — Local Search
Question: What are the failure modes of Hill Climbing (name 3 and explain briefly)?
Answer
- Local maxima: state better than all neighbors, but not globally optimal. HC stops here.
- Plateaus: flat region where all neighbors have equal value. HC can’t determine direction → may wander randomly or stop.
- Ridges: narrow region of high value surrounded by lower terrain. HC must move diagonally to stay on ridge, but neighborhood moves are orthogonal → may fall off.
Solutions: stochastic HC, random restart, simulated annealing, or larger neighborhoods.
Max’s answer:
Result:
Score
Total: / 8