\section{Population Management}
\frame{\center \huge Chapter \thesection \\ \vspace{5mm}\alert{\insertsection}}

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

%----------------------------------------------------
\begin{frame}
	\frametitle{Learning with a population of solutions}
	\begin{figure}[h]
		\begin{center}
			\includepdftex{tsp_tour_merge}
		\end{center}
	\end{figure}
\end{frame}

%----------------------------------------------------
\begin{frame}
	\frametitle{Idea of Evolutionary Algorithms}
	\begin{itemize}[<+->]
		\item It is easy to generate many different solutions for a problem
		\item Build new solutions by combining previously obtained solutions
		\item Scatter the generated solutions throughout the solution set
		\item The combination of solutions can select the right features from each
	\end{itemize}
	\begin{figure}[h]
		\begin{center}
			\includepdftex{beetle_mate}
		\end{center}
	\end{figure}
\end{frame}


%----------------------------------------------------
%----------------------------------------------------
\subsection{Evolutionary Algorithms Framework}
\frame{\center \Large \thesection .\thesubsection \ \alert{\insertsubsection}}


%----------------------------------------------------
\begin{frame}
	\frametitle{Generational loop in an evolutionary algorithm}
	\begin{figure}[h]
		\begin{center}
			\includepdftex{generational_loop}
		\end{center}
	\end{figure}
\end{frame}

%----------------------------------------------------
\begin{frame}
	\frametitle{Evolutionary Algorithms Frame}
	\input{./algorithms/evolutionnary}
\end{frame}

\begin{frame}
	\frametitle{Evolutionary Algorithms Options}
	\begin{itemize}[<+->]
		\item Selection operators for reproduction and survival
		\item Solution combination operator
		\item Mutation operator
		\item Population Management
		\item Stopping criterion
	\end{itemize}
\end{frame}


%----------------------------------------------------
%----------------------------------------------------
\subsection{Genetic Algorithms}
\frame{\center \Large \thesection .\thesubsection \ \alert{\insertsubsection}}

\subsubsection{Selection Operators for Reproduction}
%----------------------------------------------------
\begin{frame}
	\frametitle{\insertsubsubsection}
	\begin{description}[<+->]
		\item[Selection by rank]Assigning a quality measure $f_i = (1 - \frac{r_i}{\mu})^p$, where $r_i$ is the rank of the  $i$th individual (the best individual has a rank of 1 and the worst of $\mu$) and $p \geqslant 0$ is a parameter to modulate the   \definition{selection pressure} ($p=0$ : uniform  (no selection pressure), $p=2$ is a relatively high pressure)
		\item[Proportional selection]Individual $i$ of quality $f_i$ has a probability $f_i/{\sum{f_i}}$ of being selected (\definition{roulette wheel})
		\item[Natural selection]Each individual has the same probability of being selected
		\item[Complete selection]All individuals are selected for reproduction
	\end{description}
\end{frame}
\begin{frame}
	\frametitle{Selection probability for different operators for reproduction}
	\rowcolors{1}{RoyalBlue!20}{mymauve!5}
	\begin{table}
		\begin{center}
			\begin{tabular}{r|r|cccc}
				Fitness-function & Rank & Rank-b. ($p = 2$) & Rank-b. ($p = 1$) & Natural & Proportional \\
				\hline
				\hline
				220              & 1    & 0.260          & 0.182          & 0.1     & 0.220        \\
				162              & 2    & 0.210          & 0.164          & 0.1     & 0.162        \\
				157              & 3    & 0.166          & 0.146          & 0.1     & 0.157        \\
				93               & 4    & 0.127          & 0.127          & 0.1     & 0.093        \\
				85               & 5    & 0.094          & 0.109          & 0.1     & 0.085        \\
				74               & 6    & 0.065          & 0.091          & 0.1     & 0.074        \\
				61               & 7    & 0.042          & 0.073          & 0.1     & 0.061        \\
				55               & 8    & 0.023          & 0.054          & 0.1     & 0.055        \\
				49               & 9    & 0.010          & 0.036          & 0.1     & 0.049        \\
				44               & 10   & 0.003          & 0.018          & 0.1     & 0.044        \\
			\end{tabular}
		\end{center}
	\end{table}
\end{frame}

%----------------------------------------------------
\begin{frame}
	\frametitle{Uniform Crossover: Production of 2 children from 2 parents}
	\begin{itemize}[<+->]
		\item Going through the genes one by one
		\item Each element of the first child is drawn randomly from the first or second parent
		\item The other child receives the complementary elements
	\end{itemize}
	\begin{figure}[h]
		\begin{center}
			\includepdftex{uniform_crossover}
		\end{center}
	\end{figure}
\end{frame}

%----------------------------------------------------
\begin{frame}
	\frametitle{Uniform Crossover for Permutation}
	Proceed in two steps, leaving empty the cells for which no choice is possible\\
	Randomly fill in the blanks with the missing elements\\
	\begin{figure}[h]
		\begin{center}
			\includepdftex{uniform_crossover_permutation}
		\end{center}
	\end{figure}
\end{frame}

%----------------------------------------------------
\begin{framefont}{\footnotesize}
	\begin{frame}
		\frametitle{Single-Point Crossover: Production of 2 children from 2 parents}
			Randomly picks a point within the solution vector
	     \begin{itemize}[<+->]
		      \item Copy the items from the first parent up to the point, and those of the second from there for the first child
		      \item Copy the items from the second parent up to the point, and those of the first from there for the second child
	     \end{itemize}
		\begin{figure}[h]
			\begin{center}
				\includepdftex{single_point_crossover}
			\end{center}
		\end{figure}
	\end{frame}

	%----------------------------------------------------
	\begin{frame}
		\frametitle{2-Points Crossover : Production of 2 children from 2 parents}
		Randomly picks 2 different points within the solution vector
	     \begin{itemize}[<+->]
		      \item For the first child: Copy the elements from the first parent up to the first point and from the second point up to the end, copy the intermediate part from the second parent
		      \item For the second child: Copy the elements from the second parent up to the first point and from the second point up to the end, copy the intermediate part from the first parent
	     \end{itemize}
		\begin{figure}[h]
			\begin{center}
				\includepdftex{2points_crossover}
			\end{center}
		\end{figure}
	\end{frame}

	%----------------------------------------------------
	\begin{frame}
		\frametitle{OX Crossover for the TSP : Respect the sequence of successors}
		\begin{itemize}[<+->]
			\item Choose 2 crossover points
			\item The intermediate portion is copied from the first parent
			\item Locate the last item copied into the child in the second parent
			\item Complete the child in the order in which the elements appear in the second parent (skip elements already introduced; cyclic path)
		\end{itemize}
		\begin{figure}[h]
			\begin{center}
				\includepdftex{OX_crossover}
			\end{center}
		\end{figure}
	\end{frame}
\end{framefont}

\subsubsection{Mutation Operators}
%----------------------------------------------------
\begin{frame}[shrink]
	\frametitle{\insertsubsubsection : Randomly disturb the children}
	\begin{itemize}[<+->]
		\item Bringing diversity (new blood) into the population
		\item Avoid to clone individuals
	\end{itemize}
	%	Influence of the mutation rate on the quality of the solutions produced according to the number of generational loops performed\\
	%	Only the value of the best solution in the population is represented\\
	\begin{figure}[h]
		\begin{center}
			\includepdftex{infl_mutation_gen}
		\end{center}
	\end{figure}
\end{frame}

\subsubsection{Selection operator for survival}
%----------------------------------------------------
\begin{frame}
	\frametitle{\insertsubsubsection}
			\begin{description}[<+->]
				\item[Generational replacement] $\lambda = \mu$, children replace parents
				\item[Evolutionary strategy] $\lambda > \mu$, the best children replace the parents
				\item[Stationary replacement] $\lambda = 2$, children replace parents
				\item[Elitist replacement] The $\mu$ best elements among $\mu + \lambda$ survive
			\end{description}
\end{frame}

%----------------------------------------------------
\begin{frame}[shrink]
	\frametitle{Influence of population size, elitist replacement}
			\begin{center}
				\begin{figure}[h]
					\includepdftex{infl_pop_gen}
				\end{figure}				
			\end{center}
\end{frame}

\subsection{Memetic Algorithms}
%\frame{\center \Large \thesection .\thesubsection \ \textcolor{col_evidence}{\insertsubsection}}

\begin{frame}{\thesection .\thesubsection \ \insertsubsection}
	\begin{block}{Idea: Learn better by managing the population intelligently, improve solutions faster by combining a genetic algorithm with other ingredients of meta-heuristics}
		\begin{itemize}[<+->]
			\item Consider several small populations (islands)
			      \begin{itemize}
				      \item Accelerated convergence of each population
			      \end{itemize}
			\item Define a diversity measure between solutions
			      \begin{itemize}
				      \item Reject the solutions that are too similar to others in the population
				      \item Survival of the best solution of a population
			      \end{itemize}
			\item Create a communication network between islands (ring, grid, \dots)
			      \begin{itemize}
				      \item Send solutions from one population to another to diversify them
			      \end{itemize}
			\item Replace the mutation operator with a local search
		\end{itemize}
	\end{block}
\end{frame}

\subsection{Scatter Search \label{sec:dispersion}}
%\frame{\center \Large \thesection .\thesubsection \ \textcolor{col_evidence}{\insertsubsection}}

%----------------------------------------------------
\begin{frame}[shrink]
	\frametitle{\thesection .\thesubsection \ \insertsubsection}
	\begin{block}{Break the taboo of a reproduction limited to the crossover of two solutions}
		\begin{itemize}[<+->]
			\item Initial population: as scattered as possible
			\item Combine several solutions with each other
			\item Repair/improvement operator
			\item Population management in elite and diverse solutions
		\end{itemize}
	\end{block}
	\begin{figure}[h]
		\begin{center}
			\includegraphics[width=0.5\textwidth]{../figures/DSD_4593p.jpg}
		\end{center}
	\end{figure}
\end{frame}

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

\subsubsection{Example of Scatter Search for the Knapsack}
%----------------------------------------------------
\begin{frame}[shrink]
	\frametitle{\insertsubsubsection}
	\begin{equation} \label{scatter_knapsack}
		\begin{array}{rlrr}
			\max        r = & 11s_1+10s_2+\phantom{1}9s_3+12s_4+10s_5+\phantom{1}6s_6+\phantom{1}7s_7+\phantom{1}5s_8+\phantom{1}3s_9+\phantom{1}8s_{10} &           &     \\
			\mbox{Subject}  & 33s_1+27s_2+16s_3+14s_4+29s_5+30s_6+31s_7+33s_8+14s_9+18s_{10}                                                             & \leqslant & 100 \\
			\mbox{to:}      & s_i  \in  \{ 0, 1\} (i = 1, \dots, 10)                                                                                     &           &     \\
		\end{array}
	\end{equation}
	\rowcolors{1}{RoyalBlue!20}{mymauve!5}
	\begin{table}
		\begin{center}
			\begin{tabular}{r|cc|ccc}
				   & Potential solution                     & Value & Repaired/improved solution            & Value &              \\
				%   & Solution                      &       & Solution                      &       &              \\
				\hline
				1  & \alert{(1,1,1,1,1,1,1,1,1,1)} & 81    & \alert{(0,1,1,1,0,0,0,0,1,1)} & 42    &              \\
				2  & \alert{(1,0,1,0,1,0,1,0,1,0)} & 40    & \alert{(1,0,1,1,1,0,0,0,0,0)} & 42    &              \\
				3  & (1,0,0,1,0,0,1,0,0,1)         & 38    & (1,0,0,1,0,0,1,0,0,1)         & 38    &              \\
				4  & (1,0,0,0,1,0,0,0,1,0)         & 24    & (1,0,0,1,1,0,0,0,1,0)         & 36    &              \\
				5  & (1,0,0,0,0,1,0,0,0,0)         & 17    & (1,0,1,1,0,1,0,0,0,0)         & 38    &              \\
				6  & (0,0,0,0,0,0,0,0,0,0)         & 0     & (0,1,1,1,0,0,0,0,0,1)         & 39    &              \\
				7  & \alert{(0,1,0,1,0,1,0,1,0,1)} & 41    & (0,1,0,1,0,1,0,0,0,1)         & 36    &              \\
				8  & \alert{(0,1,1,0,1,1,0,1,1,0)} & 43    & \alert{(0,1,1,1,1,0,0,0,1,0)} & 44    &              \\
				9  & \alert{(0,1,1,1,0,1,1,1,0,1)} & 57    & (0,1,1,1,0,0,0,0,1,1)         & 42    & = solution 1 \\
				10 & \alert{(0,1,1,1,1,0,1,1,1,1)} & 64    & (0,1,1,1,0,0,0,0,1,1)         & 42    & = solution 1 \\
			\end{tabular}
		\end{center}
	\end{table}
\end{frame}

%----------------------------------------------------
\begin{framefont}{\small}
	\begin{frame}
		\frametitle{Determining the reference set and combining 3 solutions}
		\begin{table}
			\begin{center}
				\begin{tabular}{rc|ccc|c}
					  & Candidate             & \multicolumn{3}{c}{Hamming Distance} & Minimal                      \\
					  & Solution              & Elite 1                              & Elite 2 & Elite 8 & Distance \\
					\hline
					3 & (1,0,0,1,0,0,1,0,0,1) & 5                                    & 4       & 7       & 4        \\
					4 & (1,0,0,1,1,0,0,0,1,0) & 5                                    & 2       & 3       & 2        \\
					5 & (1,0,1,1,0,1,0,0,0,0) & 5                                    & 2       & 5       & 2        \\
					6 & (0,1,1,1,0,0,0,0,0,1) & 1                                    & 4       & 3       & 1        \\
					7 & (0,1,0,1,0,1,0,0,0,1) & 3                                    & 6       & 5       & 3        \\
				\end{tabular}
			\end{center}

		\end{table}
		\begin{align*}
			\frac{38}{38+36+44} \cdot & (1,0,0,1,0,0,1,0,0,1) +                                                \\
			\frac{36}{38+36+44} \cdot & (0,1,0,1,0,1,0,0,0,1) +                                                \\
			\frac{44}{38+36+44} \cdot & (0,1,1,1,1,0,0,0,1,0)                                                  \\
			=                         & (0.322, 0.678, 0.373, 1.000, 0.373, 0.305, 0.322, 0.000, 0.373, 0.627) \\
			Round                     & (0, 1, 0, 1, 0, 0, 0, 0, 0, 1)
		\end{align*}

	\end{frame}
\end{framefont}


%----------------------------------------------------
%----------------------------------------------------
\subsection{Biased Random Key Genetic Algorithm (BRKGA)}
%----------------------------------------------------
%\frame{\center \Large \thesection .\thesubsection \ \textcolor{col_evidence}{\insertsubsection}}

\begin{frame}
	\frametitle{\thesection .\thesubsection \ \insertsubsection }
	\begin{block}{Working Principles}
		\begin{itemize}[<+->]
			\item A solution (permutation) is coded as an array of real numbers
			      \begin{itemize}
				      \item Sorting the array allows the permutation to be reconstructed
			      \end{itemize}
			\item The $E$ best solutions are kept for the next iteration
			\item The selection for reproduction always chooses a solution from the elite set $E$
			\item The child is generated with a uniform crossover, but with a probability $\neq 0.5$
			      \begin{itemize}
				      \item The selected elite solution is favoured
			      \end{itemize}
			\item $\lambda < \mu - E$ children are generated
			\item $\mu - E - \lambda$ new arrays are generated randomly to maintain diversity
		\end{itemize}
	\end{block}
\end{frame}

%----------------------------------------------------
\begin{frame}
	\frametitle{\insertsubsection : Illustration}
	\begin{figure}[h]
		\begin{center}
			\includepdftex{brkga}
		\end{center}
	\end{figure}
\end{frame}


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


%----------------------------------------------------
\begin{frame}
	\frametitle{\thesection .\thesubsection \ \insertsubsection}
	\begin{block}{General Idea}
		\begin{itemize}[<+->]
			\item{Gradually transform a starting solution into a given target solution}
			\item Evaluate at each stage the neighbour solutions that allow to get closer to the target one
			\item Choose the neighbour with the best objective function
			\item The path can also be tried in the opposite direction
			\item Or modify alternately the 2 solutions and stop when they are identical
		\end{itemize}
	\end{block}
\end{frame}

\begin{frame}
	\frametitle{Illustration of a Path Relinking for Permutations}
	\begin{figure}[h]
		\begin{center}
			\includepdftex{path_relinking}
		\end{center}
	\end{figure}
\end{frame}

\subsubsection{GRASP with Path Relinking}
%----------------------------------------------------
\begin{frame}[shrink]
	\frametitle{\insertsubsubsection}
	\input{./algorithms/GRASP_PR}
\end{frame}


%----------------------------------------------------
%----------------------------------------------------
\subsection{Fixed Set Search}
\subsection{Particle Swarm}
%\frame{\center \Large \thesection .\thesubsection \ \textcolor{col_evidence}{\insertsubsection}}

%----------------------------------------------------
\begin{frame}
	\frametitle{\thesection .\thesubsection \ \insertsubsection}
	\begin{block}{General idea: Solution = particle}
		\begin{itemize}[<+->]
			\item The solutions are represented by real number vectors
			\item Each particle has initially a random position and speed
			\item Each particle is influenced by the best position it has found and the position of the best particle in the swarm
		\end{itemize}
	\end{block}
\end{frame}

\begin{frame}
	\frametitle{Particle Swarm: Velocity and Position Update}
	\begin{figure}[h]
		\begin{center}
			\includepdftex{swarm_particle}
		\end{center}
	\end{figure}
\end{frame}


%----------------------------------------------------
\begin{framefont}{\tiny}
	\begin{frame}
		\frametitle{Particle Swarm Frame}
		\input{./algorithms/swarm}
	\end{frame}
\end{framefont}


