source: liacs/ccs/op4/report.tex@ 355

\documentclass[a4paper,12pt]{article}
\usepackage{hyperref}
\usepackage{a4wide}
%\usepackage{indentfirst}
\usepackage[english]{babel}
\usepackage{graphics}
%\usepackage[pdftex]{graphicx}
\usepackage{latexsym}
\usepackage{fancyhdr}
\usepackage{fancyvrb}

\pagestyle{fancyplain}
\newcommand{\tstamp}{\today}
\newcommand{\id}{$ $Id: report.tex 195 2007-05-30 01:04:25Z rick $ $}
\lfoot[\fancyplain{\tstamp}{\tstamp}]   {\fancyplain{\tstamp}{\tstamp}}
\cfoot[\fancyplain{\id}{\id}]           {\fancyplain{\id}{\id}}
\rfoot[\fancyplain{\thepage}{\thepage}] {\fancyplain{\thepage}{\thepage}}


\title{ Challenges in Computer Science \\
\large{Assignment 4 - genetic search algorithm}}
\author{Rick van der Zwet\\
  \texttt{<hvdzwet@liacs.nl>}\\
  \\
  LIACS\\
  Leiden Universiteit\\
  Niels Bohrweg 1\\
  2333 CA Leiden\\
  The Netherlands}
\date{\today}
\begin{document}
\maketitle
\section{Introduction}
The assignment given out during the seminar of Natural Computing
Group of LIACS\footnote{http://natcomp.liacs.nl/}  will have the
following context:
\begin{quote}
You are required to implement an Evolutionary Algorithm for tacking the
low-autocorrelation problem. Given your implementation, run your
algorithm on strings of the lengths given the table, and report your
results. A MATLAB code for the objective function is given to you in the
following location:
\texttt{http://www.liacs.nl/home/oshir/code/merit.m} (Backup at
Appendix~\ref{file:merit.m})
Its documentation:
\texttt{http://www.liacs.nl/home/oshir/code/autocorr.pdf}
\end{quote}

\section{Problem}
The given problem, the so-called \textsl{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 follows.\\
\textbf{Feasible Solutions:} Binary Sequences
$\overrightarrow{y} \in \{-1,+1\}^n$ \\
\textbf{Objective Function:}
\begin{equation}
\displaystyle 
f(\overrightarrow{y}) =
      \frac{n^2}{2 \cdot E\overrightarrow{y}} \longrightarrow maximization
\end{equation}
s.t.
\begin{equation}
\displaystyle 
E(\overrightarrow{y}) = \sum_{k=1}^{n-1}
\left(
      \sum_{i=1}^{n-k} y_i \cdot y_{i+k}
\right) ^2
\end{equation}

Find a way using genetic algorithm to get the optional solutions

\section{Theory}
A genetic algorithm will use 'evolution' to get the best possible
results. It will normally be executed in the following order

\begin{enumerate}
\item Generate N number of random parents
\item Determine best parents
\item start generating offspring \label{again}
\item Determine best offspring
\item Combine the best parents and offspring to number of N new parents
\item Check if end condition is matched else go-to \ref{again} again
\end{enumerate}

There are a few well known mutations to generate new nodes
\begin{itemize}
\item Crossover: Combine 2 parts of 2 nodes to a new node. Example (using crossover point 3):
\begin{verbatim}
    A = 0 1 0 | 1 1 0
    B = 1 1 1 | 0 0 0
    A' = 0 1 0  0 0 0
    B' = 1 1 1  1 1 0
\end{verbatim}
\item Mutation: Change a few values in a node. Example using mutation
point 3.
\begin{verbatim}
    A = 0 1 0 1 1 0
    A' = 0 1 1 1 1 0
\end{verbatim}
\end{itemize}

\subsection{Algorithm}
I have introduced one new mutation way, cross-flip. It will flip all
values starting from a certain point. Example, using point 3
\begin{verbatim}
    A = 0 1 0 1 1 0
    A' = 0 1 1 0 0 1
\end{verbatim}

This will be my algorithm
\begin{verbatim}
01: Generate N random nodes on stack @A
02: for n in 0 to size A
03:     exit loop if run for $round_size times
04:     check mutation(n) children are better and unshift to stack @A
05:     check cross-flip(n) children are better and unshift to stack @A
06:     check crossover(n) children are better and unshift to stack @A
07:     if n on end of the stack then remove all but A[0:5], add 5 random
08:        strings and do crossover on all variants.
09:     if improvement then set n to beginning
10: add best result (@A[0]) to the @W array but keep the array sorted and
    not longer then 10
11: check if we have been here $maxround times, exit and give result
12: check if we have been here such that ($times % $winnercompare) == 0
       start generating special results  by combining the best results of @W
       into @A and go-to 02;
13: start putting 75 random strings into @A and go-to 02:
\end{verbatim}

\section{Implementation}
I wrote my implementation in Perl code, with a stack
implementation and used as much references as possible.

\section{Experiments}
I ran all tests 5 times and will display the best merit factor and
corresponding string. Vectors are written in run-length notation: each
figure indicates the number of consecutive elements with the same 
sign. 

\begin{table}[h]
\caption{Experiment results}
\begin{tabular}{l || l | l}
Size & m-factor & vector \\
\hline
  3 &  4.5 & 2,1\\
  4 &  4.0 & 1,3\\
  5 &  6.5 & 3,1,1\\
 10 & 10.0 & 3,3,1,2,1,1\\
 15 &  7.5 & 3,3,1,3,1,2,1,1\\
 20 &  7.7 & 5,1,1,3,1,1,2,3,2,1\\
 30 &  6.7 & 4,2,5,1,2,3,1,2,1,1,1,1,3,1,1,1\\
 50 &  5.0 & 1,1,1,1,1,1,1,2,2,3,4,1,7,2,2,2,1,2,1,1,5,4,1,1,2\\
 75 &  4.7 & 1,1,4,5,2,1,1,2,4,4,1,3,3,2,1,1,1,1,1,2,2,3,1,4,2,2,1,3,1,1,2,1,4,1,3,1,2\\
\end{tabular}
\end{table}

\section{Conclusion}
The algorithm works pretty well on the small size numbers. The big
numbers (n > 20) are not scoring good, cause the script/program is
causing time problems.

Writing the implementation in Perl is too slow. It's not generation
the bigger rates at a decent speed\footnotemark, cause the Perl code is not optional
yet. When looking at the profiler output (Appendix~\ref{text:profiler}), the merit
function could be optimised to get a higher throughput.

\footnotetext{one round of n = 100 takes at a dual
core Pentium 4 3Ghz and 2GB RAM about 2 minutes}
%\begin{thebibliography}{XX}
%
%\end{thebibliography}

\section{Appendix}

\subsection{merit.m}
\label{file:merit.m}
\VerbatimInput{merit.m}
%\newpage
\subsection{merit.pl}
\label{file:merit.pl}
\VerbatimInput{merit.pl}
%\newpage
\subsection{profiler output}
\label{text:profiler}
\begin{verbatim}
Total Elapsed Time = 33.07120 Seconds
  User+System Time = 32.94120 Seconds
Exclusive Times
%Time ExclSec CumulS #Calls sec/call Csec/c  Name
 85.9   28.31 28.312  99474   0.0003 0.0003  main::merit
 6.00   1.975  1.975 990000   0.0000 0.0000  main::flip
 5.22   1.718 17.022   2000   0.0009 0.0085  main::crossovers
 3.26   1.073 15.030   2000   0.0005 0.0075  main::mutations
 2.84   0.935 28.587 126000   0.0000 0.0002  main::try_merit
 0.50   0.166  0.163   2529   0.0001 0.0001  main::combine
 0.25   0.083  0.164     20   0.0042 0.0082  main::reinit
 0.22   0.074 34.493      1   0.0736 34.492  main::main
 0.16   0.054  1.075   2000   0.0000 0.0005  main::crossover
 0.15   0.048  0.042   1365   0.0000 0.0000  main::randarray
 0.08   0.027  0.027  18532   0.0000 0.0000  main::message
 0.06   0.019  0.019    134   0.0001 0.0001  main::array2string
 0.03   0.009  0.028    134   0.0001 0.0002  main::printer
 0.00       - -0.000      1        -      -  strict::bits
 0.00       - -0.000      1        -      -  strict::import
\end{verbatim}

\end{document}