Find maximum value from array using Simulated Annealing

Gallery
1

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