// (Constants are chosen by intuition, so feel free to change them to work better.

​

function setup() {

  createCanvas(700, 700);

  vert = []; // towns

  sz = 100; // number of towns

  for (var i = 0; i < sz; i++) {

    v = createVector(random(40, width - 40), random(40, height - 40));

    vert.push(v);

  }

​

  maxTemp = (width + height)/18; // Starting temperature. It should be of the same order as the length of connections. 18 just works well. For other sz, it may be necessary to make it "colder".

  time = 0;

  maxTime = 3500; // Number of frames that algorithm runs. If this is too low, algorithm stops before it can make it to the best solution. I could't figure out a decent  formula, thus it should be chosen by trial and error for each sz.

  frame = 0;

}

​

function draw() {

  background(0);

  frameRate(10);

  var T = temperature((time + 1) / maxTime);

​

  beginShape();

  for (var i = 0; i < sz; i++) {

    vertex(vert[i].x, vert[i].y);

    fill(255);

    noStroke();

    ellipse(vert[i].x, vert[i].y, 8, 8);

  }

  noFill();

  stroke(255);

  strokeWeight(2);

  endShape(CLOSE);

​

  var pathlength = 0;

  for (var i = 0; i < sz; i++) {

    var d = vert[i].dist(vert[(i + 1) % sz]);

    pathlength += d;

  }

​

  // Choose 2 random disjoint edges, and calculate fitness of a neighbor generated by switching them.

  var d1 = 0;

  var d2 = T + 1;

  var i = 0;

  var j = 0;

  while (d2 - d1 > T || i-j < 2) {

    i = floor(random(sz));

    j = floor(random(sz));

    d1 = vert[i].dist(vert[(i + 1) % sz]) + vert[j].dist(vert[(j + 1) % sz]);

    d2 = vert[i].dist(vert[j]) + vert[(i + 1) % sz].dist(vert[(j + 1) % sz]);

  }

  var newlength = pathlength - d1 + d2;

​

​

  //2-opt move. Reverses a sub-path to switch two pairs of edges.

  if (probability(pathlength, newlength, T) >= random()) {

    m = vert.slice(Math.min((i + 1) % sz, (j + 1) % sz), Math.max((i + 1) % sz, (j + 1) % sz)).reverse();

    l = vert.slice(0, Math.min((i + 1) % sz, (j + 1) % sz));

    r = vert.slice(Math.max((i + 1) % sz, (j + 1) % sz), sz);

    vert = l.concat(m).concat(r);

  }

  time++;

​

  textSize(25);

  text(pathlength, 160, 20);

  text(frame, 20, 20);

  frame++;

  if (time == maxTime) {

    noLoop();

  }

}

​

// fr - fraction of time already spent.

// I use linear temperature function, as it's simple, but something like logistic may be better.

function temperature(fr) {

  return maxTemp * (1 - fr) + 0.0001;

}

​

// c - current fitness, n - fitness of the generated neighbor, T - temperature.

// Probability of switching to the neighbor. Took from the original SA. Might also be tweaked to be better, but this function performs well, so probably isn't worth it.

function probability(c, n, T) {

  if (n < c) {

    return 1;

  } else {

    return exp(-(n - c) / T);

  }

}

​

​

​

​

​

​

​

​

​

​

​

​

​

​

​

​

​

​

​

​

​

​

​

//