\section{Randomized Methods}
\frame{\center \huge Chapter \thesection \\ \vspace{5mm}\alert{\insertsection}}

\begin{frame}{Chapter Content}
	\begin{center}\vfill
		\tableofcontents[sections={\thesection}]
	\end{center}
\end{frame}

\subsection{Simulated Annealing}
\frame{\center \Large \thesection .\thesubsection \ \alert{\insertsubsection}}
%----------------------------------------------------
\begin{frame}[shrink]
	\frametitle{Annealing and Quenching Physical Processes}
	\begin{figure}[h]
		\begin{center}
			\includepdftex{annealing}
		\end{center}
	\end{figure}
\end{frame}

%-------------------
\begin{frame}
	\frametitle{Analogy with the metallurgical annealing process}
	\begin{itemize}[<+->]
		\item By rapidly cooling a molten metal, an amorphous structure is obtained
		\item By slowly cooling the metal, a crystalline structure is obtained
		\item The crystal structure is that which minimizes the internal energy of the
		      of the metal
		\item The amorphous structure corresponds to a local minimum of energy
		\item  The particles are in a stable state
		\item They do not have enough energy to change to another stable state with less energy
	\end{itemize}
	\begin{block}{Idea of Simulated Annealing}
		\begin{itemize}[<+->]
			\item Make the analogy between the internal energy of a metal and the fitness function of a problem to be minimized
			\item Particles move randomly
			\item Allow degrading moves with a certain probability
		\end{itemize}

	\end{block}
\end{frame}

%----------------------------------------------------
\begin{frame}
	\frametitle{Simulated Annealing Frame}
	\input{./algorithms/annealing}
\end{frame}

%----------------------------------------------------
\begin{frame}[shrink]
	\frametitle{Evolution of a TSP Tour Length and Temperature}
	\begin{figure}[h]
		\begin{center}
			\includepdftex{evolution_sa}
		\end{center}
	\end{figure}
\end{frame}

%----------------------------------------------------
%----------------------------------------------------
\subsection{Threshold Accepting}
%\frame{\center \Large \thesection .\thesubsection \ \textcolor{col_evidence}{\insertsubsection}}
%%----------------------------------------------------


%------------------
\begin{frame}
	\frametitle{\thesection .\thesubsection \ \insertsubsection}
	\begin{block}{Idea}
		\begin{itemize}[<+->]
			\item Observation: the computation of exponentials can take most of the computational effort of simulated annealing
			\item Draw a random move
			\item Accept this move if it degrades the solution by less than a certain threshold
			\item Start again, gradually lowering the threshold
			\item Threshold values:
			      \begin{itemize}
				      \item Start by making random moves
				      \item Estimate the distribution function of the differences in values $\Delta$ between neighbour solutions
			      \end{itemize}
		\end{itemize}
	\end{block}

\end{frame}

\begin{frame}
	\frametitle{\insertsubsection \ Frame}
	\input{./algorithms/threshold_accepting}
\end{frame}

%----------------------------------------------------
\begin{frame}
	\frametitle{Technique for determining thresholds $\tau_1, \dots \tau_T$}
	\begin{figure}[h]
		\begin{center}
			\includepdftex{init_gilli}
		\end{center}
	\end{figure}
\end{frame}

%----------------------------------------------------
%----------------------------------------------------
\subsection{Great Deluge}
%\frame{\center \Large \thesection .\thesubsection \ \textcolor{col_evidence}{\insertsubsection}}
%%----------------------------------------------------


%------------------
\begin{frame}
	\frametitle{\thesection .\thesubsection \ \insertsubsection}
	\begin{block}{Idea}
		\begin{itemize}[<+->]
			\item Draw a random move
			\item Accept this move if it leads to a solution better than a certain level
			\item Start again by gradually increasing the level (for a function to be maximized)
		\end{itemize}
	\end{block}
	\begin{center}
		\includepdftex{deluge}
	\end{center}
\end{frame}

\begin{frame}
	\frametitle{\insertsubsection \ Frame}
	\input{./algorithms/deluge}
	\begin{figure}[h]
	\end{figure}
\end{frame}



%----------------------------------------------------
%----------------------------------------------------
\subsection{Demon Algorithm}
%\frame{\center \Large \thesection .\thesubsection \ \textcolor{col_evidence}{\insertsubsection}}
%%----------------------------------------------------

%------------------
\begin{frame}
	\frametitle{\thesection .\thesubsection \ \insertsubsection}
	\begin{block}{Idea}
		\begin{itemize}[<+->]
			\item Simulate a player caught by the game demon
			\item The player enters the casino with a certain amount
			\item As long as he has credit, the player bets
			\item There has a gain if a random move improves the current solution (which becomes the new current solution)
			\item There is a loss if it degrades the current solution
			\item He cannot bet if the degradation is too great (the current solution is not modified)
			\item If the player's credit exceeds a certain threshold, he blows the amount that exceeds this threshold
		\end{itemize}
	\end{block}
	In terms of optimization process: navigate randomly through the solution space, but never visiting a solution worse than the best one found, increased by a certain threshold
\end{frame}

\begin{framefont}{\small}
	\begin{frame}
		\frametitle{\insertsubsection \ Frame}
		\input{./algorithms/demon}
	\end{frame}
\end{framefont}

%----------------------------------------------------
%----------------------------------------------------
\subsection{Noising Methods}
%\frame{\center \Large \thesection .\thesubsection \ \alert{\insertsubsection}}
%----------------------------------------------------
%---------------------------
\begin{frame}
	\frametitle{\Large \thesection .\thesubsection \ \insertsubsection}
	\alert{Conceptually, the above methods are very similar\\ 
		The noising methods group them into a more general frame}
	\begin{itemize}[<+->]
		\item Choose a sequence of distribution functions $Noise_k$ with (usually) standard deviations such that :
		      $\sigma(Noise_{k+1}) < \sigma(Noise_k)$
		\item At iteration $k$, add a random noise distributed according to the function $Noise_k$ :
		      \begin{itemize}
			      \item Either to the problem date
			      \item Or to the move evaluation
		      \end{itemize}
		\item Frame : Similar to an improvement method
		\item	The noise functions can be chosen dynamically during the iterations
		\item	Countless variants can be implemented depending on how the noise functions are chosen
		\item With appropriate choices one can implement simulated annealing, threshold accepting or a great deluge algorithms
	\end{itemize}
\end{frame}

\begin{frame}
	\frametitle{\insertsubsection \ Frame}
	\input{./algorithms/noising}
\end{frame}

%----------------------------------------------------
\begin{frame}
	\frametitle{Evolution of Noise Distribution as a Function of Iteration Number}
	\begin{figure}[h]
		\begin{center}
			\includepdftex{noise_distribution}
		\end{center}
	\end{figure}
\end{frame}


%----------------------------------------------------
%----------------------------------------------------
\subsection{Late Acceptance Hill Climbing}
%\frame{\center \Large \thesection .\thesubsection \  \textcolor{col_evidence}{\insertsubsection}}
%%----------------------------------------------------
\begin{framefont}{\small}
	\begin{frame}
		\frametitle{\thesection .\thesubsection \ \insertsubsection}
		\input{./algorithms/LAHC}
	\end{frame}
\end{framefont}

%----------------------------------------------------
%----------------------------------------------------
\subsection{Variable Neighbourhood Search}
%\frame{\center \Large \thesection .\thesubsection \ \textcolor{col_evidence}{\insertsubsection}}
%%----------------------------------------------------
%------------------
\begin{frame}
	\frametitle{\thesection .\thesubsection \ \insertsubsection (VNS)}
	\begin{block}{Idea}
		\begin{itemize}[<+->]
			\item Use several neighbourhoods
			\item Perform a random modification of the current solution with a neighbourhood
			\item Find the associated local optimum for a given neighbourhood
			\item If this optimum is better, it replaces the current solution
			\item Otherwise, start again using a different neighbourhood for the random jump
			\item In general, neighbourhoods are increasingly disrupting the current solution
		\end{itemize}
	\end{block}
\end{frame}

\begin{frame}
	\frametitle{\insertsubsection Frame}
	\input{./algorithms/VNS}
\end{frame}


%----------------------------------------------------
%----------------------------------------------------
\subsection{GRASP}
%\frame{\center \Large \thesection .\thesubsection \ \textcolor{col_evidence}{\insertsubsection}}

%------------------
\begin{frame}
	\frametitle{\thesection .\thesubsection \ \insertsubsection (Greedy Randomized Adaptive Search Procedure)}
	\begin{block}{Idea}
		\begin{itemize}[<+->]
			\item Build a solution in a greedy but non-deterministic way
			\item Randomly select the new element completing the partial solution from a fraction of those that cost the least
			\item Apply a local search on the constructed solution
			\item Repeat this $I_{max}$ times
		\end{itemize}
	\end{block}
\end{frame}

%%----------------------------------------------------
\begin{framefont}{\footnotesize}
	\begin{frame}
		\frametitle{\insertsubsection \ Frame}
		\input{./algorithms/GRASP}
	\end{frame}
\end{framefont}




