Quiz: Local Search
Methods of AI — 30/04/26
Q1 — Local Beam Search vs. Parallel Hill Climbing
Question: Local Beam Search selects the k best successors across all neighbors of all k current states combined, while Parallel Hill Climbing runs k searches independently. Why does this sharing of information make Local Beam Search fundamentally different — and what failure mode does it introduce that Parallel Hill Climbing doesn’t have?
Answer
In Parallel Hill Climbing, each of the k searches is fully independent — they never share information, so they explore k different regions of the state space in parallel. Local Beam Search pools all neighbors from all k states and picks the globally best k from that combined pool. This means useful information is shared: if one state is in a promising region, resources (search threads) get redirected there. The failure mode this introduces is concentration/lack of diversity: all k states can quickly cluster into the same small region of the state space, making the beam essentially equivalent to a single Hill Climbing search. This is worse than Parallel Hill Climbing because you lose the diversity advantage. The fix is Stochastic Beam Search: instead of always picking the k best, select k states probabilistically (higher probability for better states), preserving diversity.
Max’s answer:
Result:
Q2 — Simulated Annealing
Question: Simulated Annealing can accept downhill moves. Explain the acceptance formula, what role the temperature T plays, and why a slow cooling schedule is necessary for finding the global optimum.
Answer
A downhill move (Δ = value(neighbor) − value(current) < 0) is accepted with probability:
P = exp(Δ / T)
Temperature T: at high T, Δ/T is close to 0 → exp(0) ≈ 1 → nearly all moves accepted (broad exploration). At low T, Δ/T is very negative → exp → 0 → almost no downhill moves (convergence to local region).
Why slow cooling: if T decreases too fast, the algorithm freezes into a local optimum before it has had time to explore the global landscape. A sufficiently slow schedule (annealing) guarantees convergence to the global optimum in theory — the algorithm has time to escape any local optimum before T gets too low.
Uphill moves (Δ > 0) are always accepted regardless of T.
Max’s answer:
Result:
Q3 — Genetic Algorithms
Question: What is the uniform-order crossover, and why is standard 1-point crossover insufficient for permutation-encoded problems like TSP?
Answer
Problem with 1-point crossover on permutations: cutting two parent permutations and swapping tails often produces offspring with duplicate genes and missing genes — an invalid permutation. E.g. cities [1,2,3,4]: crossover of [1,3,2,4] and [2,4,1,3] at position 2 gives [1,3,1,3] — invalid.
Uniform-order crossover fixes this:
- Create a random binary template (e.g. 1,0,1,0)
- Child 1: copy genes from Parent 1 at positions marked 1 → [1,,2,]
- Fill gaps in the order genes appear in Parent 2 → [1,4,2,3]
Result is always a valid permutation. Needed for any problem where the chromosome is a permutation — TSP, scheduling, etc.
Max’s answer:
Result:
Score
Total: / 3