2 releases
0.1.1 | Dec 29, 2022 |
---|---|
0.1.0 | Dec 29, 2022 |
#42 in #clustering
15KB
236 lines
Tabu
Provides local search functionality and related algorithms Currently provided search algorithms:
- tabu search
Currently provided derived applications:
- clustering
for detailed examples, see the included tests.
Running a tabu search
The following code runs a tabu search on a quadratic optimization problem from a list of initial state.
mod tabu;
use tabu::tabu_search;
use itertools::Itertools;
for initial_state in vec![(10, 10), (0, 0), (7, 0), (6, 5)] {
let step = 1;
let descendants = |&(x, y): &(i32, i32)| {
(-1..2)
.cartesian_product(-1..2)
.map(move |(dx, dy)| (x + dx * step, y + dy * step))
};
let cost = |&(x, y): &(i32, i32)| ((x - 5).pow(2) + (y - 5).pow(2)) as f64;
let max_iterations = 100;
let stopping_cost = 0.0;
let best = tabu_search(
initial_state,
descendants,
cost,
max_iterations,
Some(stopping_cost),
);
assert_eq!(best, (5, 5));
}
Running a clustering job
The following code clusters a set of integers into two clusters, with the cost being the diameter of the largest cluster.
mod tabu;
use tabu::{cluster_tabu, diameter};
let items = vec![1, 2, 3, 4, 5, 6, 7, 8, 9, 10];
let n_clusters = 2;
let max_iterations = 100;
let stopping_cost = None; // Stopping cost of None means that we'll only stop when we've exhausted all our options or we've hit the iteration limit
let mut clusters: Vec<Vec<i32>> = cluster_tabu(
items,
// The cost function - note that it's easy to write different cost functions here.
|clusters: &Vec<Vec<i32>>| {
clusters
.iter()
.map(|cluster| {
diameter(cluster, |x, y| (x - y).abs() as f64).unwrap_or(f64::NEG_INFINITY)
})
.fold(f64::NEG_INFINITY, f64::max)
},
n_clusters,
max_iterations,
stopping_cost,
)
.into_iter()
.map(|mut cluster| {
cluster.sort();
cluster
})
.collect();
clusters.sort();
assert_eq!(clusters.len(), n_clusters);
assert_eq!(clusters, vec![vec![1, 2, 3, 4, 5], vec![6, 7, 8, 9, 10]]);
Dependencies
~2.5MB
~37K SLoC