% ------------------------------------------------------------------------
\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}

The testing tool is aimed to be modular: it is made of independant blocks that
are interfaced trough a scheduler. More precisely a master wrapper is written
in Python that calls a first layer which performs the chosen heuristic. This
layer is written in C++ for performences. The given discrepancy algorithm 
--- written in C --- is called when evaluations of a state is needed.
The wrapper dispatch the computations on the multi-core architecture of 
modern computers\footnote{for us, between 2 and 4 physical cores and 4 or 8 
virtual cores}. This basic architecture is described in figure~\ref{main_flow}.
Experiments were conducted on two machines: 
\begin{itemize}
  \item 2.4 GHz Intel Dual Core i5 hyperthreaded to 2.8GHz, 8 Go 1600 MHz DDR3.
  \item 2.8 GHz Intel Quad Core i7 hyperthreaded to 3.1GHz, 8 Go 1600 MHz DDR3.
\end{itemize}

\begin{figure}
  \label{main_flow}
\includegraphics[scale=0.6]{main_flow.pdf}
\caption{Tool overview}
\end{figure}


\subsection{Algorithmics insights}

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


\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 experiments. The flowchart of
the conducts of this experiment is desibed in the figure:

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

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



\subsection{Evolutionary heuristic: Simmulated annealing and local search}
\begin{figure}
 \begin{mdframed}
  \label{rand_flow}
\includegraphics[scale=0.4]{flow_recuit.pdf}
\caption{Flowchart of the simulated annealing local search heuristic}
\end{mdframed}
\end{figure}

\begin{figure}
  \label{rand_flow}
\includegraphics[scale=0.3]{Results/resu_temp3.png}
\caption{Dependence on iterations number: D=3}
\end{figure}

\begin{figure}
  \label{rand_flow}
\includegraphics[scale=0.3]{Results/resu_temp3_zoom.png}
\caption{Dependence on iterations number: D=3}
\end{figure}
\begin{figure}
  \label{rand_flow}
\includegraphics[scale=0.3]{Results/resu_2_temp.png}
\caption{Dependence on iterations number: D=3}
\end{figure}

\begin{figure}
  \label{rand_flow}
\includegraphics[scale=0.3]{Results/sa_iter.png}
\caption{Dependence on iterations number: D=3}
\end{figure}

\subsection{Genetic (5+5) search}
\begin{figure}
 \begin{mdframed}
  \label{rand_flow}
\includegraphics[scale=0.4]{flow_recuit.pdf}
\caption{Flowchart of the simulated annealing local search heuristic}
\end{mdframed}
\end{figure}

\begin{figure}
  \label{rand_flow}
\includegraphics[scale=0.3]{Results/res_gen_2.png}
\caption{Dependence on iterations number: D=3}
\end{figure}

\begin{figure}
  \label{rand_flow}
\includegraphics[scale=0.3]{Results/res_gen_2_zoom.png}
\caption{Dependence on iterations number: D=3}
\end{figure}
\begin{figure}
  \label{rand_flow}
\includegraphics[scale=0.3]{Results/res_gen_3_zoom.png}
\caption{Dependence on iterations number: D=3}
\end{figure}

\begin{figure}
  \label{rand_flow}
\includegraphics[scale=0.3]{Results/res_gen_4_zoom.png}
\caption{Dependence on iterations number: D=3}
\end{figure}

\section{Results}


\section{Conclusion}

\end{document}