Local Search and Optimisation #

Local search improves one or a few complete candidate solutions by moving through their neighbourhoods. It is especially useful when the final configuration matters but the path used to reach it does not.

– Local Search Algorithms & Optimisation Problems

Hill Climbing Search
Local Beam Search
Online Search Agents

Learning Objectives #

distinguish path optimisation from state optimisation
explain states, neighbours and objective functions
apply hill climbing and its variants
recognise local maxima, plateaus and ridges
explain random-restart and stochastic hill climbing
describe local and stochastic beam search and trace one beam update

Big Picture #

flowchart TD
    S["Current state"] --> N["Generate neighbours"]
    N --> E["Evaluate values"]
    E --> B["Choose candidate"]
    B --> S
    B --> G["Stop condition"]

    style S fill:#E1F5FE
    style N fill:#FFF9C4
    style E fill:#EDE7F6
    style B fill:#C8E6C9
    style G fill:#C8E6C9

1. Path Optimisation vs State Optimisation ☆ #

In classical route search, the path is the solution. The agent must remember how it travelled from the start to the goal.