\jection{Metaheuristic Search}

\begin{frame}
\frametitle{What is Metaheuristic Search}
Metaheuristic search techniques are used in optimization 
problems that can't be solved using
analytic or complete methods.
\vspace{.15in}

They strive to find an acceptable {\it near-optimal}
solution, without any mathematical guarantee that
a better solution wouldn't be found if the
search is re-initialized.
\end{frame}

\begin{frame}
\frametitle{Metaheuristic Search}
Three of the most common metaheuristic search technique
\begin{itemize} 
\item simulated annealing \pause
\item evolutionary algorithms \pause
\item tabu search
\end{itemize}
\end{frame}

\subsection{Simulated Annealing}
\begin{frame}
\frametitle{Simulated annealing}
\begin{columns}[T]

\begin{column}{2in}
\includegraphics[width=2.0in]{../Greenwald06/Figures/annealling}
\end{column}

\begin{column}{2in}
Hill climber that tries to not get stuck in local optima.
\vspace{.1in}

Probability of making a bad move $\propto e^{-(\triangledown E/T)}$
and ``cooling'' schedule controls the value of the temperature.
\end{column}

\end{columns}
\end{frame}

\subsection{Evolutionary Algorithms}
\begin{frame}
\frametitle{Evolutionary Algorithms}
genetic algorithms (GA) and genetic programming (GP) \\
\vspace{.18in}
\begin{columns}[T]

\begin{column}{2in}
GA crossover event \\
\vspace{.16in}
\includegraphics[width=1.8in]{../Greenwald06/Figures/crossover}
\end{column}

\begin{column}{2in}
GP crossover event \\
\vspace{.16in}
\includegraphics[width=1.8in]{../Greenwald06/Figures/AST-crossover}
\end{column}
\end{columns}

\end{frame}
