\section{Construction Learning}
\frame{\center \huge Chapter \thesection \\ \vspace{5mm}\alert{\insertsection}}

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

%-------------------------
\begin{frame}
	\frametitle{Learning: Avoid relying solely on chance}
	\begin{block}{Adding knowledge }
		\begin{itemize}[<+->]
			\item Repeat experiments and analyze successes (or failures, as one learns more by making mistakes!)
			\item Remember what has been done
			\item Forgetting certain details, which gives the ability to generalize when in a similar but different situation
		\end{itemize}
	\end{block}
\end{frame}

\subsection{Artificial Ants\label{sec:fourmis}}
\frame{\center \Large \thesection .\thesubsection \ \alert{\insertsubsection}}

\subsubsection{Behaviour of real ants}
%------------------
\begin{frame}
	\frametitle{Observations with real ants}
	\begin{columns}
		\begin{column}{0.4 \textwidth}
			\begin{itemize}[<+->]
				\item The colony is separated from a food source by a path that forks
				\item Initially the ants are equally distributed in the two branches
				\item Those that took the shortest route deposit pheromones more quickly on the way back
				\item After a while, all ants use the shortest path
			\end{itemize}
		\end{column}
		\begin{column}{0.6 \textwidth}
			\begin{figure}
				\begin{center}
					\def\svgwidth{0.85\textwidth}
					\includepdftex{ant_start_end}
				\end{center}
			\end{figure}
		\end{column}
	\end{columns}
\end{frame}

\subsubsection{Transcription into an optimization process}
%------------------
\begin{framefont}{\footnotesize}
	\begin{frame}
		\frametitle{\insertsubsubsection}

		\begin{itemize}[<+->]
			\item An ant = a process executing a solution building procedure with a random component
			\item Several processes can run in parallel
			\item Pheromone traces are $\tau_e$ values associated with each element $e$ that can constitute a solution
			\item Traces are a collective memory
			\item After the construction of a solution, the values of its elements are increased in proportion to its quality
			\item The phenomenon of forgetting is simulated by the evaporation of traces over time
		\end{itemize}
		\begin{block}{Idea: Adding learning to a GRASP process}
			\begin{itemize}[<+->]
				\item Consider the value $\tau_e$ in addition to the incremental cost function $c(s, e)$
				\item Choose the next element $e$ to be included with probability proportional to $\tau_e ^\alpha \cdot c(s,e)^\beta$, where $\alpha > 0$ and $\beta < 0$ are two parameters
				\item At each iteration, $\tau_e$ is multiplied by $1 - \rho$ ($0 \leqslant \rho \leqslant 1$) and is reinforced by a quantity $1/f(s)$
			\end{itemize}
		\end{block}
	\end{frame}
\end{framefont}

%------------------
\begin{frame}
	\frametitle{Various Ant Systems}

	\begin{description}[<+->]
		\item[Ant System (AS)]Difficult to parameterize $\alpha$, $\beta$, $\rho$ to avoid a too fast convergence or no convergence
		\item [Ant Colony Optimization (ACO)]Add a local search (\emph{demon action})
		\item [Max-Min Ant system]Keeping the value of the traces between $\tau_{min}$ and $\tau_{max}$ facilitates the adjustment of the parameters and makes the process more robust
		\item [Fast Ant (FANT)]Limit the number of parameters\\
			Self-learning of trace reinforcement level
	\end{description}
\end{frame}

\subsubsection{Max-Min Ant system}
%%----------------------------------------------------
\begin{framefont}{\tiny}
	\begin{frame}[shrink]
		\frametitle{\insertsubsubsection \ Frame}
		\input{./algorithms/maxmin_ant}
	\end{frame}
\end{framefont}


\subsubsection{Fast Ant System (FANT)}
%%----------------------------------------------------
\begin{framefont}{\tiny}
	\begin{frame}[shrink]
		\frametitle{FANT Frame}
		\input{./algorithms/FANT}
	\end{frame}
\end{framefont}
%----------------------------------------------------
\begin{frame}[shrink]
	\frametitle{Behaviour of FANT for a TSP Instance with 225 Cities}
	\begin{figure}[h]
		\begin{center}
			\includepdftex{tsp225fant}
		\end{center}
	\end{figure}
\end{frame}


%----------------------------------------------------
%----------------------------------------------------
%------------------------------------------------------------
\subsection{Vocabulary Building}
\frame{\center \Large \thesection .\thesubsection \ \alert{\insertsubsection}}

%------------------
\begin{frame}
	\frametitle{\thesection .\thesubsection \ \insertsubsection}
	\begin{block}{Idea: memorize parts (\textbf{words}) of solutions (\textbf{sentences})}
		\begin{itemize}[<+->]
			\item Build new solutions from these parts
			\item A \definition{dictionary} of parts is developed
			\item A randomized attempt of  sentence is constructed from the words in the dictionary
		\end{itemize}
	\end{block}
\end{frame}
%----------------------------------------------------
\begin{frame}
	\frametitle{Vocabulary Building for the VRP}
	\begin{figure}[h]
		\begin{center}
			\includepdftex{vrp199vocabulary_building}
		\end{center}
	\end{figure}
	(a) The optimal solution to a VRP instance\\
	(b) A few tours quickly obtained with a taboo search
\end{frame}

%-----------------
\begin{frame}
	\frametitle{Solution Fragments (tours) Constituting the Dictionary}
	\begin{columns}
		\begin{column}{0.5 \textwidth}
			\begin{itemize}[<+->]
				\item A tour is selected from the dictionary
				\item Tours with customers from the last selected tour are set aside
				\item Repeat as long as possible
			\end{itemize}
		\end{column}
		\begin{column}{0.5 \textwidth}
			\begin{figure}
				\begin{center}
					\def\svgwidth{0.8\textwidth}
					\includepdftex{dictionary}
				\end{center}

				\label{fig:dictionnaire}
			\end{figure}
		\end{column}
	\end{columns}
\end{frame}


%----------------------------------------------------
\begin{frame}
	\frametitle{Sentence Attempt, Completion and Improvement }
	\begin{figure}[h]
		\begin{center}
			\includepdftex{tentative_correction_voc_building}
		\end{center}
	\end{figure}
\end{frame}

%----------------------------------------------------
\begin{frame}
	\frametitle{Fragments of solutions (chains) for a TSP}
	Edges appearing in more than $2/3$ of 100 local optima (dark blue: not in global optimum)
	\begin{figure}[h]
		\begin{center}
			\def\svgwidth{0.5\textwidth}
			\includepdftex{pr2392_common_67opt}
		\end{center}
	\end{figure}
\end{frame}






