\begin{slide}
\section{Local Search} 
\Large
\begin{center}
\begin{picture}(500,400)
\psfig{figure=LS-graph.eps,width=500pt,height=400pt,angle=-90}
\end{picture}
\end{center}

\end{slide}


\begin{slide}
\Huge
\subsection{Main idea of Local Search}

\begin{itemize}

\item Never actually try to write the whole graph,

\item Just move from one possible solution to a ``nearby'' possible
solution,

\item Stop when ``optimal'' solution is found or time runs out.

\end{itemize}

\end{slide}

\begin{slide}
\huge
\subsection{Local Search Algorithm}

To set up an algorithm we need to have:
\begin{enumerate}

\item Set of possible solutions $\Longrightarrow$ vertices in the graph

\item {\bf neighbors} of each vertex: 
\begin{itemize}
 \item For $x$, $N(x)$ is set of adjacent vertices.
 
 \item $N(x)$ is easy to compute from $x$.
 
 \item if $y \in N(x)$ then $x \in N(y)$ $\Longrightarrow$ represent
   neighbors as undirected edges.

 \item $N(x)$ need to be polynomially bounded in the input size so
   neighbors of a node are easy to search through.
 \end{itemize}

\item Cost function: $f$: ${\cal S} \longrightarrow {\cal R}$ ,
  where ${\cal S}$ is the set of feasible solutions.
\end{enumerate} 
\end{slide}

\begin{slide}
\huge
\subsection{Most basic LS algorithm}

Say, to minize a cost function:

\begin{itemize}

\item Pick a starting point $x$.

\item While there is a neighbor $y$ of $x$ with $f(y) < f(x)$, move to
  it; that is, set $x$ to $y$ and continue.

\item Return the final solution.

\end{itemize}
\end{slide}

\begin{slide}
\huge
\subsection{Reasoning Behind Local Search}

Getting better and better solutions, we should end up with a good
one.

Pictorially, a nice state space that we would like to have:

\begin{center}
\begin{picture}(345,260)
\psfig{figure=state-space.eps,width=345pt,height=260pt,angle=-90}
\end{picture}
\end{center}
\end{slide}

\begin{slide}
\subsection{Problems with the rationale ...}
\Large
\begin{itemize}
\item Solution space might not looked as the above above ...

\item Example, cost function might not change smoothly when moving
from a state to its neighbor ...

\item There might be several {\bf local optima}, in which case the 
algorithm hone in one and get stuck there ... As shown below:

\begin{center}
\begin{picture}(300,230)
\psfig{figure=local-optima.eps,width=300pt,height=230pt,angle=-90}
\end{picture}
\end{center}
\end{itemize}
\end{slide}

\begin{slide}
\huge
\subsection{The Key Points ...}
\begin{itemize}
\item The way the problem is set up is quite important...
\item When choosing possible moves between solutions -- that is, when
  constructing the mapping that gives us the neighborhood of each node
  --- we are setting up:
\begin{enumerate}
\item how local search behave,
\item how cost function will change between neighbors,
\item how many local optima there are.
\end{enumerate}
\item Setting up the right neighborhood, so that solution space
looks the way we like ... is essential.
\end{itemize}
\end{slide}

\begin{slide}
\huge
\subsection{Local Search variations}

Assuming the goal is to minimize the cost function ...
\begin{itemize}
\item {\bf Hill-climbing}: one moves to a vertex of lower (or possibly
  equal) cost.
\item {\bf Metropolis rule}: pick a random neighbor...
\begin{itemize}
\item if cost is lower, move there.
\item if cost is higher, move there with some probability (depending
  on the cost differential).
\end{itemize}
The idea is that possibly moving to a worse state helps avoid getting
trapped at local minima.
\end{itemize}
\end{slide}

\begin{slide}
\huge
\subsection{Local Search variations -- continue}

\begin{itemize}
\item {\bf Simulated annealing}: Similar to Metropolis rule, except
  the probability of going to a higher cost neighbor varies with
  time. Same as a physical system being cooled down over time.
\item {\bf Parallel search}: (``go with the winners'') do multiple
  searches in parallel, occasionally killing off searches that appear
  less successful and replacing them with copies of searches that
  appear to be doing better.
\item {\bf Genetic algorithms}: Quite related to local search. An
  important difference is that instead of keeping one solution at a
  time, a group of them (called a population) is kept, and the
  population changes at each step.
\end{itemize}
\end{slide}

\begin{slide}
\huge
\section{Simulated Annealing -- Annealing Schedules}
\end{slide}

\begin{slide}
\huge
\subsection{geometric cooling}

\begin{itemize}

\item New temperature ($T^{'}$) is computed using:
$T^{'} = \alpha T$

where $\alpha$ ($0 < \alpha < 1$) denotes the cooling factor. 

\item Disadvantages:
\begin{itemize}
\item the scheme does not take account of the state of
  the system in the process of searching the solution space...
\item difficult to adaptively modify the intensity of the search
  depending on the difficulty of the problem...
\item at high $T$ almost all proposed interchanges are (mostly)
  accepted, even though many of them could be non-productive.
\end{itemize}
\end{itemize}

\begin{slide}
\Large
\subsection{reheating as a function of cost}

Key points about the scheme ...

\begin{itemize}
\item Compute {\bf specific heat} ($C_H$): a
measure of the variance of the cost values 
of states at a given temperature... This is needed to compute
$T$ occurring at a phase transition.

\item A phase transition occurs at a temperature $T(C_H^{max})$ when
the specific heat is maximal ($C_H^{max}$) $\Longrightarrow$ change in
the state ordering.

\item If current solution has a high cost $\Longrightarrow$
the super-structure may require re-arrangement. How?
\begin{itemize}
 \item done by raising the temperature to a level which is higher than
   the phase transition temperature $T(C_H^{max})$. 
\end{itemize}

\item In general:  the higher the current best cost, the higher the 
temperature which is required to escape the local minimum.
\end{itemize}
\end{slide}
\Large
\subsection{reheating as a function of cost -- continue}

At each $T$, the algorithm generates a set of configs ${\cal
  C}(T)$. Let $C_i$ denotes cost of config $i$, $C(T)$ is avg
cost, and $\sigma(T)$ is STD of cost at $T$.

\begin{itemize}
\item At $T$, the prob. dist. for configurations is: 
$\;\;\;\;\;P_i(T) = {e^{-C_i \over {kT}} \over \sum_j{e^{-C_j \over {kT}}}}$

\item The average cost is computed as: 
$\;\;\;\;\;<C(T)> = \sum_{i \in {\cal C}} C_i P_i(T)$

\item The average square cost is: 
$\;\;\;\;\;<C^{2}(T)> = \sum_{i \in {\cal C}} C_i^2 P_i(T)$

\item Variance of the cost is:
$\;\;\;\;\;\sigma^{2}(T) = <C^{2}(T)> - <C(T)>^{2}$

\item Now, the specific heat is defined as: 
$\;\;\;\;\;C_H(T) = {{\sigma^{2}(T)} \over {T^{2}}}$
\end{itemize}

$T(C_H^{max})$ at which the maximum specific heat occurs, or at which
the sys undergoes a phase transition, can thus be found.

Reheating sets the new $T$ to be:
$\;\;\;\;\;T = K \cdot C_b + T(C_H^{max})$

where $K$ is a parameter and $C_b$ is the current best cost. 
\end{slide}

\begin{slide}
\Large
\subsection{Adaptive Cooling}

A new $T$ is computed based on the specific heat, i.e.
the STD of all costs obtained at the current $T$.

{\bf main idea}: to keep the system close to equilibrium, by cooling
slower close to the phase transition, where the specific heat is
large.

Let $T_j$ denote the current temp, at step $j$ of the schedule.
Compute $\sigma(T_j)$ from equation then new $T_{j+1}$ is computed as
follows:  

$\;\;\;\;\;\;\;\;\;\;T_{j+1} = T_j \cdot e^{-{{a T_j} \over \bar\sigma(T_j)}}$

where $a$ is a tunable parameter.

$\sigma(T_j)$ is smoothed out in order to avoid any
dependencies of the temperature decrement on large changes in the STD. 
The smoothed STD $\bar\sigma$:

$\;\;\;\;\;\;\;\;\;\;\bar\sigma(T_{j+1}) = (1 - \omega) \sigma(T_{j+1}) + \omega
\sigma(T_j) {T_{j+1} \over T_j}$

and set $\omega$ to $0.95$
\end{slide}

\begin{slide}
\begin{table}
\begin{center}
\vspace{2pt}
\begin{tabular}{|l|l||c|c|c||}
\hline
Academic        &   Algorithm     & Scheduled & Highest   & Lowest    \\
Time Period     &                 & (average) & Scheduled & Scheduled \\
                         &                 &    \%     &    \%     &
                         \%     \\ [2pt] \hline\hline
First Semester  & SA (geometric)  &   93.90   &   95.12  &  85.20 \\
                & SA (adaptive)   &   98.80   &   99.20  &  95.00 \\
                & SA (cost-based) &   100.0   &   100.0  &  100.0 \\ [2pt]\hline 
Second Semester & SA (geometric)  &   95.00   &   98.95  &  89.40 \\
                & SA (adaptive)   &   99.00   &   99.50  &  98.50 \\    
                & SA (cost-based) &   100.0   &   100.0  &  100.0 \\ [2pt]\hline
Third Semester  & SA (geometric)  &   97.60   &   98.88  &  90.90 \\
                & SA (adaptive)   &   100.0   &   100.0  &  100.0 \\
                & SA (cost-based) &   100.0   &   100.0  &  100.0 \\ [2pt] \hline
\end{tabular}
\end{center}
\end{table}
\end{slide}
