Lernzettel: Local Search
Methods of AI — SoSe 2026 · 1-page exam sheet
For more depth: Search Algorithms (full reference with all algorithms, pseudocode, deep explanations) · quiz_local-search_30-04-26 · quiz_local-search_2026-04-30
Core Ideas
- Local search keeps only the current state — no path history, no frontier. Goal: find a good state, not a route.
- Move to neighboring states according to an objective function
f(s)to maximize. - Useful when the solution is the state (e.g. 8-Queens, TSP).
- Plain HC only finds local optima — SA, beam search, and GAs add randomness or population to escape them.
- All variants trade exploration (escape local optima) vs. exploitation (climb toward improvement).
Mini-glossary
| Term | Meaning |
|---|---|
| State | one complete configuration (not a path) |
| Neighborhood | states reachable from current in one step |
Objective f(s) | value of state s; we maximize |
| Local optimum | no neighbour strictly better — HC stops here |
| Plateau / ridge | flat region / long detour-only ascent |
Temperature T | SA’s willingness to accept downhill moves |
| Cooling schedule | function decreasing T over time |
| Beam | k states maintained in beam search |
| Chromosome | GA-encoded state |
| Fitness | GA name for objective |
| Crossover / mutation | GA reproduction / random gene change |
| Memetic algorithm | GA + per-child local search |
⭐ Full glossary with examples → Glossary
Formulas & Notation
| Symbol | Meaning |
|---|---|
f(s) | Objective function (value of state s) |
neighbors(s) | Set of states reachable in one step |
Δ = f(s') − f(s) | Value change (negative = downhill) |
exp(Δ/T) | SA acceptance probability for downhill move |
schedule(t) | Cooling function — slides: Stepwise Linear, Delayed Stepwise Linear only |
k | Beam width / population size |
Common Exam Traps ⚠️
- Local Beam Search ≠ k parallel HCs. In beam search, all k states share their successors and compete — it’s one coordinated search.
- Plain HC never accepts a downhill move. Per the slides, Stochastic HC also requires a strictly improving neighbour — so it does NOT escape plateaus. Only SA and (indirectly) GAs accept worse states.
- Random-restart HC is called “Random-restart (or parallel) Hill-Climbing” in the slides. P(global optimum) → 1 only as n → ∞ — not for finite n.
- Cooling schedule: slides only list Stepwise Linear and Delayed Stepwise Linear (no exponential). Slower cooling increases the probability of a high-quality solution — slides do not state a global-optimum guarantee. (Geman & Geman is textbook R&N, not these slides.)
- Neighborhood-size tradeoff: small = fast per step but more local optima; large = slower per step but fewer local optima.
- Permutation problems (TSP): naive 1-point crossover yields invalid solutions — use uniform-order crossover or a repair operation.
exp(Δ/T)sign: Δ for downhill is negative, so the exponent is non-positive and the probability lies in (0, 1].
When do Genetic Algorithms fail badly? (3 modes)
GAs bet on the Building Block Hypothesis: good, separable sub-chunks (“schemata”) recombine into better solutions within a diverse population. They fail when one of those three assumptions (good · separable · diverse) breaks:
- Deceptive problems — locally high-fitness building blocks combine into globally bad offspring; the landscape misleads crossover (the true optimum needs blocks that look worse in isolation). Toy: a trap function where “add 1-bits” always looks better but the optimum is all-zeros.
- Tightly-coupled encodings — genes only make sense together, so naive crossover destroys structure. Classic: permutations (TSP) — 1-point crossover yields invalid tours (duplicate/missing cities) → must use a structure-respecting operator (uniform-order crossover, OX, PMX, or a repair step).
- Premature convergence — population collapses onto one (sub-optimal) solution too early → diversity lost → crossover of near-clones yields nothing new → stuck at a local optimum. Fixes: lower selection pressure, fitness sharing/niching, bigger population, more mutation.
One-liner: GAs assume good, separable building blocks recombine within a diverse population — they fail exactly when good / separable / diverse breaks.
Quick Comparison Table
| Algorithm | Downhill? | Memory | Escapes local optima? | Guarantees |
|---|---|---|---|---|
| Hill Climbing | No | Current state | No | Local optimum |
| Stochastic HC | No | Current state | No (strict improvement required) | Local optimum |
| Random-Restart HC | No | Current state per chain | Yes across restarts | P(global) → 1 as n → ∞ |
| Simulated Annealing | Yes (prob.) | Current state + T | Yes | Slides: slower cooling ⇒ higher P(high-quality); no global guarantee in slides |
| Local Beam Search | No | k states | Limited (within beam) | Local optimum (joint) |
| Stochastic Beam Search | No | k states | Better than Local Beam | Heuristic |
| Genetic Algorithm | Yes (indirect) | Population | Yes | Heuristic |
⭐ Full algorithm reference (pseudocode + complexity + pros/cons for all 9) → ALGORITHMS (full reference) ⭐
⭐ Quick algorithm chooser (when to use which) → Quick algorithm chooser
Related Q&A & Notes
Quizzes
- quiz_local-search_30-04-26 — 8 Qs, mixed difficulty
- quiz_local-search_2026-04-30 — additional quiz
Targeted exam questions in Questions for Methods of AI
- Q1–16 (basic) · Q85 (classical vs. local search) · Q90 (Simulated Annealing) · Q105–109 (deep / exam-trap:
exp(Δ/T), Beam Search edge cases, Parallel HC vs. Beam, stalled GA, convergence guarantees)
Atomic notes
- Search Algorithms · Hill Climbing · Local Beam Search · Simulated Annealing · Temperature in neighbour selection · Genetic Algorithms · Paper Review Genetic Algorithms · Stochastic Diffusion Search · cul-de-sac obstacles
See also
Tags: methods-of-ai lernzettel ai-generated
Full reference: Search Algorithms
Quiz: quiz_local-search_30-04-26
Superlink: Methods of AI Lecture
Questions hub: Questions for Methods of AI
Created: 30/04/26