 # Find maximum value from array using Simulated Annealing

Based on the example from: https://en.wikipedia.org/wiki/Simulated_annealing

Unlike the Hill climbing algorithm,. this example will “move around” the array at random to sample other values. There is a chance of selecting a lower value (than our current selection) as long as the system temperature is greater than zero.

You may wonder “Does this actually work?”
In short: usually.

While the draw function is showing all samples, as written, the `system` will only sample up to half of the values in the `data` array.

Will sometimes only find a value close to the highest (restricted number of samples) but is unlikely to get stuck on a local maximum.

Edit: Though the function was correct, my comments on “always-” or “never switch” were swapped.

``````float MAX_TEMP = 100.0;
int K_MAX = 300;
int N = 1024;

int k = K_MAX;
int MAX_STEPS = N / 2; // sample at most half of the data
int samplecount = 0;

float[] data = new float[N];
State s;

class State
{
int idx;
State(int id)
{
idx = id;
}
}

float getEnergyOf(State s)
{
return data[s.idx];
}

// chance of switching to neighbor
float thresholdOfSwitching(float e, float ne, float t)
{
if (t > 0.0)
{
float ratio = t / MAX_TEMP;
return 1.0 - ratio;
}
else
{
// with the decision to switch based on: random(0,1) > thresholdOfSwitching(...)
if (e < ne)
{
return -1; // always switch to neighbor
}
else if (e > ne)
{
return 2; // never switch to neighbor
}
else // equal
{
// Is this better than not switching?
// Might kick us out of the global maximum but
//   could also get us out of a local maximum...
return 0.5;
}
}
}

void mouseClicked()
{
k = K_MAX;
samplecount = 0;
s = new State((int)random(N));
// Generate another set of data
float f1 = random(1,4);
float f2 = random(5,10);
float f3 = random(10,20);
float f4 = random(20,30);
for (int x=0; x<N; x++)
{
data[x] = 50*sin(f1*x*TWO_PI/width) +
25*sin(f2*x*TWO_PI/width) +
12.5*sin(f3*x*TWO_PI/width) +
6.25*sin(f4*x*TWO_PI/width);
}
}

void setup()
{
size(1024,256,JAVA2D);
s = new State((int)random(N));
for (int x=0; x<N; x++)
{
data[x] = 50*sin(2*x*TWO_PI/width) +
25*sin(7*x*TWO_PI/width) +
12.5*sin(17*x*TWO_PI/width) +
6.25*sin(27*x*TWO_PI/width);
}
fill(255);
stroke(255);
frameRate(30);
}

void draw()
{
background(0);
for (int x=0; x<N; x++)
{
// The algorithm is finding the max value, invert y axis
point(x, -data[x] + height/2);
}
line(s.idx,0, s.idx,height);

float temp = MAX_TEMP * k / K_MAX;
if (samplecount < MAX_STEPS)
{
State neighbor = new State((int)random(N)); // Sample data array
if (random(0,1) > thresholdOfSwitching(getEnergyOf(s), getEnergyOf(neighbor), temp))
{
s = neighbor;
}
k--;
samplecount++;
}

text("Sample count: " + samplecount, 20,20);
}
``````
2 Likes