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