Local Search: When the Path Does Not Matter, Only the Destination

Building on lessons 4 and 5

In the previous two lessons, we studied pathfinding: given a start state and goal state, what is the cheapest path between them? The central question was about the path: how do we traverse from here to there?

But many real AI problems don’t fit this pattern at all. They have no natural start point and no goal state to aim for. Instead, they ask a fundamentally different question: given a vast space of possible solutions, which one is the best?

Consider hospital nurse scheduling. You are not trying to transform one schedule into another, there is no path to trace. You are trying to find a shift assignment that maximizes coverage, respects constraints, and satisfies preferences. The final configuration is everything.

Or think about tuning a machine learning model’s hyperparameters, designing an efficient chemical process, or arranging components in a spacecraft to minimize weight. These are optimization problems where the quality of the final solution dominates any notion of a path to reach it.

This is local search, and it represents one of the most practically useful algorithm families in applied AI.

The central quantity in this lesson is the objective function. That is just the numeric score we use to judge how good one candidate solution is. Local-search algorithms try to maximize or minimize that score without checking every possible candidate.

Core learnings about local search

• Local search optimizes a fitness or objective function over a space of candidates, without needing a target goal state in advance.
• Hill climbing is fast and intuitive but easily trapped in local optima, especially on rugged landscapes with many competing peaks.
• Random restart addresses this by sampling multiple starting points and keeping the best final solution, leveraging simple parallelism.
• Simulated annealing allows occasional acceptance of worse moves, controlled by a cooling temperature schedule, enabling escape from local traps.

Optimization as a mathematical problem

In earlier lessons, we cast problems as mappings: $f : X \to Y$. Optimization has different mathematics. Instead of asking “what output does this input map to?”, we ask “which candidate solution has the maximum quality?”

A formal optimization problem is written as:

$$\max_{s \in S} f(s)$$

In this expression, $\max$ means we are selecting the highest-quality state under objective $f$; we are not averaging over states and not optimizing a path.

This means: find the state $s$ from the feasible set $S$ that maximizes the value of $f(s)$.

Breaking it down:

• $S$ (solution space): all possible candidate configurations we could create. For scheduling, this is all possible shift assignments.
• $s$ (one state): a specific candidate solution. For scheduling, a particular assignment of nurses to shifts.
• $f(s)$ (fitness value): a scalar number measuring how good state $s$ is. For scheduling, this might be a score combining coverage, fairness, and violated constraints.

If this notation feels new, pause and visit Function notation for AI.

In practice, a local-search algorithm never examines all candidates in $S$, the space is too vast. Instead, at each step it uses a neighborhood function $N(s)$: given the current state $s$, what are the nearby states reachable by a single small modification? For scheduling, a neighbor might be “swap nurse A and B’s shifts.”

Why finding global optima is hard

Now imagine drawing the objective function $f(s)$ as a landscape where height represents fitness. Real landscapes are not smooth rolling hills. They contain multiple peaks and valleys.

When a greedy algorithm always climbs uphill, it reaches a local peak, a state better than all immediate neighbors. But somewhere else on the landscape, beyond a valley, sits a taller peak: the global optimum, the true best solution.

The greedy algorithm will never discover that global optimum if reaching it requires descending into the valley first (accepting lower fitness temporarily). The landscape metaphor reveals the core problem: naive one-step improvement is myopic.

Different local search strategies handle this challenge in different ways.

Three practical approaches to landscape exploration

Hill climbing is the simplest: at each step, examine all neighbors of your current state, move to the best one if any is an improvement, and stop if no neighbor is better.

Hill climbing is fast because it never wastes effort on bad moves. But that greedy behavior is also its weakness: it stops at any local peak, even if vastly better peaks exist elsewhere. On smooth landscapes with few local optima, hill climbing succeeds beautifully. On rugged, multi-peaked landscapes, it often disappoints.

Random restart hill climbing addresses this elegant limitation with a simple idea: run hill climbing multiple times from different random starting points, then return the best final state found across all runs.

Why does this work? Different starting regions typically flow downhill into different local optima, different basins of attraction. A basin of attraction is the region of starting points that all lead the algorithm toward the same local optimum. By sampling multiple basins, you increase your statistical chance of discovering deeper global optima. The computational cost is running the algorithm multiple times, but parallelism makes this very practical. Random restart is often used as a default baseline for difficult optimization problems.

Simulated annealing takes a fundamentally different approach: allow the algorithm to sometimes accept worse moves. The trick is controlling how often this happens using a temperature parameter $T$ that cools over time.

Early on, with high temperature $T$, the algorithm accepts worse moves frequently, exploring widely and escaping local traps. As temperature decreases, worse moves become rarer, and the algorithm focuses on exploiting high-fitness regions. The probability of accepting a worse move is:

$$P(\text{accept worse}) = \exp\left(\frac{\Delta}{T}\right), \quad \text{where } \Delta = f(s_{new}) - f(s_{old}) < 0$$

Read this equation term by term:

• $s_{old}$ is the current state; $s_{new}$ is the proposed neighbor.
• $\Delta$ is the fitness change; here $\Delta<0$ means the proposal is worse.
• $T$ is the temperature controlling exploration strength.
• $P(\text{accept worse})$ is the probability of still taking the worse move.

Small fitness drops with high temperature yield probability near 1 (almost certainly accept). Large drops or low temperature yield probability near 0 (almost certainly reject). Temperature is a smooth tuning knob between exploration and exploitation.

In the landscape visualization, $s_{old}$ is the algorithm’s current point on the curve and $s_{new}$ is the next candidate point it is considering. The quantity $\Delta$ is therefore the change in height between those two points: if the candidate point is lower, then $\Delta < 0$. The temperature $T$ is the exploration setting shown in the simulator status panel while simulated annealing runs. So this formula tells us how willing the algorithm still is to step downhill temporarily in order to escape a local peak and maybe reach the taller global peak later.

For a refresher on complexity and iteration budgets, see Big-O growth intuition for search.

Exploring fitness landscapes in practice

The interactive simulator lets you run all three strategies on the same landscape with different starting points. You see not just where each algorithm terminates, but how it behaves:

• Hill climbing finishes fast but often gets stuck in nearby local peaks.
• Random restart takes longer but usually finds the global peak by exploring multiple basins.
• Simulated annealing’s effectiveness depends on temperature tuning: too cold and it mimics hill climbing; too hot and it wastes cycles on very poor moves.

Walkthrough: Three strategies on a challenging landscape

Run this sequence to see how each method handles a multimodal fitness landscape:

1. Select Start in a valley (a low-fitness region between two peaks).
2. Run Hill Climbing. It will climb the nearest slope and stop at whichever local peak is closest. Note the final fitness value.
3. Reset and run Simulated Annealing. Because it accepts occasional worse moves (especially early on), it might escape the nearby peak and discover a taller peak elsewhere.
4. Reset and run Random Restart. It samples multiple starting points, so statistically at least one basin should lead toward the global optimum.

In human terms: algorithm choice is a quality-speed tradeoff. Hill climbing is fastest but risky on rugged landscapes. Random restart is slower but more robust statistically. Simulated annealing requires careful tuning but can be powerful when configured correctly. In practice, teams often use random restart as a baseline and add simulated annealing or other advanced methods only when landscapes prove particularly treacherous.

Relation to earlier lessons

• Lesson 4: uninformed traversal over search trees
• Lesson 5: heuristic path search (A*)
• Lesson 6: objective optimization where destination quality matters most

Concrete bridge: lessons 4-5 optimized path choice; this lesson optimizes final-state quality.

So this continues the same course pattern: formalize the problem, choose a traversal/update rule, then analyze cost vs quality tradeoffs.

Notation quick reference

Symbol	Meaning	Detailed Explanation
$S$	candidate solution space	Optimization in one mathematical frame
$s$	one candidate state	Optimization in one mathematical frame
$f(s)$	fitness/objective value of state $s$	Optimization in one mathematical frame
$N(s)$	neighborhood of state $s$	Optimization in one mathematical frame
$\Delta$	fitness change for a proposed move	Three local search strategies
$T$	annealing temperature	Three local search strategies
$\exp(\cdot)$	exponential function	Three local search strategies

Concept deep dives

• Function notation for AI
• Big-O growth intuition for search

What comes next

In lesson 7, we move to constraint satisfaction, where variables, domains, and constraints provide stronger structure and allow more aggressive pruning than generic local search.

Next: Lesson 7, Constraint Satisfaction Problems

---

References and Further Reading

• Kirkpatrick, S., Gelatt, C.D., and Vecchi, M.P. “Optimization by Simulated Annealing.” Science 220(4598), 1983.
• Russell, S. and Norvig, P. Artificial Intelligence: A Modern Approach, 4th ed. Pearson, 2020. Chapter 4.
• Glover, F. “Tabu Search, Part I.” ORSA Journal on Computing 1(3), 1989.
• Mitchell, Melanie. An Introduction to Genetic Algorithms. MIT Press, 1996.
• Winston, Patrick H. Artificial Intelligence, 3rd ed. Addison-Wesley, 1992. Chapter 14.

---

This is Lesson 6 of 18 in the AI Starter Course.