metaheuristics/simulated_annealing/
mod.rs

1//! Find an approximate solution to your optimisation problem using Simulated Annealing
2//!
3//! When metal is heated to melting point, its atoms are let loose to move freely, and do so in a
4//! random fashion. If cooled too quickly (a process known as quenching), the random positioning of
5//! atoms gets frozen in time, creating a hard and brittle metal. However if allowed to cool at a
6//! slower rate (a process known as annealing), the atoms arrange in a more uniform fashion,
7//! creating a soft and malleable metal. Simulated annealing borrows from this process.
8//!
9//! Here we duplicate the functionality of the `metaheuristics::hill_climbing` module but with
10//! slight modification - at each iteration, we introduce a probability of going downhill! This
11//! probability mimicks the cooling temperature from its physical counterpart. At first, the
12//! probability of going downhill is 1. But as time moves on, we lower that probability until time
13//! has run out.
14//!
15//! The probability of going downhill, or cooling temperature, is given by the following function:
16//!ignore
17//!    P(t) = e^(-10*(t^3))
18//!
19//! and can be seen by the following gnuplot:
20//!
21//!```bash
22//!cat <<EOF | gnuplot -p
23//!  set xrange [0:1];
24//!  set yrange [0:1];
25//!  set xlabel "Runtime";
26//!  set ylabel "Probability of going downhill";
27//!  set style line 12 lc rgb '#9bffff' lt 0 lw 1;
28//!  set grid back ls 12;
29//!  set style line 11 lc rgb '#5980d4' lt 1;
30//!  set border 3 back ls 11;
31//!  set tics nomirror;
32//!  set key off;
33//!  f(x) = exp(-10*(x**3));
34//!  plot f(x) with lines lc rgb '#d52339';
35//!EOF
36//!```
37//!
38//! For more info on Simulated Annealing, please see the [Simulated
39//! Annealing](https://wikipedia.org/wiki/Simulated_annealing) Wikipedia article.
40//!
41//!# Examples
42//!
43//!```ignore
44//!let solution = metaheuristics::simulated_annealing::solve(&mut problem, runtime);
45//!```
46
47use super::Metaheuristics;
48use rand::{thread_rng, Rng};
49use time::{Duration, Instant};
50
51/// Returns an approximate solution to your optimisation problem using Simulated Annealing
52///
53///# Parameters
54///
55/// `problem` is the type that implements the `Metaheuristics` trait.
56///
57/// `runtime` is a `time::Duration` specifying how long to spend searching for a solution.
58///
59///# Examples
60///
61///```ignore
62///let solution = metaheuristics::simulated_annealing::solve(&mut problem, runtime);
63///```
64pub fn solve<T>(problem: &mut dyn Metaheuristics<T>, runtime: Duration) -> T {
65    let mut best_candidate = problem.generate_candidate();
66    let mut annealing_candidate = problem.tweak_candidate(&best_candidate);
67    let start_time = Instant::now();
68    let runtime_in_milliseconds = runtime.whole_milliseconds() as f64;
69
70    loop {
71        let portion_elapsed =
72            (start_time.elapsed().whole_milliseconds() as f64) / runtime_in_milliseconds;
73
74        if portion_elapsed >= 1.0 {
75            break;
76        }
77
78        let next_candidate = problem.tweak_candidate(&annealing_candidate);
79        let next_is_better =
80            problem.rank_candidate(&next_candidate) > problem.rank_candidate(&annealing_candidate);
81        let replacement_threshold = 1.0f64.exp().powf(-10.0 * portion_elapsed.powf(3.0));
82
83        if next_is_better || (thread_rng().gen_range(0.0..1.0) < replacement_threshold) {
84            annealing_candidate = next_candidate;
85        }
86
87        if problem.rank_candidate(&annealing_candidate) > problem.rank_candidate(&best_candidate) {
88            best_candidate = problem.clone_candidate(&annealing_candidate);
89        }
90    }
91
92    best_candidate
93}
metaheuristics/simulated_annealing/mod.rs

metaheuristics/simulated_annealing/
mod.rs
