source: liacs/nc/low-correlation/sa.m@ 35

% Simulated Annealing low-autocorrelation program
% BSDLicence
% Rick van der Zwet - 0433373 - <hvdzwet@liacs.nl>

% 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 number = randint(low,high)
    number = round(rand() * (high - low)) + low;
endfunction

function new = mutation(old)
    loc = randint(1,length(old));
    old(loc) = old(loc) * -1;
    new = old;
endfunction

function s = initseq(n)
    % Generate a random column s={-1,1}^n
    s = rand(n,1);
    s = round(s);
    s = s - (s == 0);
endfunction

function [fitness,value] = sa(length, temperature, stopLimit)
    best_fitness = 0;
    s = initseq(length);
    stopCounter = 0;

    while (stopCounter < stopLimit)
        % Generate new mutation
        newseq = mutation(s);

        % Better is always accept
        fitness = autocorrelation(newseq);
        if (fitness > best_fitness)
            best_value = s;
            best_fitness = fitness;
            s = newseq;
            fitness
            disp(rot90(newseq,-1));
            stopCounter = 0;
        else
            % Make the next 'move' less atractive
            temperature =- 1;

            stopCounter += 1;
            % Accept on an certain probability
            if (temperature < 0)
                break;
            else 
                if(randint(0,temperature) > temperature / 4)
                    s = newseq;
                endif
            endif
        endif
    endwhile
    value = best_value;
    fitness = best_fitness;
endfunction

%% Basic variables
iterations = [1:10:1000];
repetitions = 20;
length = 20;
temperature = 1000;


% Plot the stuff
fitnesses = [];
for iteration = iterations
    fitness = [];
    for rep = 1:repetitions
        printf('Iter:%i, Rep:%i\n',iteration,rep);
        [new_fitness, value] =  sa(length,iteration,temperature);
        fitness = [fitness, new_fitness];

        % Little hack to display output nicely
        % disp(rot90(value,-1));
    endfor
    
    fitnesses = [fitnesses,mean(fitness)];
endfor

plot(iterations,fitnesses);
title(sprintf('Simulated Annealing on Low-Corretation set - repetitions %i',repetitions));
ylabel('fitness');
xlabel('iterations');
grid on;
legend(sprintf('Length %i',length));
print("sa-fitness.eps","-depsc2");