\documentclass{article}
\usepackage{fleqn}
\usepackage{epsf}
\usepackage[dvips]{color}
\usepackage{aima2e-slides}
\begin{document}
\begin{huge}
\titleslide{Local search algorithms}{Chapter 4, Sections 3--4}
\sf
%%%%%%%%%%%% Slide %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\heading{Outline}
\blob Hill-climbing
\blob Simulated annealing
\blob Genetic algorithms (briefly)
\blob Local search in continuous spaces (very briefly)
%%%%%%%%%%%% Slide %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\heading{Iterative improvement algorithms}
In many optimization problems, \emph{path} is irrelevant;\\
the goal state itself is the solution
Then state space = set of ``complete'' configurations;\nl
find \emph{optimal} configuration, e.g., TSP\nl
or, find configuration satisfying constraints, e.g., timetable
In such cases, can use \defn{iterative improvement} algorithms;\\
keep a single ``current'' state, try to improve it
Constant space, suitable for online as well as offline search
%%%%%%%%%%%% Slide %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\heading{Example: Travelling Salesperson Problem}
Start with any complete tour, perform pairwise exchanges
\vspace*{0.3in}
\epsfxsize=0.7\textwidth
\fig{\file{figures}{tsp-sequence.ps}}
Variants of this approach get within 1\% of optimal very quickly with
thousands of cities
%%%%%%%%%%%% Slide %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\heading{Example: \mat{$n$}-queens}
Put \mat{$n$} queens on an \mat{$n \times n$} board with no two queens
on the same\\
row, column, or diagonal
Move a queen to reduce number of conflicts
\vspace*{0.3in}
\epsfxsize=1.0\textwidth
\fig{\file{figures}{4queens-iterative.ps}}
Almost always solves \mat{$n$}-queens problems almost instantaneously\\
for very large \mat{$n$}, e.g., \mat{$n\eq 1 million$}
%%%%%%%%%%%% Slide %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\heading{Hill-climbing (or gradient ascent/descent)}
``Like climbing Everest in thick fog with amnesia''
\input{\file{algorithms}{hill-climbing-algorithm}}
%%%%%%%%%%%% Slide %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\heading{Hill-climbing contd.}
Useful to consider \defn{state space landscape}
\vspace*{0.1in}
\epsfxsize=0.8\textwidth
\fig{\file{figures}{hill-climbing.ps}}
\vspace*{-0.1in}
\defn{Random-restart hill climbing} overcomes local maxima---trivially complete
\defn{Random sideways moves} \smiley escape from shoulders \frowny loop on flat maxima
%%%%%%%%%%%% Slide %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\heading{Simulated annealing}
Idea: escape local maxima by allowing some ``bad'' moves\\
\emph{but gradually decrease their size and frequency}
\input{\file{algorithms}{simulated-annealing-algorithm}}
%%%%%%%%%%%% Slide %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\heading{Properties of simulated annealing}
At fixed ``temperature'' $T$, state occupation probability reaches\\
Boltzman distribution
\mat{\[
p(x) = \alpha e^{\frac{E(x)}{kT}}
\]}
$T$ decreased slowly enough $\Longrightarrow$ always reach best state \mat{$x^*$}\\
because \mat{$e^{\frac{E(x^*)}{kT}} / e^{\frac{E(x)}{kT}}
= e^{\frac{E(x^*)-E(x)}{kT}} \gg 1$} for small \mat{$T$}
\q{Is this necessarily an interesting guarantee}
Devised by Metropolis et al., 1953, for physical process modelling
Widely used in VLSI layout, airline scheduling, etc.
%%%%%%%%%%%% Slide %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\heading{Local beam search}
\note{Idea}: keep $k$ states instead of 1; choose top $k$ of all their successors
Not the same as $k$ searches run in parallel!\\
Searches that find good states recruit other searches to join them
\note{Problem}: quite often, all $k$ states end up on same local hill
\note{Idea}: choose $k$ successors randomly, biased towards good ones
Observe the close analogy to natural selection!
%%%%%%%%%%%% Slide %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\heading{Genetic algorithms}
= stochastic local beam search + generate successors from \emph{pairs} of states
\vspace*{0.2in}
\epsfxsize=1.05\textwidth
\fig{\file{figures}{genetic.ps}}
%%%%%%%%%%%% Slide %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\heading{Genetic algorithms contd.}
GAs require states encoded as strings (\defn{GPs} use \note{programs})
Crossover helps \emph{iff substrings are meaningful components}
\vspace*{0.2in}
\epsfxsize=0.9\textwidth
\fig{\file{figures}{8queens-crossover.ps}}
GAs $\neq$ evolution: e.g., real genes encode replication machinery!
%%%%%%%%%%%% Slide %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\heading{Continuous state spaces}
Suppose we want to site three airports in Romania:\al
-- 6-D state space defined by \mat{$(x_1,y_2)$}, \mat{$(x_2,y_2)$}, \mat{$(x_3,y_3)$}\al
-- objective function \mat{$f(x_1,y_2,x_2,y_2,x_3,y_3)$} = \nl
sum of squared distances from each city to nearest airport
\defn{Discretization} methods turn continuous space into discrete space,\\
e.g., \defn{empirical gradient} considers \mat{$\pm \delta$} change in each coordinate
\defn{Gradient} methods compute
\mat{\[
\nabla f=\left(
\frac{\partial f}{\partial x_1},\frac{\partial f}{\partial y_1},
\frac{\partial f}{\partial x_2},\frac{\partial f}{\partial y_2},
\frac{\partial f}{\partial x_3},\frac{\partial f}{\partial y_3}
\right)
\]}
to increase/reduce \mat{$f$}, e.g., by
\mat{$\x \leftarrow \x + \alpha \nabla f(\x)$}
Sometimes can solve for \mat{$\nabla f(\x) = 0$} exactly (e.g., with one city).\\
\defn{Newton--Raphson} (1664, 1690) iterates
\mat{$\x \leftarrow \x - \H^{-1}_f(\x) \nabla f(\x)$}\\
to solve \mat{$\nabla f(\x) = 0$}, where \mat{$\H_{ij}\eq \partial^2 f/\partial x_i \partial x_j$}
\end{huge}
\end{document}