% ------------------------------------------------------------------------
\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 independents 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 performances. 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 hyper-threaded to 2.8GHz, 8 Go 1600 MHz DDR3.
  \item 2.8 GHz Intel Quad Core i7 hyper-threaded 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}

On these machines, some basic profiling has make clear that 
the main bottleneck of the computations is hiding in the \emph{computation
of the discrepency}. The chosen algorithm and implantation of this 
cost function is the DEM-algorithm of \emph{Magnus Wahlstr\o m}.\medskip

All the experiments has been conducted on dimension 2,3,4 
--- with a fixed Halton basis 7, 13, 29, 3 ---. Some minor tests have
been made in order to discuss the dependency of the discrepency and 
efficiency of the heuristics with regards to the values chosen for the
prime base. The average results remains roughly identical when taking 
changing these primes and taking them in the range [2, 100]. For such
a reason we decided to pursue the full computations with a fixed 
basis.


\subsection{Algorithmic insights}

To perform an experiment we made up a 
loop above the main algorithm which calls the chosen heuristic multiple 
times in order to smooth up the results and obtain more exploitable datas.
Then an arithmetic mean of the result is performed on the values. In addition
extremal values are also given in order to construct error bands graphs.

A flowchart of the conduct of one experiment is described in the 
flowchart~\ref{insight_flow}. The number of iteration of the heuristic is 
I and the number of full restart is N. Th efunction Heuristic() correspond to
a single step of the chosen heursitic. We now present an in-depth view of
the implemented heuristics.

\begin{figure}
 \begin{mdframed}
  \label{insight_flow}
\includegraphics[scale=0.4]{insight.pdf}
\caption{Flowchart of a single experiment}
\end{mdframed}
\end{figure}


\section{Heuristics developed}

\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 
 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 analyze the dependence of the results on the number of 
iterations of the heuristic, in order to discuss its stability. 
The results are compiled in the figures~\ref{rand_iter2}\ref{rand_iter3}.
As expected from a fully random search, the error bands are very large for 
low number of iterations ($15\%$ of the value for 200 iterations) and tends
to shrink with a bigger number of iterations (arround $5\%$ for 1600 iterations).
The average results are quite stable, they decrease progressively with 
the growing number of iterations, but seems to get to a limits after 1000 iterations. This value acts as a threshold for the interesting number of iterations.
As such interesting results can be conducted with \emph{only} 1000 iterations, 
without alterating too much the quality of the set with regards to its
discrepency and this heuristic.

\begin{figure}
  \label{rand_iter2}
\includegraphics[scale=0.3]{Results/random_iter.png}
\caption{Dependence on iterations number: D=2}
\end{figure}
\begin{figure}
  \label{rand_iter3}
\includegraphics[scale=0.3]{Results/random_iter_3.png}
\caption{Dependence on iterations number: D=3}
\end{figure}



\subsection{Evolutionary heuristic: Simulated 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}

\subsubsection{Dependence on the temperature}

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

\subsubsection{Stability with regards to the number of iterations}

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