nsga is an opinionated implementation of the NSGA-II (Non-dominated Sorting Genetic Algorithm), a multi-objective genetic optimization algorithm.
The focus for this implementation is on practical applicability, not necessarily just for optimizing pure mathematical functions.
Let's define an example problem:
Given an array of integers and a value, find indices of the array elements
that sum up to the given value.
For example, given an array:
rust
let a = vec![1, 5, 8, 0, 6, 4];
and a value of 19, the solution could be:
rust
vec![1, 0, 1, 0, 1, 1]; // 1 + 8 + 6 + 4 = 19
or
rust
vec![0, 1, 1, 0, 1, 0]; // 5 + 8 + 6 = 19
Of course, for such a small input we wouldn't need a fancy optimizer, but when dealing with thousands or millions of elements, the task becomes somewhat challenging.
The problem is represented by an implementation of the Solution trait.
Let's define a base structure for our solution candidate:
```rust
struct Candidate {
indices: Vec
Since the solution to our problem is an array of indices, we can simply have
a Vec<isize> in our struct.
Mutation is an operation that changes the solution candidate. It is a way for the system to add diversity and escape local optima. Not unlike the role mutation plays in the evolution of the real biological systems.
Mutation is heavily problem-dependent and in our case we're just going to flip an index from 0 to 1 and vice versa with a certain probability.
```rust fn mutate(&mut self) { let mut rng = thread_rng();
for i in &mut self.indices { if rng.genratio(MUTATIONODDS.0, MUTATION_ODDS.1) { *i = if *i == 0 { 1 } else { 0 } } } } ```
Crossover is an operation that takes two parent candidates and mixes their "genes". In our implementation, we're going to split both parents in half and swap corresponding parts. I.e. given two parents:
rust
let a = vec![1, 1, 1, 1, 1, 1];
let b = vec![0, 0, 0, 0, 0, 0];
after the crossover these would look like:
rust
vec![1, 1, 1, 0, 0, 0];
vec![0, 0, 0, 1, 1, 1];
```rust
fn crossover(&mut self, other: &mut Self) { let mut a = &mut self.indices; let mut b = &mut other.indices;
// Use a for the longer vector:
if b.len() > a.len() {
a = &mut other.indices;
b = &mut self.indices;
}
let amid = a.len() / 2; let bmid = b.len() / 2;
let bback = &mut b[bmid..]; let aback = &mut a[amid..][..b_back.len()];
aback.swapwithslice(bback);
let alen = amid + aback.len(); b.extend(a.drain(alen..)); } ```
In order to guide the optimizer, we need to implement the Objective trait.
The only mandatory method is Objective::value which takes a solution
candidate and returns its fitness value. The lower this value the closer
a particular solution is to the ideal solution.
For our task we'd implement something like the following:
```rust fn value(&self, candidate: &Candidate) -> f64 { let res: f64 = candidate .indices .iter() .enumerate() .map(|(i, rec)| if *rec == 1 { self.items[i] } else { 0. }) .sum();
let diff = (self.goal - res).abs(); if diff < 0. { f64::MAX } else { diff } } ```
Basically, it computes the sum of all the values for which the the index bit was set in the solution and then computes the difference between the sum and the target value, we're looking for.
The closer the sum of the current solution is to the value we're looking for, the smaller will be the difference, and this is exactly what we need, since the optimizer always tries to find the function minimum.
When in a particular objective the target value is known, the optimization process can be made significantly faster by not having to compute all the iteration steps.
For example, in our case, we know exactly the value we're looking for so we can terminate the search the moment we're close enough to the desired value.
rust
fn good_enough(&self, val: f64) -> bool {
val <= self.toleration
}
By tweaking the self.toleration value we can make the search as
precise as we need.
There's a set of additional meta-parameters we'd need to provide to the
optimizer. We do this by implementing a Meta trait.
Population size is the size of the internal pool of candidates optimizer uses.
The default value is 20 and in most cases, it can be left untouched.
This method should return a probability of applying a crossover operation. It should generally be relatively high, around 50% or so.
This method should return a probability of applying a mutation operation. It should generally be smaller than the crossover value, around 20-30% or so.
A method to return a random solution candidate. In our case, we'll just return a vector of zeroes for the indices.
```rust
fn randomsolution(&mut self) -> Candidate {
let indices: Vec
Candidate { indices } } ```
This method returns a vector of objectives to use in the optimization.
In our case, it will be an instance of our SumObjective one:
rust
fn objectives(&self) -> &Vec<Box<dyn Objective<Candidate>>> {
vec![
Box::new(SumObjective {
goal: 19.,
items: vec![1, 5, 8, 0, 6, 4],
toleration: 0.0,
}),
]
}
This method returns an optional vector of constraints to use in the optimization. We won't need constraints for our little example.
Now, being able to optimize for one objective is great, but NSGA-II is a
multi-objective optimization algorithm, meaning that it can optimize
for many objectives at the same time. And some of those may even conflict
with each other! The details are outside the scope of this tutorial,
feel free to read more about it on
Wikipedia,
if you'd like.
Remember, with our initial test vector:
rust
let a = vec![1, 5, 8, 0, 6, 4];
we identified two solutions with a sum of 19:
rust
let s1 = vec![1, 0, 1, 0, 1, 1]; // 1 + 8 + 6 + 4 = 19
let s2 = vec![0, 1, 1, 0, 1, 0]; // 5 + 8 + 6 = 19
Now, let's say in addition to finding a required sum, we'd also want
to find the one with the smallest number of summands.
So, for s1 above there would be four summands: 1, 8, 6 and 4,
while s2 only has three: 5, 8 and 6, so we'd want our optimization
to find the latter one.
All we need for this is to implement another objective, let's call it
OnesObjective, because it's simply going to return the number of ones (set bits)
in the solution:
```rust pub struct OnesObjective {}
impl Objective
And then add to our objectives method:
```rust
fn objectives(&self) -> &Vec
That's it!
For complete-code examples take a look at the crate tests: