created_at2022-01-30 04:27:10.129002
updated_at2023-02-25 04:48:21.964083
descriptionMulti-objective genetic optimization algorithm NSGA-II



# nsga *nsga* is an opinionated implementation of the [NSGA-II (Non-dominated Sorting Genetic Algorithm)](https://ieeexplore.ieee.org/abstract/document/996017), a multi-objective genetic optimization algorithm. The focus for this implementation is on practical applicability, not necessarily just for optimizing pure mathematical functions. # Example 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. ## Solution candidate The problem is represented by an implementation of the `Solution` trait. Let's define a base structure for our solution candidate: ```rust #[derive(Clone, Debug)] struct Candidate { indices: Vec, } ``` Since the solution to our problem is an array of indices, we can simply have a `Vec` in our struct. ### Mutation [Mutation](https://en.wikipedia.org/wiki/Mutation_(genetic_algorithm)) 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.gen_ratio(MUTATION_ODDS.0, MUTATION_ODDS.1) { *i = if *i == 0 { 1 } else { 0 } } } } ``` ### Crossover [Crossover](https://en.wikipedia.org/wiki/Crossover_(genetic_algorithm)) 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 a_mid = a.len() / 2; let b_mid = b.len() / 2; let b_back = &mut b[b_mid..]; let a_back = &mut a[a_mid..][..b_back.len()]; a_back.swap_with_slice(b_back); let a_len = a_mid + a_back.len(); b.extend(a.drain(a_len..)); } ``` ## Objective 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. ### Early termination 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. ## Metadata There's a set of additional meta-parameters we'd need to provide to the optimizer. We do this by implementing a `Meta` trait. ### Meta::population_size 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. ### Meta::crossover_odds This method should return a probability of applying a crossover operation. It should generally be relatively high, around 50% or so. ### Meta::mutation_odds 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. ### Meta::random_solution A method to return a random solution candidate. In our case, we'll just return a vector of zeroes for the indices. ```rust fn random_solution(&mut self) -> Candidate { let indices: Vec = (0..self.records_length).map(|_| 0).collect(); Candidate { indices } } ``` ### Meta::objectives 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>> { vec![ Box::new(SumObjective { goal: 19., items: vec![1, 5, 8, 0, 6, 4], toleration: 0.0, }), ] } ``` ### Meta::constraints This method returns an optional vector of constraints to use in the optimization. We won't need constraints for our little example. ## Multiple objectives 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](https://en.wikipedia.org/wiki/Multi-objective_optimization), 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 for OnesObjective { fn value(&self, candidate: &Candidate) -> f64 { candidate.indices.iter().filter(|i| **i == 1).count() as f64 } } ``` And then add to our `objectives` method: ```rust fn objectives(&self) -> &Vec>> { vec![ Box::new(SumObjective { goal: 19., items: vec![1, 5, 8, 0, 6, 4], toleration: 0.0, }), Box::new(OnesObjective{}), ] } ``` That's it! For complete-code examples take a look at the crate tests: * [test_sch](https://github.com/syhpoon/nsga/blob/master/src/test_sch.rs) * [tes_sum](https://github.com/syhpoon/nsga/blob/master/src/test_sum.rs)
Commit count: 0

cargo fmt