% Monte-Carlo Search Algoritm on low-autocorrelation program
% BSDLicence
% Rick van der Zwet - 0433373 - <hvdzwet@liacs.nl>
% $Id: mcs.m 46 2009-12-18 01:43:33Z rick $

% Brute-force result of length 20
% best_20 = [-1,1,1,-1,-1,-1,1,1,-1,1,-1,-1,-1,1,-1,1,1,1,1,1];
% autocorrelation(best_20);

function [iteration_history,fitness_history] = mcs(length, iterations)
  iteration_history = [];
  fitness_history = [];

  best_fitness = 0;
  for iteration = 1:iterations
    % Generate a random column s={-1,1}^n
    n = length;
    s = rand(n,1);
    s = round(s);
    s = s - (s == 0);
  
    % Find whether we are better than everything else
    fitness = autocorrelation(s);
    if (fitness > best_fitness)
      best_value = s;
      best_fitness = fitness;
    end
    iteration_history = [ iteration_history, iteration ];
    fitness_history = [ fitness_history, best_fitness ]; 
  end
end