projet_optim_m2/main.tex

% ------------------------------------------------------------------------
\documentclass{llncs}
\input{prelude}
\begin{document} 
\title{Star Discrepancies for generalized Halton points}
% \titlerunning{}  % abbreviated title (for running head)
%                                     also used for the TOC unless
%                                     \toctitle is used

\author{Thomas Espitau\inst{1} \and Olivier Marty\inst{1}} 
%
% \authorrunning{} % abbreviated author list (for running head)
%
%%%% list of authors for the TOC (use if author list has to be modified)
% \tocauthor{}
%
\institute{
  $\mbox{}^1$ ENS Cachan \qquad
}

\maketitle

\makeatletter

\makeatother


\begin{abstract}
\end{abstract}


\section{Introduction}

\section{General architecture of the toolset}
   Big pipeline + pool + blabla\medskip

   Un truc bien ca serait d'avoir un truc modulaire (genre les heuristiques 
   sont des "blocs" et l'outil appelle un bloc quand il veut faire son test
   en l'appelant en multicore" 

   (c'est stupide mais ca fera un beau schéma!)



\section{Heuristics devlopped}

\subsection{Fully random search (Test case)}
 The first heuristic implemented is rge random search. We generates
 random sets of Halton points and select the best set with regard to its
 discrepancy iteratively. The process is wraped up in the following 
 flowchart~\ref{rand_flow}. In order to generate at each step a random 
 permutation, we transform it directly from the previous one.
  More precisely the permutation is a singleton object which have method 
  random, built on the Knuth Fisher Yates shuffle. This algorithm allows
  us to generate an uniformly chosen  permutation at each step. We recall 
  this fact and detail the algorithm in the following section.
\begin{figure}
 \begin{mdframed}
  \label{rand_flow}
\includegraphics[scale=0.4]{flow_rand.pdf}
\caption{Flowchart of the random search}
\end{mdframed}
\end{figure}


  \subsubsection{The Knuth-Fisher-Yates shuffle}

The Fisher–Yates shuffle is an algorithm for generating a random permutation 
of a finite sets. The Fisher–Yates shuffle is unbiased, so that every 
permutation is equally likely. We present here the Durstenfeld variant of 
the algorithm, presented by Knuth in \emph{The Art of Computrer programming}.
The algorithm's time complexity is here $O(n)$, compared to $O(n^2)$ of 
the naive implementation.

\begin{algorithm}[H]
  \SetAlgoLined
  \SetKwFunction{Rand}{Rand}
  \SetKwFunction{Swap}{Swap}
  \KwData{A table T[1..n]}
  \KwResult{Same table T, shuffled}
  \For{$i\leftarrow 1$ \KwTo $n-1$}{
     $j \leftarrow$ \Rand{$[1,n-i]$}\;
     \Swap{$T[i], T[i+j]$}\;
    }
  \caption{KFY algorithm}
\end{algorithm}


\begin{lemma}
  The resulting permutation of KFY is unbiaised.
\end{lemma}
\begin{proof}
  Let consider the set $[1,\ldots n]$ as the vertices of a random graph 
  constructed as the trace of the execution of the algorithm: 
  an edge $(i,j)$ exists in the graph if and only if the swap of $T[i]$ and
  $T[j]$ had been executed. This graph encodes the permutation represented by
  $T$. To be able to encode any permutation the considered graph must be connex 
  --- in order to allow any pairs of points to be swapped ---.
  Since by construction every points is reached by an edge, and that there 
  exists exactly $n-1$ edges, we can conclude directly that any permutation can
  be reached by the algorithm. Since the probability of getting a fixed graph 
  of $n-1$ edges with every edges of degree at least one is $n!^{-1}$, the 
  algorithm is thus unbiaised.

\end{proof}


\subsubsection{Results and stability}
\subsection{Local Search}
  Blabla+Pipeline
\subsection{Evolutionary heuristics}
  Blabla+Pipeline
\subsection{Genetic heuristics}
  Blabla+Pipeline

\section{Results}


\section{Conclusion}

\end{document}