### 3 releases

0.1.2 | Feb 25, 2023 |
---|---|

0.1.1 | Jan 30, 2022 |

0.1.0 | Jan 30, 2022 |

#**578** in Algorithms

**MIT**license

40KB

762 lines

# nsga

*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.

# 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:

`let` a `=` `vec!``[``1``,` `5``,` `8``,` `0``,` `6``,` `4``]``;`

and a value of

, the solution could be:`19`

`vec!``[``1``,` `0``,` `1``,` `0``,` `1``,` `1``]``;` `//` 1 + 8 + 6 + 4 = 19

or

`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

trait.
Let's define a base structure for our solution candidate:`Solution`

`#``[``derive``(``Clone``,` Debug`)``]`
`struct` `Candidate` `{`
`indices``:` `Vec``<``isize``>`,
`}`

Since the solution to our problem is an array of indices, we can simply have
a

in our struct.`Vec``<``isize``>`

### Mutation

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.

`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 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:

`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:

`vec!``[``1``,` `1``,` `1``,` `0``,` `0``,` `0``]``;`
`vec!``[``0``,` `0``,` `0``,` `1``,` `1``,` `1``]``;`

`
``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

trait.
The only mandatory method is `Objective`

which takes a solution
candidate and returns its fitness value. The lower this value the closer
a particular solution is to the ideal solution.`Objective ::`value

For our task we'd implement something like the following:

`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.

`fn` `good_enough``(``&``self`, `val``:` `f64``)`` ``->` `bool` `{`
val `<=` `self``.`toleration
`}`

By tweaking the

value we can make the search as
precise as we need.`self``.`toleration

## Metadata

There's a set of additional meta-parameters we'd need to provide to the
optimizer. We do this by implementing a

trait.`Meta`

### Meta::population_size

Population size is the size of the internal pool of candidates optimizer uses.
The default value is

and in most cases, it can be left untouched.`20`

### 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.

`fn` `random_solution``(``&``mut` `self``)`` ``->` Candidate `{`
`let` indices`:` `Vec``<``isize``>` `=` `(``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

one:`SumObjective`

`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``,`
`}``)``,`
`]`
`}`

### 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

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.`NSGA``-``II`

Remember, with our initial test vector:

`let` a `=` `vec!``[``1``,` `5``,` `8``,` `0``,` `6``,` `4``]``;`

we identified two solutions with a sum of

:`19`

`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

above there would be four summands: `s1`

, `1`

, `8`

and `6`

,
while `4`

only has three: `s2`

, `5`

and `8`

, so we'd want our optimization
to find the latter one.`6`

All we need for this is to implement another objective, let's call it

, because it's simply going to return the number of ones (set bits)
in the solution:`OnesObjective`

`pub` `struct` `OnesObjective` `{``}`
`impl` `Objective``<`Candidate`>` `for`` ``OnesObjective` `{`
`fn` `value``(``&``self`, `candidate``:` `&`Candidate`)`` ``->` `f64` `{`
candidate`.`indices`.``iter``(``)``.``filter``(``|``i``|` `*``*`i `==` `1``)``.``count``(``)` `as` `f64`
`}`
`}`

And then add to our

method:`objectives`

`
``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``,`
`}``)``,`
`Box``::`new`(`OnesObjective`{``}``)``,`
`]`
`}`

That's it!

For complete-code examples take a look at the crate tests:

#### Dependencies

~320KB