### 3 unstable releases

0.1.1 | Mar 6, 2023 |
---|---|

0.1.0 | Mar 2, 2023 |

0.0.0 | Feb 17, 2023 |

#**195** in Algorithms

**MIT**license

85KB

1.5K
SLoC

# Eviolite

Eviolite is a set of tools and algorithms for using evolutionary algorithms in
Rust. It is written in a performance-minded, minimal-copy style, and uses
rayon to parallelize the most
computationally intensive parts. It also includes a drop-in replacement for
rand's

that is fully
reproducible and can be seeded from an environment variable. This means that
if you get a run you like, you can share that seed with someone else alongside
your program and they will be guaranteed to get the same output you got.`thread_rng`

### Getting Started

Add the following to your

:`Cargo .toml`

`eviolite = "0.1"
`

Then continue reading for a simple example, or take a look at the docs if you're not the tutorial type.

## Example

Let's go step by step over a complete program that uses a genetic algorithm to find a polynomial that approximates the sine function. This program is nice and short, but nicely demonstrates the general workflow of using Eviolite.

First, we'll import everything we need from Eviolite:

`use` `eviolite``::``prelude``::``*``;`

Then import a few other things that'll be helpful:

`use` `ndarray``::`Array1`;`
`use` `ndarray_rand``::`RandomExt`;`
`use` `rand``::``distributions``::`Uniform`;`
`use` `std``::``f64``::``consts``::``FRAC_PI_2``;`

### Defining Our Solution Type

`#``[``derive``(``Clone``)``]`
`struct` `Polynomial``(``Array1``<``f64``>``)``;`

The elements of this array will represent the coefficients

, `a`

, `b`

, and
`c`

of the polynomial `d`

. Now let's define a method to
evaluate our polynomial for a given `a + bx + cx² + dx³`

`x`

:`impl` `Polynomial` `{`
`fn` `apply``(``&``self`, `x``:` `f64``)`` ``->` `f64` `{`
`self``.``0``[``0``]`
`+` `self``.``0``[``1``]` `*` x
`+` `self``.``0``[``2``]` `*` x`.``powi``(``2``)`
`+` `self``.``0``[``3``]` `*` x`.``powi``(``3``)`
`}`
`}`

Next, we'll create an array of test points. We can't evaluate how good our
approximation is at *every* point, since that would take forever, so we'll use
100 evenly spaced points between 0 and π/2. We'll wrap this in a

so it's globally accessible.`lazy_static`

`lazy_static``::`lazy_static`!` `{`
`static` `ref` `TEST_POINTS``:` `Array1``<``f64``>` `=` `Array1``::`range`(``0.``,` `FRAC_PI_2``,` `FRAC_PI_2` `/` `100.``)``;`
`}`

### Implementing `Solution`

`Solution`

Now we're ready to implement the

trait:`Solution`

`impl` `Solution ``for`` ``Polynomial` `{`

First, we define what type our fitness values will be. For now, we'll keep it
simple, and say that how good an approximation is can be represented as a
single

:`f64`

`type` `Fitness` `=` `f64``;`

Next, we need to define the four genetic algorithm primitives:
* generation*,

*,*

**evaluation***, and*

**crossover***.*

**mutation**#### Generation

Eviolite needs to be able to create a population of randomly generated
individuals as a starting point for the algorithm. We'll use the handy

method from
ndarray-rand
to generate four random `random_using`

s between 0 and 1 with Eviolite's reproducible RNG.
These numbers will represent the coefficients `f64`

, `a`

, `b`

, and `c`

in our
polynomial `d`

.`a + bx + cx² + dx³`

`fn` `generate``(``)`` ``->` Polynomial `{`
Polynomial`(``Array1``::`random_using`(``4``,` `Uniform``::`new_inclusive`(``0.``0``,` `1.``0``)``,` `&``mut` `thread_rng``(``)``)``)`
`}`

#### Evaluation

We need to be able to tell the algorithm how good a given polynomial is at
approximating

. We'll do this by evaluating our polynomial for every test
point `sin`

and taking the absolute difference between that value and `x`

,
then averaging all of those differences to get the mean error across all test
points.`sin``(`x`)`

`fn` `evaluate``(``&``self``)`` ``->` `f64` `{`
`-``TEST_POINTS``.``mapv``(`
`|``x``|` `(``self``.``apply``(`x`)` `-` x`.``sin``(``)``)``.``abs``(``)`
`)``.``mean``(``)``.``unwrap``(``)`
`}`

Genetic algorithms assume that a higher fitness value is better, so we stick a negative sign in front.

Activity:Think of other ways we could measure the fitness of these approximations!

#### Crossover

If you were to compare genetic algorithms to real-life selective breeding, this would be the breeding part. We need to mix together the coefficients of two polynomials so that they both get some information from the other while retaining some of their own. We'll just use a simple one-point crossover, which there's conveniently a built-in for:

`fn` `crossover``(``a``:` `&``mut` `Self`, `b``:` `&``mut` `Self``)`` ``{`
`crossover``::`one_point`(``&``mut` a`.``0``,` `&``mut` b`.``0``)``;`
`}`

#### Mutation

Just like in real-life evolution, this is where "new ideas" come from. We need to randomly modify a polynomial just a little bit. One way to do this is by adding some Gaussian noise to the coefficients. Fortunately, there's a built-in for that. We'll apply a 50% chance to mutate each coefficient, and add noise with a standard deviation of 0.1 to the ones that are chosen for mutation.

`fn` `mutate``(``&``mut` `self``)`` ``{`
`mutation``::`gaussian`(``&``mut` `self``.``0``,` `0.``5``,` `0.``1``)``;`
`}`

And that's it! We've implemented

, and that means Eviolite has
everything it needs to evolve a polynomial to approximate `Solution`

.
Now we can write our `sin``(`x`)`

function and actually get a result.`main``(``)`

### Running an Evolution

Let's create our

instance. We'll use the
`Evolution`
algorithm, with some somewhat arbitrarily chosen parameters. We'll pass it a

`(`μ`+`λ`)``Tournament`

selector, which will repeatedly choose 10 polynomials at random and pick the
best. We'll also create a
`BestN`

hall of fame with a size of 1, which will automatically track the best
polynomial that's been found so far. Finally, we'll completely delete the
population and generate a fresh one every 25,000 generations as a failsafe in
case the algorithm gets stuck. In `main``(``)`

:`let` evo`:` `Evolution``<`Polynomial, `_`, `_`, `(``)``>` `=` `Evolution``::`with_resets`(`
`alg``::``MuPlusLambda``::`new`(`
`//` population size (μ)
`1000``,`
`//` offspring size (λ)
`1000``,`
`//` crossover chance (cxpb)
`0.``5``,`
`//` mutation chance (mutpb)
`0.``2``,`
`//` selection operator
`select``::``Tournament``::`new`(``10``)`
`)``,`
`hof``::``BestN``::`new`(``1``)``,`
`25000`
`)``;`

Activity:Try playing around with these parameters to see how they affect the evolution!

Now we just have to run it! We'll have the evolution run until it finds a polynomial whose mean error across all the test points is less than 0.001. We'll also time it for good measure:

`let` start `=` `std``::``time``::``Instant``::`now`(``)``;`
`let` log `=` evo`.``run_until``(`
`|``gen``|` `-`gen`.`hall_of_fame`[``0``]``.``evaluate``(``)` `<` `0.``001`
`)``;`
`let` time `=` start`.``elapsed``(``)``;`

takes a closure that receives information about the current state of the run
and decides whether to stop it, so we just check if the best solution we've
seen has a mean error less than 0.001.`.``run_until``(``)`

Now, let's extract our shiny new less-than-0.001-average-error polynomial from the run log and print it to console:

`let` `(`best`,` `_``)` `=` log`.`hall_of_fame`[``0``]``.``clone``(``)``.``into_inner``(``)``;`
`println!``(``"`found in `{:.3}` secs: sin(x) ≈ `{:.3}` + `{:.3}`x + `{:.3}`x² + `{:.3}`x³`"``,`
time`.``as_secs_f64``(``)``,` best`.``0``[``0``]``,` best`.``0``[``1``]``,` best`.``0``[``2``]``,` best`.``0``[``3``]`
`)``;`

And that's everything! See

for the full code.`examples /approx_sin.rs`

When you compile and run this example (on release build - genetic algorithms are very computationally intensive!), after a moment you should get an output that looks a bit like this:

`found ``in` `3.``982` secs`:` `sin``(`x`)` ≈ `0.``001` `+` `1.``017`x `+` `-``0.``059`x² `+` `-``0.``118`x³

Activity:Set the environment variable`to`

EVIOLITE_SEED`and run the program again to get the exact same output as above! (Except the run time, of course.)`

1175913497836025702

The
Taylor series expansion
for

starts `sin``(`x`)`

, so it's a nice sanity check to see
that the coefficients roughly match 0, 1, 0, and -1/6.`x - (x³ / 3!) + ...`

#### Dependencies

~1.8–2.5MB

~47K SLoC