1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88

//! 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:
//!
//!```bash
//!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 [Simulated
//! Annealing](https://wikipedia.org/wiki/Simulated_annealing).
//!
//!# Examples
//!
//!```
//!let solution = metaheuristics::simulated_annealing::solve(&mut problem, runtime);
//!```

use rand::{thread_rng, Rng};
use super::Metaheuristics;
use time::{Duration, PreciseTime};

/// Returns an approximate solution to your optimisation problem using Simulated Annealing
///
///```
///let solution = metaheuristics::simulated_annealing::solve(&mut problem, runtime);
///```
///
/// `problem` is the type that implements the `Metaheuristics` trait.
///
/// `runtime` is a `time::Duration` specifying how long to spend searching for a solution.

pub fn solve<T>(problem: &mut Metaheuristics<T>, runtime: Duration) -> T {
    let mut best_candidate      = problem.generate_candidate();
    let mut annealing_candidate = problem.tweak_candidate(&best_candidate);
    let start_time              = PreciseTime::now();
    let runtime_in_milliseconds = runtime.num_milliseconds() as f64;

    loop {
        let portion_elapsed = (start_time.to(PreciseTime::now()).num_milliseconds() as f64) / runtime_in_milliseconds;

        if portion_elapsed >= 1.0 {
            break;
        }

        let next_candidate        = problem.tweak_candidate(&annealing_candidate);
        let next_is_better        = problem.rank_candidate(&next_candidate) > problem.rank_candidate(&annealing_candidate);
        let replacement_threshold = 1.0f64.exp().powf(-10.0 * portion_elapsed.powf(3.0));

        if next_is_better || (thread_rng().gen_range(0.0, 1.0) < replacement_threshold) {
            annealing_candidate = next_candidate;
        }

        if problem.rank_candidate(&annealing_candidate) > problem.rank_candidate(&best_candidate) {
            best_candidate = problem.clone_candidate(&annealing_candidate);
        }
    }

    best_candidate
}