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 tool-set}
   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 wrapped 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 Computer 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 unbiased.
\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 
  connected --- 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 unbiased.

\end{proof}


\subsubsection{Results and stability}

We first want to analyse the dependence of the results on the number of 
iterations of the algorithm. To perform such an experiment we made up a 
wrapper above the main algorithm which calls the random search on 
different number of iterations. To smooth up the results and obtain
more exploitable datas, we also perform an 
arithmetic mean of fifteen searches for each expermiement. The flowchart of
the conducts of this experiment is descibed in the figure:

\begin{figure}
 \begin{mdframed}
  \label{rand_flow}
\includegraphics[scale=0.4]{flow_rand_2.pdf}
\caption{Flowchart of the random search experiement for dependence on iterations}
\end{mdframed}
\end{figure}

The results are compiled in the figure
\begin{figure}
  \label{rand_flow}
\includegraphics[scale=0.6]{rand_res.png}
\caption{Dependence on iterations number: D=2}
\end{figure}

The same experiment has been conducted on dimension 4 -- with Halton basis
7, 13, 29, 3 ---:
\begin{figure}
  \label{rand_flow}
\includegraphics[scale=0.6]{rand_search_4.png}
\caption{Dependence on iterations number: D=4}
\end{figure}


The same experiment has been conducted on dimension 6 -- with Halton basis
7, 13, 29, 3, 11, 31---:
\begin{figure}
  \label{rand_flow}
\includegraphics[scale=0.6]{rand_search_4.png}
\caption{Dependence on iterations number D=6}
\end{figure}

Based on the same wrapper, we also experiments the dependence on the number
of points, in dimension 2, 4, 6.
\begin{figure}
  \label{rand_flow}
\includegraphics[scale=0.6]{low_discr_rand.png}
\caption{Dependence on iterations number}
\end{figure}

\subsection{Local Search}
  Blabla+Pipeline
\subsection{Evolutionary heuristics}
  Blabla+Pipeline
\subsection{Genetic heuristics}
  Blabla+Pipeline

\section{Results}


\section{Conclusion}

\end{document}