Changeset 32

Timestamp:

Dec 13, 2009, 9:41:09 PM (15 years ago)

Author:

Rick van der Zwet

Message:

SA - fitness calculations

Location:

liacs/nc/low-correlation

Files:

• sa-fitness.eps (added)
• sa.m (copied) (copied from liacs/nc/low-correlation/mcs.m ) (4 diffs)

liacs/nc/low-correlation/sa.m

@@ -1 @@
-% Monte-Carlo Search Algoritm on low-autocorrelation program
+% Simulated Annealing low-autocorrelation program
 % BSDLicence
 % Rick van der Zwet - 0433373 - <hvdzwet@liacs.nl>
@@ -7 +7 @@
 % autocorrelation(best_20);
 
-function [fitness,value] = mcs(length, iterations)
+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;
-    for i = 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);
+    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
-    endfor
+    endwhile
+    value = best_value;
     fitness = best_fitness;
-    value = best_value;
 endfunction
 
-% Basic variables
-iterations = [1:10:200];
+%% Basic variables
+iterations = [1:10:1000];
 repetitions = 20;
 length = 20;
+temperature = 1000;
 
 
@@ -39 +74 @@
     for rep = 1:repetitions
         printf('Iter:%i, Rep:%i\n',iteration,rep);
-        [new_fitness, value] =  mcs(length,iteration);
+        [new_fitness, value] =  sa(length,iteration,temperature);
         fitness = [fitness, new_fitness];
 
@@ -50 +85 @@
 
 plot(iterations,fitnesses);
-title(sprintf('Monte-Carlo Search on Low-Corretation set - repetitions %i',repetitions));
+title(sprintf('Simulated Annealing on Low-Corretation set - repetitions %i',repetitions));
 ylabel('fitness');
 xlabel('iterations');
 grid on;
 legend(sprintf('Length %i',length));
-print("mcs-fitness.eps","-depsc2");
+print("sa-fitness.eps","-depsc2");