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
89
90
91
92
93
94
95
96
97
98
99
100
|
#![allow(dead_code)]
use rand::{thread_rng, Rng, rngs::ThreadRng, seq::SliceRandom};
use crate::gene::Gene;
use crate::chromosome::Chromosome;
#[derive(Debug)]
pub struct Generation {
pub t: usize,
pub map: Vec<Gene>,
pub population: Vec<Chromosome>,
}
impl Generation {
const POPULATION_SIZE: usize = 4000;
const MAX_GENERATIONS: usize = 200;
const TOURNAMENT_SIZE: usize = 5;
fn new_population(map: &Vec<Gene>) -> Vec<Chromosome> {
let mut rng = thread_rng();
let mut perm: Vec<usize> = (0..map.len()).collect();
let mut ret: Vec<Chromosome> = Vec::new();
for _ in 0..Self::POPULATION_SIZE {
perm.shuffle(&mut rng);
ret.push(Chromosome::new(perm.clone(), map));
}
ret
}
pub fn new_from_map(map: Vec<Gene>) -> Generation {
Generation {
t: 0,
population: Self::new_population(&map),
map,
}
}
pub fn new_from_random(cities: usize) -> Generation {
let mut rng = thread_rng();
let map = (0..cities)
.map(|_| Gene {
x: rng.gen::<f64>() * 10.0_f64.powi(rng.gen_range(0..5)),
y: rng.gen::<f64>() * 10.0_f64.powi(rng.gen_range(0..5)),
name: String::new() })
.collect();
Self::new_from_map(map)
}
pub fn select(&self, rng: &mut ThreadRng) -> usize {
let mut tournament: Vec<usize> = Vec::new();
for _ in 0..Self::TOURNAMENT_SIZE {
tournament.push(rng.gen_range(0..self.population.len()));
}
tournament
.into_iter()
.min_by(|a, b| self.population[*a].fitness.partial_cmp(&self.population[*b].fitness).unwrap())
.unwrap()
}
pub fn selection_crossover(&mut self) {
let mut rng = thread_rng();
let mut new_generation: Vec<Chromosome> = Vec::new();
while new_generation.len() < self.population.len() {
let parent1 = self.select(&mut rng);
let parent2 = self.select(&mut rng);
if parent1 == parent2 { continue; }
let mut children = self.population[parent1].crossover_with(&self.population[parent2], &self.map);
new_generation.append(&mut children);
}
self.population = new_generation;
}
pub fn mutate(&mut self) {
for p in &mut self.population {
p.mutate(&self.map);
}
}
pub fn next_generation(mut self) -> Generation {
self.t += 1;
self
}
pub fn terminated(&self) -> bool {
self.t == Self::MAX_GENERATIONS || self.population[1..].iter().all(|x| *x == self.population[0])
}
pub fn best_fitness(&self) -> f64 {
self.population
.iter()
.map(|x| x.fitness)
.min_by(|a, b| a.partial_cmp(b).unwrap())
.unwrap()
}
}
|
