Struct SequentialSelector

Source

pub struct SequentialSelector<Solution> { /* private fields */ }

Expand description

Select operators in a consecutive manner

Iterate through all operators, consecutively, starting from the first one. When an improvement is made, the iteration is restarted from the beginning.

Implementations§

Source §

impl<Solution> SequentialSelector<Solution>

Source

pub fn new() -> Self

Examples found in repository ?

examples/tsp.rs (line 48)

19fn main() {
20    // init
21    let n = 100;
22    let width = 100.;
23    let height = 100.;
24    let computation_time_max = Duration::new(2, 0);
25
26    // create random cities
27    let seed = 0;
28    let mut rng = rand::rngs::StdRng::seed_from_u64(seed);
29    let cities: Vec<City> = (0..n)
30        .map(|id| create_random_city(id, width, height, &mut rng))
31        .collect();
32    let cities = Box::new(cities);
33
34    let now = SystemTime::now();
35    let random_tour = construct_random_tour(&mut cities.clone().into_iter(), &mut rng);
36    let duration_random = now.elapsed().unwrap();
37    let random_outcome = Outcome::new(random_tour, duration_random);
38    let now = SystemTime::now();
39    let greedy_tour = construct_greedy_tour(&mut cities.clone().into_iter(), &mut rng);
40    let duration_greedy = now.elapsed().unwrap();
41    let greedy_outcome = Outcome::new(greedy_tour, duration_greedy);
42
43    // optimize with VNS
44    let operator1 = TwoOpt::new(cities.as_slice());
45    let operator2 = Insertion::new(cities.as_slice());
46    let vns = VariableNeighborhoodSearch::builder()
47        .selector(
48            SequentialSelector::new()
49                .option(operator1)
50                .option(operator2),
51        )
52        .terminator(TimeTerminator::new(computation_time_max))
53        .build();
54    let vns_outcome = vns.optimize_timed(random_outcome.solution().clone());
55
56    // optimize with Simulated Annealing
57    let temperature = 100.;
58    let cooling_factor = 0.05;
59    let minimum_acceptance_probability = 0.05;
60    let schedule = FactorSchedule::new(temperature, cooling_factor);
61    let operator = TwoOpt::new(cities.as_slice());
62    let sa = SimulatedAnnealing::builder()
63        .selector(RandomSelector::new(rng.clone()).option(operator))
64        .operator(TwoOptRandom)
65        .cooling_schedule(schedule)
66        .terminator(
67            Terminator::builder()
68                .computation_time(computation_time_max)
69                .build(),
70        )
71        .minimum_acceptance_probability(minimum_acceptance_probability)
72        .rng(rng.clone())
73        .build();
74    let sa_outcome = sa.optimize_timed(random_outcome.solution().clone());
75
76    // optimize with Large Neighborhood Search
77    let n_destroyed_cities = 2;
78    let destroyer = TSPDestroyer::new(n_destroyed_cities);
79    let repairer = TSPRepairer::new(*cities.clone());
80    let lns = LargeNeighborhoodSearch::builder()
81        .selector_destroyer(SequentialSelector::new().option(destroyer))
82        .selector_repairer(SequentialSelector::new().option(repairer))
83        .terminator(
84            Terminator::builder()
85                .computation_time(computation_time_max)
86                .build(),
87        )
88        .rng(rng.clone())
89        .build();
90    let lns_outcome = lns.optimize_timed(random_outcome.solution().clone());
91
92    // optimize with adaptive VNS
93    let decay = 0.5;
94    let operator1 = TwoOpt::new(cities.as_slice());
95    let operator2 = Insertion::new(cities.as_slice());
96    let adaptive_vns = VariableNeighborhoodSearch::builder()
97        .selector(
98            AdaptiveSelector::default_weights(decay, rng)
99                .operator(operator1)
100                .operator(operator2),
101        )
102        .terminator(TimeTerminator::new(computation_time_max))
103        .build();
104    let adaptive_vns_outcome = adaptive_vns.optimize_timed(random_outcome.solution().clone());
105
106    // display results
107    show_solution(random_outcome, "random");
108    show_solution(greedy_outcome, "greedy");
109    show_solution(vns_outcome, "vns");
110    show_solution(adaptive_vns_outcome, "adaptive vns");
111    show_solution(sa_outcome, "sa");
112    show_solution(lns_outcome, "lns");
113}

Source

pub fn option<T: Operator<Solution = Solution> + 'static>( self, option: T, ) -> Self

Examples found in repository ?

examples/tsp.rs (line 49)

19fn main() {
20    // init
21    let n = 100;
22    let width = 100.;
23    let height = 100.;
24    let computation_time_max = Duration::new(2, 0);
25
26    // create random cities
27    let seed = 0;
28    let mut rng = rand::rngs::StdRng::seed_from_u64(seed);
29    let cities: Vec<City> = (0..n)
30        .map(|id| create_random_city(id, width, height, &mut rng))
31        .collect();
32    let cities = Box::new(cities);
33
34    let now = SystemTime::now();
35    let random_tour = construct_random_tour(&mut cities.clone().into_iter(), &mut rng);
36    let duration_random = now.elapsed().unwrap();
37    let random_outcome = Outcome::new(random_tour, duration_random);
38    let now = SystemTime::now();
39    let greedy_tour = construct_greedy_tour(&mut cities.clone().into_iter(), &mut rng);
40    let duration_greedy = now.elapsed().unwrap();
41    let greedy_outcome = Outcome::new(greedy_tour, duration_greedy);
42
43    // optimize with VNS
44    let operator1 = TwoOpt::new(cities.as_slice());
45    let operator2 = Insertion::new(cities.as_slice());
46    let vns = VariableNeighborhoodSearch::builder()
47        .selector(
48            SequentialSelector::new()
49                .option(operator1)
50                .option(operator2),
51        )
52        .terminator(TimeTerminator::new(computation_time_max))
53        .build();
54    let vns_outcome = vns.optimize_timed(random_outcome.solution().clone());
55
56    // optimize with Simulated Annealing
57    let temperature = 100.;
58    let cooling_factor = 0.05;
59    let minimum_acceptance_probability = 0.05;
60    let schedule = FactorSchedule::new(temperature, cooling_factor);
61    let operator = TwoOpt::new(cities.as_slice());
62    let sa = SimulatedAnnealing::builder()
63        .selector(RandomSelector::new(rng.clone()).option(operator))
64        .operator(TwoOptRandom)
65        .cooling_schedule(schedule)
66        .terminator(
67            Terminator::builder()
68                .computation_time(computation_time_max)
69                .build(),
70        )
71        .minimum_acceptance_probability(minimum_acceptance_probability)
72        .rng(rng.clone())
73        .build();
74    let sa_outcome = sa.optimize_timed(random_outcome.solution().clone());
75
76    // optimize with Large Neighborhood Search
77    let n_destroyed_cities = 2;
78    let destroyer = TSPDestroyer::new(n_destroyed_cities);
79    let repairer = TSPRepairer::new(*cities.clone());
80    let lns = LargeNeighborhoodSearch::builder()
81        .selector_destroyer(SequentialSelector::new().option(destroyer))
82        .selector_repairer(SequentialSelector::new().option(repairer))
83        .terminator(
84            Terminator::builder()
85                .computation_time(computation_time_max)
86                .build(),
87        )
88        .rng(rng.clone())
89        .build();
90    let lns_outcome = lns.optimize_timed(random_outcome.solution().clone());
91
92    // optimize with adaptive VNS
93    let decay = 0.5;
94    let operator1 = TwoOpt::new(cities.as_slice());
95    let operator2 = Insertion::new(cities.as_slice());
96    let adaptive_vns = VariableNeighborhoodSearch::builder()
97        .selector(
98            AdaptiveSelector::default_weights(decay, rng)
99                .operator(operator1)
100                .operator(operator2),
101        )
102        .terminator(TimeTerminator::new(computation_time_max))
103        .build();
104    let adaptive_vns_outcome = adaptive_vns.optimize_timed(random_outcome.solution().clone());
105
106    // display results
107    show_solution(random_outcome, "random");
108    show_solution(greedy_outcome, "greedy");
109    show_solution(vns_outcome, "vns");
110    show_solution(adaptive_vns_outcome, "adaptive vns");
111    show_solution(sa_outcome, "sa");
112    show_solution(lns_outcome, "lns");
113}