Changeset 46

Timestamp:

Dec 18, 2009, 1:43:33 AM (15 years ago)

Author:

Rick van der Zwet

Message:

Report finished = sleep

Location:

liacs/nc/low-correlation

Files:

• autocorrelation.m (modified) (2 diffs)
• mcs-call.m (modified) (2 diffs)
• mcs-fitness.eps (added)
• mcs.m (modified) (2 diffs)
• report.tex (modified) (3 diffs)
• sa-call.m (modified) (2 diffs)
• sa-fitness.eps (modified) ( previous)

liacs/nc/low-correlation/autocorrelation.m

@@ -3 +3 @@
 %-----------------------------------------------------------------------
 function [f] = autocorrelation(pop)
-% Given a population of binary sequences, this function calculates the merit
-% function according to the formula specified in the exercise description.  The
-% input pop is the given matrix.
-% The output f is the merit factor calculated (row vector).
+% Given a population of binary sequences, this function calculates
+% the merit function according to the formula specified in the
+% exercise description. The input pop is the given matrix. The
+% output f is the merit factor calculated (row vector).
 
 n = size(pop,1);
@@ -12 +12 @@
 E = zeros(1,m);
 
-% Calculated efficiently in a matrix-notation; auxilary matrices - Y1,Y2 - are
-% initialized in every iteration. They are shifted form of the original y
-% vectors. The diagonal of the dot-squared Y2*Y1 matrix is exactly the inner
-% sum of merit function.
+% Calculated efficiently in a matrix-notation; auxilary matrices -
+% Y1,Y2 - are initialized in every iteration. They are shifted form
+% of the original y vectors. The diagonal of the dot-squared Y2*Y1
+% matrix is exactly the inner sum of merit function.
 for k=1:n-1
     Y1=pop(1:n-k,:);

liacs/nc/low-correlation/mcs-call.m

@@ -7 +7 @@
 % best_20 = [-1,1,1,-1,-1,-1,1,1,-1,1,-1,-1,-1,1,-1,1,1,1,1,1];
 
-% Basic variables
-iterations = [1:10:200];
-repetitions = 20;
-length = 20;
+%% Basic variables
+iterations = 1000;
+length = 222;
+repetitions = 1;
 
 % Plot the stuff
-fitnesses = [];
-for iteration = iterations
-  fitness = [];
-  for rep = 1:repetitions
-    fprintf('Iter:%i, Rep:%i\n',iteration,rep);
-    [new_fitness, value] =  mcs(length,iteration);
-    fitness = [fitness, new_fitness];
+[iteration_history, fitness_history] = mcs(length,iterations);
 
-    % Little hack to display output nicely
-    % disp(rot90(value,-1));
-  end
-  fitnesses = [fitnesses,mean(fitness)];
-end
-
-plot(iterations,fitnesses);
+plot(iteration_history,fitness_history);
 title(sprintf('Monte-Carlo Search on Low-Corretation set - repetitions %i',repetitions));
 ylabel('fitness');
@@ -33 +21 @@
 grid on;
 legend(sprintf('Length %i',length));
-print('mcs-fitness.eps','-depsc2');
+print(sprintf('mcs-fitness-%f.eps',max(fitness_history)),'-depsc2');
+max(fitness_history)
 

liacs/nc/low-correlation/mcs.m

@@ -8 +8 @@
 % autocorrelation(best_20);
 
-function [fitness,value] = mcs(length, iterations)
+function [iteration_history,fitness_history] = mcs(length, iterations)
+  iteration_history = [];
+  fitness_history = [];
+
   best_fitness = 0;
-  for i = 1:iterations
+  for iteration = 1:iterations
     % Generate a random column s={-1,1}^n
     n = length;
@@ -23 +26 @@
       best_fitness = fitness;
     end
+    iteration_history = [ iteration_history, iteration ];
+    fitness_history = [ fitness_history, best_fitness ]; 
   end
-  fitness = best_fitness;
-  value = best_value;
 end

liacs/nc/low-correlation/report.tex

@@ -17 +17 @@
 \usepackage{float}
 \usepackage{color}
+\usepackage{subfig}
 \floatstyle{ruled}
 \newfloat{result}{thp}{lop}
@@ -73 +74 @@
 those numbers are not found.
 
-\begin{center}
 \begin{table}
   \caption{Best known values of low-autocorrelation problem}
-  \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}
+  \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}
-\end{center}
 
 \section{Approach}
@@ -111 +112 @@
 \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.
+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\%\%
+\unixcmd{octave -q \%\%PROGRAM\%\%}
 
 \section{Results}
-All experiments are run 20 times the best solution is choosen
+All experiments are run 5 times the best solution is choosen 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}
-\newpage
+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 algoritms are preforming much worse then the best found solutions.
 \section{Appendix 1}
+\label{app:code}
 \include{autocorrelation.m}
 \include{initseq.m}

liacs/nc/low-correlation/sa-call.m

@@ -6 +6 @@
 %% Basic variables
 iterations = 10000;
-length = 20;
+length = 222;
 
 
@@ -21 +21 @@
 grid on;
 legend(sprintf('Length %i',length));
-print('sa-fitness.eps','-depsc2');
+print(sprintf('sa-fitness-%f.eps',max(fitness_history)),'-depsc2');
+max(fitness_history)