-
Notifications
You must be signed in to change notification settings - Fork 0
/
novelty_search.rs
98 lines (86 loc) · 3.04 KB
/
novelty_search.rs
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
use std::collections::HashSet;
use rand::{distributions::Uniform, prelude::Distribution, rngs::StdRng};
use crate::{
lcell::LCell,
universe::{self, Universe},
};
pub fn novelty_search(
universe_size: usize,
seed_size: usize,
generations: usize,
n_simulation_steps: usize,
rng: &mut StdRng,
) -> Vec<Vec<Vec<LCell>>> {
fn interesting(u: &Universe) -> bool {
universe::count_alive_cells(u) > 20 && universe::measure_symmetry(u) > 10
}
let n_parents = 4;
let n_offspring = 6;
let n_mutations = 1;
let k_nearest_neighbors = 4;
let mut discoveries = Vec::new();
// we use a hashset as the archive, this gets the density wrong but
// accelerates the search; since the "behavioural" space is anyway large,
// the error in the estimate should not be too relevant
let mut archive = HashSet::new();
let mut parents = vec![
Individual {
cells: vec![vec![LCell::Dead; seed_size]; seed_size],
novelty: usize::MIN
};
n_parents
];
let between = Uniform::from(0..parents.len());
for _ in 0..generations {
let mut offspring = Vec::with_capacity(n_offspring);
for _ in 0..n_offspring {
// choose a random parent and mutate
let idx = between.sample(rng);
let cells = mutate(&parents[idx].cells, n_mutations, rng);
// compute final state of universe
let universe = Universe::new(universe_size);
let universe = universe::seed(&universe, &cells);
let universe = universe::simulate(&universe, n_simulation_steps);
if interesting(&universe) {
discoveries.push(cells.clone());
}
// compute novelty as total distance from k closest neighbors
let mut distances = archive
.iter()
.map(|u| universe::compute_distance(u, &universe))
.collect::<Vec<usize>>();
distances.sort_unstable();
let novelty = if distances.len() < k_nearest_neighbors {
usize::MIN
} else {
distances[..k_nearest_neighbors].iter().sum::<usize>()
};
offspring.push(Individual { cells, novelty });
archive.insert(universe);
}
// choose offspring with highest novelty
offspring.sort_by_key(|a| a.novelty);
offspring.reverse();
parents = offspring[..n_parents].to_vec();
}
discoveries
}
#[derive(Clone)]
struct Individual {
cells: Vec<Vec<LCell>>,
novelty: usize,
}
fn mutate(cells: &[Vec<LCell>], n_mutations: usize, rng: &mut StdRng) -> Vec<Vec<LCell>> {
let mut cells = cells.to_vec();
let n = cells.len();
let between = Uniform::from(0..n);
for _ in 0..n_mutations {
let row = between.sample(rng);
let col = between.sample(rng);
match cells[row][col] {
LCell::Alive => cells[row][col] = LCell::Dead,
LCell::Dead => cells[row][col] = LCell::Alive,
};
}
cells
}