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

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

\subsection{Taboo Search}
%\frame{\center \Large \thesection .\thesubsection \ \textcolor{col_evidence}{\insertsubsection}}

%------------------------------
\begin{frame}
	\frametitle{\thesection .\thesubsection \ \insertsubsection}
	\begin{block}{Basic Ideas}
		\begin{itemize}[<+->]
			\item Local search with best move policy
			\item Allow degradation of the solution from one iteration to the next
			\item Using a memory to avoid cycling
		\end{itemize}
	\end{block}
\end{frame}

\begin{frame}
	\frametitle{Learning Process}
	\begin{itemize}[<+->]
		\item Memory
		      \begin{itemize}
			      \item Visited solutions
			      \item Moves performed
		      \end{itemize}

		\item Memory use
		      \begin{itemize}
			      \item Prohibit returning to a previously visited solution (the solution is \definition{taboo})
			      \item Prohibit performing the reverse of a move
			      \item Penalize frequently used moves
			      \item Force the use of never used moves
		      \end{itemize}

		\item Oblivion
		      \begin{itemize}
			      \item Remove a prohibition after a certain number of iterations
		      \end{itemize}

	\end{itemize}
\end{frame}


%%----------------------------------------------------
\begin{framefont}{\footnotesize}
	\begin{frame}
		\frametitle{Elementary Taboo Search Frame}
		\input{./algorithms/taboo_search}
	\end{frame}
\end{framefont}

%%----------------------------------------------------
%%---------------------------
\begin{framefont}{\footnotesize}
	\begin{frame}{Elementary Taboo Search for the Knapsack Problem}
		\begin{equation*}
			\begin{array}{rlrr}
				\max        r = & 12s_1+10s_2+9s_3+7s_4+4s_5+8s_6+11s_7+6s_8+13s_9 &           &    \\
				\mbox{S.t.}     & 10s_1+12s_2+8s_3+7s_4+5s_5+13s_6+9s_7+6s_8+14s_9 & \leqslant & 45 \\
				                & s_i  \in  \{ 0, 1\}\quad (i = 1, \dots, 9)       &           &    \\
			\end{array}
		\end{equation*}

		\rowcolors{1}{RoyalBlue!20}{mymauve!5}
		\begin{tabular}{m{0.08\textwidth}| m{0.08\textwidth}| m{0.25\textwidth}|m{0.05\textwidth}| m{0.05\textwidth}| m{0.3\textwidth}}
			\toprule
			Iter. & Var. Modif. & Solution                    & $r$ & $v$ & Taboo status (duration $d = 3$) \\
			\midrule
			0     & ---         & (0, 0, 0, 0, 0, 0, 0, 0, 0) & 0   & 0   & (0, 0, 0, 0, 0, 0, 0, 0, 0)     \\
			1     & $s_9$       & (0, 0, 0, 0, 0, 0, 0, 0, 1) & 13  & 14  & (0, 0, 0, 0, 0, 0, 0, 0, 4)     \\
			2     & $s_1$       & (1, 0, 0, 0, 0, 0, 0, 0, 1) & 25  & 24  & (5, 0, 0, 0, 0, 0, 0, 0, 4)     \\
			3     & $s_7$       & (1, 0, 0, 0, 0, 0, 1, 0, 1) & 36  & 33  & (5, 0, 0, 0, 0, 0, 6, 0, 4)     \\
			4     & $s_2$       & (1, 1, 0, 0, 0, 0, 1, 0, 1) & 46  & 45  & (5, 7, 0, 0, 0, 0, 6, 0, 4)     \\
			5     & $s_9$       & (1, 1, 0, 0, 0, 0, 1, 0, 0) & 33  & 31  & (5, 7, 0, 0, 0, 0, 6, 0, 8)     \\
			6     & $s_3$       & (1, 1, 1, 0, 0, 0, 1, 0, 0) & 42  & 39  & (5, 7, 9, 0, 0, 0, 6, 0, 8)     \\
			7     & $s_8$       & (1, 1, 1, 0, 0, 0, 1, 1, 0) & 48  & 45  & (5, 7, 9, 0, 0, 0, 6, 10, 8)    \\
			8     & $s_2$       & (1, 0, 1, 0, 0, 0, 1, 1, 0) & 38  & 33  & (5, 11, 9, 0, 0, 0, 6, 10, 8)   \\
			9     & $s_4$       & (1, 0, 1, 1, 0, 0, 1, 1, 0) & 45  & 40  & (5, 11, 9, 12, 0, 0, 6, 10, 8)  \\
			10    & $s_5$       & (1, 0, 1, 1, 1, 0, 1, 1, 0) & 49  & 45  & (5, 11, 9, 12, 13, 0, 6, 10, 8) \\
			\bottomrule
		\end{tabular}
	\end{frame}
\end{framefont}

\subsubsection{Taboo Duration}
%----------------------------------------------------
\begin{frame}[shrink]
	\frametitle{Influence of Taboo Duration}
	\begin{figure}[h]
		\begin{center}
			\includepdftex{list_size_influence}
		\end{center}
	\end{figure}
\end{frame}

%----------------------------------------------------
\begin{frame}[shrink]
	\frametitle{Random Taboo Duration for the QAP}

	Number of iterations to reach the optimum (disc diameter) or number of times the optimum is found (diameter of empty circles)
	\begin{figure}[h]
		\begin{center}
			\includepdftex{random_list_QAP}
		\end{center}
	\end{figure}
\end{frame}

%----------------------------------------------------
\begin{frame}
	\frametitle{Taboo Duration Choice}
	\begin{columns}
		\begin{column}{0.5 \textwidth}
			\begin{itemize}[<+->]
				\item Taboo duration too short: cycling
				\item Taboo duration too long: good solutions are not allowed to be visited
				\item Remedy: Randomly draw taboo duration between $d_{min}$ and $d_{min} + \Delta$
				\item Example for a TSP with $n=52$ cities performing $10n$ iterations
			\end{itemize}
		\end{column}
		\begin{column}{0.5 \textwidth}
			\begin{figure}[h]
				\begin{center}
					\includepdftex{bier127_ts10n}
				\end{center}
			\end{figure}
		\end{column}
	\end{columns}
\end{frame}


%----------------------------------------------------
%----------------------------------------------------
\subsection{Strategic Oscillations}
\frame{\center \Large \thesection .\thesubsection \ \alert{\insertsubsection}}


%----------------------------------------------------
\begin{frame}{\insertsubsection}

	\begin{block}{Alternate phases of intensification and diversification}
		\begin{itemize}[<+->]
			\item \textbf{Intensification:} Forbidding a move or solution for $d$ iterations implements a \alert{short term} memory
			      \begin{itemize}
				      \item Lower the value of $d$
				      \item Start again from best solution found
			      \end{itemize}
			\item \textbf{Diversification:} Try to go elsewhere
			      \begin{itemize}
				      \item By penalizing frequently performed moves
				      \item By forcing to do a very rarely performed move, regardless of its evaluation
				      \item Starting with a new solution
			      \end{itemize}
		\end{itemize}
	\end{block}
	\begin{itemize}
		\item Reactive Taboo Search (RTS)
		      \begin{itemize}[<+->]
			      \item Increase taboo duration if visiting a solution already encountered
			      \item Diminish taboo duration if no solution is revisited for many iterations
		      \end{itemize}
	\end{itemize}
\end{frame}


\subsubsection{Long Term Memory}

%----------------------------------------------------
\begin{frame}
	\frametitle{Pathological Situation for the TSP}
	Penalizing frequently performed moves allows escape from plateaus
	\begin{figure}[h]
		\begin{center}
			\includepdftex{penalty_move}
		\end{center}
	\end{figure}
	For this TSP tour: many 2-opt moves with 0 cost
\end{frame}

%----------------------------------------------------
\begin{frame}
	\frametitle{Move Penalty for the TSP}
	Penalizing moves according to the frequency of their use can even eliminate the need for a taboo list!
	\begin{figure}[h]
		\begin{center}
			\includepdftex{bier127_ts10n_pena}
		\end{center}
	\end{figure}
\end{frame}


