Local Search

Local search is essentially greedy descent:

$$s_{k+1}\in \underset{s^{\prime }\in N(s_k)}{\mathrm{argmin}}E(s^{\prime })$$

where we always take the move that results in the lowest immediate cost. This is essentially hill climbing search.

It’s very effective at intensification/exploitation, but stops at local optimum relative to the neighborhood $N(\cdot )$. It cannot cross a barrier without allowing non-improving moves.

To be more specific: in order to escape, we need a mechanism that occasionally accepts worse solutions:

$$\Delta E=E(s^{\prime })-E(s)$$

• if $\Delta E\le 0$: Improving (or equal) move
• if $\Delta E>0$: Uphill move (temporary degradation)

To do this, we turn to Simulated Annealing and Tabu Search.