genetic_algorithm_tsp/routes.rs
1use crate::distance_mat::DistanceMat;
2use crate::route::Route;
3use crate::utils::random_permutation;
4use crossbeam_utils::thread;
5use fasthash_fork::xx;
6use genetic_algorithm_traits::{Individual, Population};
7use std::collections::HashSet;
8use std::convert::From;
9use std::fmt;
10use std::time::Instant;
11
12/// From a vector of routes create a Hashet with capacity length and hash function `xx-hash`.
13///
14/// # Arguments
15///
16/// * `routes` - The routes that should be added to the hashset.
17///
18fn route_vec_to_xx_hashset(routes: Vec<Route>) -> HashSet<Route, xx::Hash64> {
19 let n_routes = routes.len();
20 let mut routes_as_hashset = HashSet::with_capacity_and_hasher(n_routes, xx::Hash64);
21 for route in routes {
22 routes_as_hashset.insert(route);
23 }
24 routes_as_hashset
25}
26
27/// The `Population` is your current pools of routes that you would to improve by evolving them.
28#[derive(Debug, Clone, PartialEq)]
29pub struct Routes {
30 /// An individual routes is made from `routes`, e.g. individuals that might your given problem
31 /// better of worse.
32 routes: HashSet<Route, xx::Hash64>,
33}
34impl fmt::Display for Routes {
35 fn fmt(&self, formatter: &mut fmt::Formatter) -> fmt::Result {
36 write!(
37 formatter,
38 "Routes([{}\n])",
39 self.iter()
40 .map(|route| format!("{}", route))
41 .collect::<Vec<String>>()
42 .join("\n\t")
43 )
44 }
45}
46
47// Convert a Vector of solutioons to a routes.
48impl From<Vec<Route>> for Routes {
49 /// Create a new Population of Routse from a vector of routes.
50 ///
51 /// # Arguments
52 ///
53 /// * `routes` - The routes you collected so far and would like to put into your
54 /// routes.
55 ///
56 /// # Examples
57 ///
58 /// ```
59 /// use genetic_algorithm_tsp::routes::Routes;
60 /// use genetic_algorithm_tsp::route::Route;
61 ///
62 /// let routes = Routes::from(vec![Route::new(vec![0,1,2]), Route::new(vec![1,0,2])]);
63 /// ```
64 fn from(routes: Vec<Route>) -> Self {
65 // When this this will be `evolved` at most n_routes * (n_routes - 1) new
66 // routes will be generate and all `n_routes` will be retained.
67 Routes {
68 routes: route_vec_to_xx_hashset(routes),
69 }
70 }
71}
72
73impl Routes {
74 /// Create a new Population of routes by creating random invidiual routes.
75 ///
76 /// # Arguments
77 ///
78 /// * `n_routse` - The number of routes your population of routes should contain.
79 /// * `route_length` - The length of an individual route.
80 ///
81 /// # Examples
82 ///
83 /// ```
84 /// use genetic_algorithm_tsp::routes::Routes;
85 /// use genetic_algorithm_tsp::route::Route;
86 ///
87 /// let routes = Routes::from(vec![Route::new(vec![0,1,2]), Route::new(vec![1,0,2])]);
88 /// ```
89 pub fn random(n_routes: usize, route_length: usize) -> Self {
90 let all_objects = (0..route_length).collect::<Vec<usize>>();
91 let mut routes = HashSet::with_capacity_and_hasher(n_routes, xx::Hash64);
92
93 while routes.len() < n_routes {
94 routes.insert(Route::new(random_permutation(&all_objects)));
95 }
96
97 Routes { routes }
98 }
99 /// Add new routes to a `Routes`-object and create a new `Routes`-object
100 ///
101 /// # Arguments
102 ///
103 /// * `routes` - A vector of `Route`s that should be added.
104 ///
105 /// # Examples
106 ///
107 /// ```
108 /// use genetic_algorithm_tsp::routes::Routes;
109 /// use genetic_algorithm_tsp::route::Route;
110 ///
111 /// let current_routes = Routes::from(vec![Route::new(vec![1]), Route::new(vec![2])]);
112 /// let extended_routes = current_routes.add_vec_route(vec![Route::new(vec![3]), Route::new(vec![4])]);
113 ///
114 /// ```
115 pub fn add_vec_route(self, routes: Vec<Route>) -> Self {
116 Routes::from(
117 self.routes
118 .iter()
119 .chain(routes.iter())
120 .cloned()
121 .collect::<Vec<Route>>(),
122 )
123 }
124 /// Combine two routes objects.
125 ///
126 /// # Arguments
127 ///
128 /// * `routes` - A vector of `Route`s that should be added.
129 ///
130 /// # Examples
131 ///
132 /// ```
133 /// use genetic_algorithm_tsp::routes::Routes;
134 /// use genetic_algorithm_tsp::route::Route;
135 ///
136 /// let current_routes = Routes::from(vec![Route::new(vec![1]), Route::new(vec![2])]);
137 /// let other_routes = Routes::from(vec![Route::new(vec![3]), Route::new(vec![4])]);
138 /// println!("{}", current_routes.combine_routes(other_routes));
139 /// ```
140 pub fn combine_routes(self, other_routes: Routes) -> Self {
141 self.add_vec_route(other_routes.iter().cloned().collect::<Vec<Route>>())
142 }
143 /// Get the number of nodes for the `Route`'s in this `Routes`-object.
144 ///
145 /// # Examples
146 ///
147 /// ```
148 /// use genetic_algorithm_tsp::route::Route;
149 /// use genetic_algorithm_tsp::routes::Routes;
150 ///
151 /// let routes_with_three_nodes = Routes::from(vec![Route::new(vec![1,2,3,]), Route::new(vec![4,5,6])]);
152 /// println!("The route have {} nodes", routes_with_three_nodes.get_n_nodes());
153 /// ```
154 pub fn get_n_nodes(&self) -> usize {
155 *self
156 .iter()
157 .take(1)
158 .map(|node| node.get_n_nodes())
159 .collect::<Vec<usize>>()
160 .first()
161 .unwrap()
162 }
163 /// Add n random nodes to your current pool.
164 ///
165 /// # Arguments:
166 ///
167 /// `n_random_nodes`: The number of random nodes that should be added.
168 ///
169 /// # Examples
170 /// ```
171 /// use genetic_algorithm_tsp::route::Route;
172 /// use genetic_algorithm_tsp::routes::Routes;
173 ///
174 /// let a_single_route = Routes::from(vec![Route::new(vec![0,1,2])]);
175 /// println!("{}", a_single_route.add_n_random_nodes(1));
176 /// ```
177 pub fn add_n_random_nodes(self, n_random_nodes: usize) -> Self {
178 let number_of_nodes = self.get_n_nodes();
179 self.combine_routes(Routes::random(n_random_nodes, number_of_nodes))
180 }
181}
182
183impl<'a> Population<'a> for Routes {
184 type Individual = Route;
185 type IndividualCollection = std::collections::hash_set::Iter<'a, Route>;
186
187 /// Given your pool of current routes, compute the fitness of your individuals to solve the
188 /// problem at hand.
189 ///
190 /// # Arguments
191 ///
192 /// * `distance_mat` - The distances between nodes that is neccessary to computes how well the route
193 /// work in terms of the TSP
194 ///
195 /// # Examples
196 ///
197 /// ```
198 /// use genetic_algorithm_tsp::routes::Routes;
199 /// use genetic_algorithm_tsp::route::Route;
200 /// use genetic_algorithm_tsp::distance_mat::DistanceMat;
201 /// use genetic_algorithm_traits::Population;
202 ///
203 /// let distance_matrix = DistanceMat::new(vec![vec![0.0,1.0,2.0], vec![1.0,0.0,3.0], vec![2.0,3.0,0.0]]);
204 /// let routes = Routes::from(vec![Route::new(vec![0,1,2]), Route::new(vec![1,0,2])]);
205 /// println!("Your routes's fitnesses: {:?}", routes.fitnesses(&distance_matrix));
206 /// ```
207 // fn fitnesses(&self, distance_mat: &DistanceMat) -> Vec<(f64, &Route)> {
208 // self.iter()
209 // .map(|route| (route.fitness(distance_mat), route))
210 // .collect()
211 // }
212 /// Get the n fittest individuals in your routes as new routes object. This is typically used
213 /// to select the top n inidividuals, before continuing to evolve the routes further.
214 ///
215 /// # Arguments
216 ///
217 /// * `n` - The number of individuals you would like to have.
218 /// * `distance_mat` - The distance matrix the fitness should be evaluated on.
219 ///
220 /// # Examples
221 ///
222 /// ```
223 /// use genetic_algorithm_tsp::routes::Routes;
224 /// use genetic_algorithm_tsp::route::Route;
225 /// use genetic_algorithm_tsp::distance_mat::DistanceMat;
226 /// use genetic_algorithm_traits::Population;
227 ///
228 /// let distance_matrix = DistanceMat::new(vec![vec![0.0,1.0,2.0], vec![1.0,0.0,3.0], vec![2.0,3.0,0.0]]);
229 /// let routes = Routes::from(vec![Route::new(vec![0,1,2]), Route::new(vec![1,0,2])]);
230 /// let my_fittest_routes = routes.get_fittest_population(2, &distance_matrix);
231 /// ```
232 fn get_fittest_population(&self, n: usize, distance_mat: &DistanceMat) -> Routes {
233 Routes {
234 routes: route_vec_to_xx_hashset(self.get_n_fittest(n, distance_mat)),
235 }
236 }
237 /// Evolve your population.
238 ///
239 /// The evolution consists of the following stages:
240 /// 1) `crossover` between all 1,...,n routes excluding the route itself.
241 /// 2) `mutate` is applied to all individuals.
242 ///
243 /// # Arguments
244 ///
245 /// * `mutate_prob` - The probabilty of an inviduals beeing mutated. Is applied via `individuals.mutate`.
246 ///
247 /// # Examples
248 ///
249 /// ```
250 /// use genetic_algorithm_tsp::routes::Routes;
251 /// use genetic_algorithm_tsp::route::Route;
252 /// use genetic_algorithm_traits::Population;
253 /// use genetic_algorithm_tsp::distance_mat::DistanceMat;
254 ///
255 /// let distance_matrix = DistanceMat::new(vec![vec![0.0,1.0,2.0], vec![1.0,0.0,3.0], vec![2.0,3.0,0.0]]);
256 /// let routes = Routes::from(vec![Route::new(vec![0,1,2]), Route::new(vec![1,0,2])]);
257 /// let evolved_routes = routes.evolve(0.5);
258 /// ```
259 fn evolve(&self, mutate_prob: f32) -> Routes {
260 let mutated_individuals = self.evolve_individuals(mutate_prob);
261 Routes {
262 routes: route_vec_to_xx_hashset(mutated_individuals),
263 }
264 }
265 /// Iterate over the individuals of your population.
266 ///
267 /// # Examples
268 ///
269 /// ```
270 /// use genetic_algorithm_tsp::routes::Routes;
271 /// use genetic_algorithm_tsp::route::Route;
272 /// use genetic_algorithm_traits::Population;
273 ///
274 /// let routes = Routes::from(vec![Route::new(vec![0,1,2]), Route::new(vec![1,0,2])]);
275 /// for route in routes.iter(){
276 /// println!("{:?}", route);
277 /// }
278 /// ```
279 fn iter(&'a self) -> std::collections::hash_set::Iter<Route> {
280 self.routes.iter()
281 }
282}
283
284/// Given an initial population evolve it for `n_generations` while keeping `size_generation`
285/// individuals. The final population will be returned.
286///
287/// # Arguments
288///
289/// * `initial_population` - Your initial population that should be evolved.
290/// * `n_generations` - How many times should your population be evolved?
291/// * `size_generation` - How many individuals should be kept after evolving it.
292/// * `distance_matrix` - The distance matrix on which the fitness will be computed on.
293///
294/// # Examples
295///
296/// ```
297/// use genetic_algorithm_tsp::routes::{Routes, evolve_population};
298/// use genetic_algorithm_tsp::route::Route;
299/// use genetic_algorithm_tsp::distance_mat::DistanceMat;
300///
301/// let evolved_population = evolve_population(
302/// Routes::from(vec![Route::new(vec![0,1,2]), Route::new(vec![1,0,2])]),
303/// 10,
304/// 10,
305/// &DistanceMat::new(vec![vec![0.0,1.0,2.0], vec![1.0,0.0,3.0], vec![2.0,3.0,0.0]]),
306/// 0
307/// );
308/// ```
309pub fn evolve_population(
310 initial_population: Routes,
311 n_generations: usize,
312 size_generation: usize,
313 distance_matrix: &DistanceMat,
314 n_jobs: usize,
315) -> Routes {
316 if n_jobs == 0 {
317 // single-thread
318 (0..n_generations).fold(initial_population, |pop, _| {
319 pop.evolve(0.5)
320 .get_fittest_population(size_generation, distance_matrix)
321 })
322 } else {
323 // Multi-threaded execution
324 thread::scope(|s| {
325 let mut result = Vec::new();
326 for _ in 0..n_jobs {
327 let this_population = initial_population.clone();
328 result.push(s.spawn(move |_| -> Vec<Route> {
329 (0..((n_generations / n_jobs) + 1))
330 .fold(this_population, |pop, _| {
331 pop.evolve(0.5)
332 .get_fittest_population(size_generation, distance_matrix)
333 })
334 .get_n_fittest(size_generation, distance_matrix)
335 }))
336 }
337 Routes::from(
338 result
339 .into_iter()
340 .flat_map(|thread| thread.join().unwrap())
341 .collect::<Vec<Route>>(),
342 )
343 })
344 .unwrap()
345 }
346}
347/// Compute the time in milliseconds that it takes for a genetic algorithm to run.
348///
349/// # Arguments
350///
351/// * `n_generations` - How many generations should the algorithm evolve?
352/// * `size_generation` - How many individuals should be selected at the end of each
353/// evolution step.
354/// * `dist_mat` - What is the distance matrix for your TSP.
355///
356/// ```
357pub fn benchmark_population(
358 n_generations: usize,
359 size_generation: usize,
360 dist_mat: &DistanceMat,
361 n_jobs: usize,
362) -> (u64, f64) {
363 // End-to-end test: does the error of the route get down?
364 let before = Instant::now();
365 let final_population = evolve_population(
366 Routes::random(size_generation, dist_mat.n_units()),
367 n_generations,
368 size_generation,
369 dist_mat,
370 n_jobs,
371 );
372 let duration = before.elapsed();
373 let nanos = duration.subsec_nanos() as u64;
374 (
375 (1000 * 1000 * 1000 * duration.as_secs() + nanos) / (1000 * 1000),
376 final_population.get_n_fittest(1, dist_mat)[0].fitness(dist_mat),
377 )
378}
379
380#[cfg(test)]
381mod tests {
382 use super::*;
383 use crate::test_utils::{test_dist_mat, valid_permutation};
384 #[test]
385 fn test_route_vec_to_xx_hashset() {
386 let routes_vec = vec![
387 Route::new(vec![0, 1, 2]),
388 Route::new(vec![0, 1, 2]),
389 Route::new(vec![1, 0, 2]),
390 ];
391 let routes_as_hashet: HashSet<Route, xx::Hash64> =
392 route_vec_to_xx_hashset(routes_vec.clone());
393 // Routes in the hashset are unique, so the duplicate in `routes_vec`
394 // should only be in there once.
395 assert_eq!(routes_as_hashet.len(), 2);
396 // But all routes from route_vec should be in there.
397 for route in &routes_vec {
398 assert!(routes_as_hashet.contains(route))
399 }
400 }
401 #[test]
402 fn test_format() {
403 let route_to_print = Routes::from(vec![Route::new(vec![1, 2])]);
404 assert_eq!(format!("{}", route_to_print), "Routes([Route([1, 2])\n])");
405 }
406 #[test]
407 fn from_routes_vector() {
408 assert_eq!(
409 Routes::from(vec![
410 Route {
411 indexes: vec![0, 1, 2]
412 },
413 Route {
414 indexes: vec![0, 2, 1]
415 }
416 ])
417 .routes,
418 route_vec_to_xx_hashset(vec![
419 Route {
420 indexes: vec![0, 1, 2]
421 },
422 Route {
423 indexes: vec![0, 2, 1]
424 }
425 ],)
426 )
427 }
428
429 #[test]
430 fn random_constructor() {
431 let n_objects = 3;
432 let population = Routes::random(3, n_objects);
433 assert_eq!(population.routes.len(), 3);
434 for route in population.routes {
435 valid_permutation(&route.indexes, &(0..n_objects).collect::<Vec<usize>>());
436 }
437 }
438 #[test]
439 fn test_add_vec_routes() {
440 let current_routes = Routes::from(vec![Route::new(vec![1]), Route::new(vec![2])]);
441 let extended_routes =
442 current_routes.add_vec_route(vec![Route::new(vec![3]), Route::new(vec![4])]);
443
444 valid_permutation(
445 &vec![
446 Route::new(vec![1]),
447 Route::new(vec![2]),
448 Route::new(vec![3]),
449 Route::new(vec![4]),
450 ],
451 &extended_routes
452 .iter()
453 .map(|route| route.clone())
454 .collect::<Vec<Route>>(),
455 )
456 }
457 #[test]
458 fn test_combine_routes() {
459 let current_routes = Routes::from(vec![Route::new(vec![1]), Route::new(vec![2])]);
460 let other_routes = Routes::from(vec![Route::new(vec![3]), Route::new(vec![4])]);
461 let combined_routes = current_routes.combine_routes(other_routes);
462 valid_permutation(
463 &vec![
464 Route::new(vec![1]),
465 Route::new(vec![2]),
466 Route::new(vec![3]),
467 Route::new(vec![4]),
468 ],
469 &combined_routes
470 .iter()
471 .map(|route| route.clone())
472 .collect::<Vec<Route>>(),
473 )
474 }
475 #[test]
476 fn test_get_n_nodes() {
477 let routes_with_three_nodes =
478 Routes::from(vec![Route::new(vec![1, 2, 3]), Route::new(vec![4, 5, 6])]);
479 assert_eq!(routes_with_three_nodes.get_n_nodes(), 3);
480 }
481 #[test]
482 fn add_n_random_nodes() {
483 // Because there are only 6 possible routes with three nodes,
484 // when I add 6, there have to be 6 in total (e.g. five new ones
485 // were added).
486 let a_single_route = Routes::from(vec![Route::new(vec![0, 1, 2])]);
487 assert_eq!(a_single_route.add_n_random_nodes(6).iter().len(), 6);
488 }
489 #[test]
490 fn test_fitness() {
491 let distance_mat = test_dist_mat();
492 let population = Routes::from(vec![Route::new(vec![1, 2, 0]), Route::new(vec![1, 0])]);
493 let fitnesses = population.fitnesses(&distance_mat);
494 assert_eq!(fitnesses.len(), 2);
495
496 for element in vec![
497 (-6.0, &Route::new(vec![1, 2, 0])),
498 (-2.0, &Route::new(vec![1, 0])),
499 ] {
500 assert!(fitnesses.contains(&element))
501 }
502 }
503 mod test_get_n_fittest {
504 use super::*;
505 #[test]
506 fn n_0_fittest() {
507 let distance_mat = test_dist_mat();
508 let routes = Routes::from(vec![
509 Route::new(vec![1, 2, 0]),
510 Route::new(vec![1, 0]),
511 Route::new(vec![2, 0]),
512 ]);
513 assert_eq!(routes.get_n_fittest(0, &distance_mat), vec![],)
514 }
515 #[test]
516 fn n_1_fittest() {
517 let distance_mat = test_dist_mat();
518 let routes = Routes::from(vec![
519 Route::new(vec![1, 2, 0]),
520 Route::new(vec![1, 0]),
521 Route::new(vec![2, 0]),
522 ]);
523 assert_eq!(
524 routes.get_n_fittest(1, &distance_mat),
525 vec![Route::new(vec![1, 0]),],
526 )
527 }
528 #[test]
529 fn n_2_fittest() {
530 let distance_mat = test_dist_mat();
531 let routes = Routes::from(vec![
532 Route::new(vec![1, 2, 0]),
533 Route::new(vec![1, 0]),
534 Route::new(vec![2, 0]),
535 ]);
536 assert_eq!(
537 routes.get_n_fittest(2, &distance_mat),
538 vec![Route::new(vec![1, 0]), Route::new(vec![2, 0]),],
539 )
540 }
541 #[test]
542 fn n_3_fittest() {
543 let distance_mat = test_dist_mat();
544 let routes = Routes::from(vec![
545 Route::new(vec![1, 2, 0]),
546 Route::new(vec![1, 0]),
547 Route::new(vec![2, 0]),
548 ]);
549 assert_eq!(
550 routes.get_n_fittest(3, &distance_mat),
551 vec![
552 Route::new(vec![1, 0]),
553 Route::new(vec![2, 0]),
554 Route::new(vec![1, 2, 0]),
555 ],
556 )
557 }
558 }
559 mod test_fittest_routes {
560 use super::*;
561 #[test]
562 fn n_0_fittest() {
563 let distance_mat = test_dist_mat();
564 let routes = Routes::from(vec![
565 Route::new(vec![1, 2, 0]),
566 Route::new(vec![1, 0]),
567 Route::new(vec![2, 0]),
568 ]);
569 assert_eq!(
570 routes.get_fittest_population(0, &distance_mat),
571 Routes {
572 routes: HashSet::with_hasher(xx::Hash64),
573 },
574 )
575 }
576 #[test]
577 fn n_1_fittest() {
578 let distance_mat = test_dist_mat();
579 let routes = Routes::from(vec![
580 Route::new(vec![1, 2, 0]),
581 Route::new(vec![1, 0]),
582 Route::new(vec![2, 0]),
583 ]);
584 assert_eq!(
585 routes.get_fittest_population(1, &distance_mat),
586 Routes {
587 routes: route_vec_to_xx_hashset(vec![Route::new(vec![1, 0]),],),
588 },
589 )
590 }
591 #[test]
592 fn n_2_fittest() {
593 let distance_mat = test_dist_mat();
594 let routes = Routes::from(vec![
595 Route::new(vec![1, 2, 0]),
596 Route::new(vec![1, 0]),
597 Route::new(vec![2, 0]),
598 ]);
599 assert_eq!(
600 routes.get_fittest_population(2, &distance_mat),
601 Routes {
602 routes: route_vec_to_xx_hashset(vec![
603 Route::new(vec![1, 0]),
604 Route::new(vec![2, 0])
605 ],),
606 },
607 )
608 }
609 #[test]
610 fn n_3_fittest() {
611 let distance_mat = test_dist_mat();
612 let routes = Routes::from(vec![
613 Route::new(vec![1, 2, 0]),
614 Route::new(vec![1, 0]),
615 Route::new(vec![2, 0]),
616 ]);
617 assert_eq!(
618 routes.get_fittest_population(3, &distance_mat),
619 Routes {
620 routes: route_vec_to_xx_hashset(vec![
621 Route::new(vec![1, 0]),
622 Route::new(vec![2, 0]),
623 Route::new(vec![1, 2, 0]),
624 ],),
625 },
626 )
627 }
628 }
629 mod test_evolve {
630 use super::*;
631 use crate::test_utils::{test_dist_mat, valid_permutation};
632 #[test]
633 fn simple_test() {
634 let distance_mat = test_dist_mat();
635 let routes = Routes::from(vec![
636 Route::new(vec![1, 2, 0]),
637 Route::new(vec![1, 0, 2]),
638 Route::new(vec![2, 1, 0]),
639 ]);
640
641 // Test at least three members after evolving.
642 // Test maximum fitness can never decrease.
643 let past_max_fitness = routes.get_n_fittest(1, &distance_mat)[0].fitness(&distance_mat);
644 let new_routes = routes.evolve(0.5).evolve(0.5);
645
646 assert!(
647 routes.get_n_fittest(1, &distance_mat)[0].fitness(&distance_mat)
648 <= past_max_fitness
649 );
650 assert!(new_routes.routes.len() >= 3);
651 for route in new_routes.routes {
652 valid_permutation(&vec![0, 1, 2], &route.indexes);
653 }
654 }
655 }
656 #[test]
657 fn test() {
658 let mut set = HashSet::with_capacity_and_hasher(1000, xx::Hash64);
659 set.insert(Route::new(vec![1, 2, 3]));
660 }
661}