Module metaheuristics::simulated_annealing

Find an approximate solution to your optimisation problem using Simulated Annealing

When metal is heated to melting point, its atoms are let loose to move freely, and do so in a random fashion. If cooled too quickly (a process known as quenching), the random positioning of atoms gets frozen in time, creating a hard and brittle metal. However if allowed to cool at a slower rate (a process known as annealing), the atoms arrange in a more unform fashion, creating a soft and malleable metal. Simulated annealing borrows from this process.

Here we duplicate the functionality of the metaheuristics::hill_climbing module but with slight modification - at each iteration, we introduce a probability of going downhill! This probability mimicks the cooling temperature from its physical counterpart. At first, the probability of going downhill is 1. But as time moves on, we lower that probability until time has run out.

The probability of going downhill, or cooling temperature, is given by the following function:

P(t) = e^(-10*(t^3))

and can be seen by the following gnuplot:

cat <<EOF | gnuplot -p
  set xrange [0:1];
  set yrange [0:1];
  set xlabel "Runtime";
  set ylabel "Probability of going downhill";
  set style line 12 lc rgb '#9bffff' lt 0 lw 1;
  set grid back ls 12;
  set style line 11 lc rgb '#5980d4' lt 1;
  set border 3 back ls 11;
  set tics nomirror;
  set key off;
  f(x) = exp(-10*(x**3));
  plot f(x) with lines lc rgb '#d52339';
EOF

For more info on Simulated Annealing, please see the Simulated Annealing Wikipedia article.

Examples

let solution = metaheuristics::simulated_annealing::solve(&mut problem, runtime);

Functions

solve

Returns an approximate solution to your optimisation problem using Simulated Annealing