genetic_algorithm_tsp_api/
tsp_solver.rs

1use genetic_algorithm_traits::Population;
2use genetic_algorithm_tsp::{distance_mat, route};
3use std::time;
4
5/// From a `std::time::Duration` object compute the elapsed microseconds.
6///
7/// # Arguments
8///
9/// * `duration` - The time that has gone by.
10///
11/// # Examples
12///
13/// ```
14/// use std::time;
15/// use std::thread;
16/// use genetic_algorithm_tsp_api::tsp_solver;
17///
18/// let before = time::Instant::now();
19/// thread::sleep(time::Duration::from_millis(10));
20/// println!("Sleeping for 10 ms took {} ms", tsp_solver::duration_to_ms(before.elapsed()));
21/// ```
22pub fn duration_to_ms(duration: time::Duration) -> u64 {
23    let nano_seconds = duration.subsec_nanos() as u64;
24    (1000 * 1000 * 1000 * duration.as_secs() + nano_seconds) / (1000 * 1000)
25}
26
27/// Compute an route that for the traveling-salesman-problem defined by
28/// the distance matrix.
29///
30/// # Arguments
31///
32/// * `distance_matrix` - These distances define the fitness of an invidual.
33/// * `n_generation` - How many generations should the algorithm run for?
34/// * `n_routes` - How many routes should be kept in the population.
35/// * `n_random_route_per_generation` - How many random routes should be
36///     ingested in every generation to allow?
37pub fn solve_tsp(
38    distance_matrix: &distance_mat::DistanceMat,
39    n_generations: usize,
40    n_routes: usize,
41    n_random_individuals_per_generation: usize,
42    top_n: usize,
43) -> Vec<route::Route> {
44    let initial_population = distance_matrix.get_random_population(n_routes);
45    // Decay mutation probability.
46    (0..10000)
47        .step_by(10000 / n_generations)
48        .fold(
49            initial_population,
50            |population, mutation_probability_int| {
51                population
52                    .evolve(1.0 - (f64::from(mutation_probability_int) / 10000.0) as f32)
53                    // Add a few random inidividuals each round.
54                    .add_n_random_nodes(n_random_individuals_per_generation)
55                    .get_fittest_population(n_routes, distance_matrix)
56            },
57        )
58        .get_n_fittest(top_n, distance_matrix)
59}
60
61mod tests {
62    #[test]
63    fn test_duration() {
64        use super::duration_to_ms;
65        use std::thread;
66        use std::time;
67
68        // Test that after waiting for 12 ms, `duration_to_ms`
69        // reports correctly that 12 ms have gone by.
70        let before = time::Instant::now();
71        thread::sleep(time::Duration::from_millis(12));
72        assert_eq!(duration_to_ms(before.elapsed()), 12);
73    }
74    #[test]
75    fn test_solve_tsp() {
76        use super::solve_tsp;
77        use genetic_algorithm_tsp::distance_mat;
78        use std::fs;
79        // Just run `solve_tsp` for a simple distance matrix.
80        // Load in the test matrix.
81        let distances = distance_mat::DistanceMat::new(
82            fs::read_to_string("tests/test-data/6_cities.txt")
83                .unwrap()
84                .lines()
85                .collect::<Vec<&str>>()
86                .iter()
87                .map(|line| {
88                    line.split(";")
89                        .map(|float_string| float_string.parse::<f64>().unwrap())
90                        .collect::<Vec<f64>>()
91                })
92                .collect(),
93        );
94        // Get a solution
95        let _ = solve_tsp(&distances, 20, 10, 10, 3);
96    }
97}
genetic_algorithm_tsp_api/tsp_solver.rs

genetic_algorithm_tsp_api/
tsp_solver.rs
