source: liacs/NC2010/low-correlation/report.tex@ 229

%
% $Id: report.tex 571 2008-04-20 17:31:04Z rick $
%

\documentclass[12pt,a4paper]{article}

\usepackage{listings}

\frenchspacing
\usepackage[english,dutch]{babel}
\selectlanguage{dutch}
\usepackage{graphicx}
\usepackage{url}
\usepackage{multicol}
\usepackage{fancybox}
\usepackage{amssymb,amsmath}
\usepackage{float}
\usepackage{color}
\usepackage{subfig}
\usepackage{marvosym}
\floatstyle{ruled}
\newfloat{result}{thp}{lop}
\floatname{result}{Result}

\input{highlight.sty}

\title{The low-autocorrelation problem\\
\large{Practical Assignments Natural Computing, 2009}}
\author{Rick van der Zwet\\
  \texttt{<hvdzwet@liacs.nl>}}
\date{\today}


\begin{document}
\newcommand{\wekacmd}[1]{\begin{quote}\small{\texttt{#1}}\end{quote}}
\newcommand{\unixcmd}[1]{\begin{quote}\small{\texttt{#1}}\end{quote}}


\maketitle

\section{Introduction}
The report is focused on the so-called \emph{low-autocorrelation problem of
binary sequences}, is subject to actual research and is of big interest for
industrial applications, e.g. communications and electrical engineering. Its
description goes as follows.

\textbf{Feasible Solutions:} Binary Sequences $\vec{y} \in \{-1,+1\}^n$

\textbf{Objective Function:}
\begin{equation}
f(\vec{y}) = \frac{n^2}{2 \cdot E(\vec{y})} \longrightarrow maximization
\end{equation}

\begin{equation}
E(\vec{y}) = \displaystyle\sum_{k=1}^{n-1} (\sum_{i=1}^{n-k} y_i \cdot y_{i+k})^2
\end{equation}

\section{Problem description}
Due to the huge 'exploding' possibilities it is not possible to walk trough the
whole list of possibilities, so we need alternative approaches to tackle this
problem. First we will try the \emph{Monte Carlo Search algorithm [MCS]} and next try
\emph{Simulated Annealing [SA]}.

\emph{MCS} is all about random sequence generation and trying to find a good
solution, do a small adjustment on the solution and compare the new solution
again.

\emph{SA} takes a more and less the same approach, but it also accept small
'losses' from time-to-time. But as time passes it get less likely to accept
'bad solutions'.

\section{Statistics}
Of course many people have run numerous computer hours on finding the best
possible fitness as shown in table~\ref{tab:best}. The algorithms used to find
those numbers are not found.

\begin{table}
  \caption{Best known values of low-autocorrelation problem}
  \begin{center}
    \begin{tabular}{| l | c | r | }
      \hline
      $n$ & Best known $f$ \\
      \hline \hline          
      20  & 7.6923 \\ \hline 
      50  & 8.1699 \\ \hline
      100 & 8.6505 \\ \hline
      200 & 7.4738 \\ \hline
      222 & 7.0426 \\ \hline
    \end{tabular}
  \end{center}
  \label{tab:best}
\end{table}

\section{Approach}
The \emph{MCS} is implemented straight-forward from the Wikipedia
page\footnote{http://en.wikipedia.org/wiki/Monte\_Carlo\_method}. The mutation
choosing is flipping one bit in the array.

For the \emph{SA} implemented also comes straight from 'the book'
\footnote{http://en.wikipedia.org/wiki/Simulated\_annealing}, the process
choosing for the cooling-down sequence is taken from the dutch Wikipedia page
'Simulated annealing', which is nice indicator when to choose something when
the solution is worse (logically, better solutions will always be accepted).
\footnote{http://nl.wikipedia.org/wiki/Simulated\_annealing}:
\begin{math}
p = e^{\frac{f(i)-f(j)}{c}}
\end{math}

\section{Implementation}
The code is written in
\emph{Octave}\footnote{http://www.gnu.org/software/octave/} which is the
open-source 'variant' of \emph{MATLAB}\copyright 
\footnote{http://www.mathworks.com/products/matlab/}. There are small minor
differences between them, but all code is made compatible to to run on both
systems. The code is to be found in Appendix~\ref{app:code}.

As work is done remotely, the following commands are used:
\unixcmd{matlab-bin -nojvm -nodesktop -nosplash -nodisplay < \%\%PROGRAM\%\%}
\unixcmd{octave -q \%\%PROGRAM\%\%}

\section{Results}
All experiments are run 5 times the best solution is chosen and will be
resented at table~\ref{tab:result}. Iteration size is set to 1000. For $n=20$
the best fitness history is shown at figure~\ref{fig:fitness}.

\begin{table}
  \caption{Best known values of low-autocorrelation problem}
  \begin{center}
    \begin{tabular}{| r | r | r | r | }
      \hline
      $n$ & \multicolumn{3}{|c|}{Best fitness} \\
          & known & MCS & SA \\
      \hline \hline          
      20  & 7.6923 & 4.3478 & 4.7619 \\ \hline 
      50  & 8.1699 & 2.4752 & 2.6882 \\ \hline
      100 & 8.6505 & 1.8342 & 1.7470 \\ \hline
      200 & 7.4738 & 1.8678 & 1.5733 \\ \hline
      222 & 7.0426 & 1.5657 & 1.4493 \\ \hline
    \end{tabular}
    \label{tab:result}
  \end{center}
\end{table}

\begin{figure}[htp]
  \begin{center}
    \subfloat[SA]{\label{fig:edge-a}\includegraphics[scale=0.4]{sa-fitness.eps}}
    \subfloat[MCS]{\label{fig:edge-b}\includegraphics[scale=0.4]{mcs-fitness.eps}}
  \end{center}
  \caption{Fitness throughout the iterations}
  \label{fig:fitness}
\end{figure}

\section{Conclusions}
Looking at the graphs the fitness was still increasing so a larger iteration
size would make the fitness a better result. Secondly the \emph{SA} is
preforming much worse on large number than the \emph{MCS} one. It seems to the
temperature function is not working as expected. 

Both algorithms are preforming much worse then the best found solutions.
\section{Appendix 1}
\label{app:code}
\include{autocorrelation.m}
\include{initseq.m}
\include{mcs-call.m}
\include{mcs.m}
\include{mutation.m}
\include{randint.m}
\include{sa-call.m}
\include{sa.m}
\end{document}