Evvo

Evvo is the Scala framework for distributed multi-objective evolutionary computing.

Evvo supports:

• Distributed evolutionary computing on heterogenous networks
• User-defined problem and solution types
• Sane, but overridable, defaults, almost everywhere
• Built-in problem types for common solution type representations, e.x. bitstrings
• (planned) Real-time visualization of the evolutionary process
• (planned) The ability for users to dynamically add solutions and contraints to the population

NOTE: This code is provided as a public beta

Evvo is in beta. The API is not stable, and is guaranteed to change in the future. This is made clear by the version being v0.*.*. Once the major version is 1, the API will be stable. Do not use this code in production.

Here's an example showing how simple it is to set up and solve a basic problem (on one machine) using Evvo. Let's say we want to maximize the number of ones in a Bitstring. To represent this objective, we'll need to write an Objective (who would have guessed?). Then we can use Evvo to search for Bitstrings that satisfy the Objective. After running for a second, we'll print the current pareto frontier.

import io.evvo.agent.defaults.{Bitstring, Bitflipper, BitstringGenerator, DeleteDominated}
import io.evvo.island.{EvvoIsland, LocalIslandManager, StopAfter}
import io.evvo.island.population.{Maximize(), Objective}
import scala.concurrent.duration._

object Maximize()1Bits extends Objective[Bitstring]("1Bits", Maximize()) {
  override protected def objective(sol: Bitstring): Double = {
    sol.count(identity) // Bitstrings are represented as Seq[Boolean], count `true`s
  }
}


val islandBuilder = EvvoIsland.builder[Bitstring]()
  .addCreator(BitstringGenerator(length=16))
  .addModifier(Bitflipper())
  .addDeletor(DeleteDominated[Bitstring]())
  .addObjective(Maximize()1Bits)

val islandManager = new LocalIslandManager(numIslands = 1, islandBuilder)
islandManager.runBlocking(StopAfter(1.second))

print(islandManager.currentParetoFrontier())

This will run three asynchronous agents locally. BitstringGenerator creates Bitstrings of length 16 with randomly initialized bits, Bitflipper flips a random bit, and DeleteDominated will pick Bitstrings out of the generated solutions and delete the dominated ones. If you run this code on anything more powerful than a toaster, here's what will be printed:

ParetoFrontier(Map(1Bits -> 16.0))

This means that there was one solution on the pareto frontier, which scored 16.0 according to the objective named "1Bits". Since the generated Bitstrings only have 16 bits, the best possible score is 16.0 bits that are 1. Note that the pareto frontier doesn't print the actual solutions. The solutions are available within the ParetoFrontier class, but the toString method prints only the scores, because solutions to more complex problems are very large.

If our built-in Creators, Modifiers, and Deletors do not work for your problem, you can define your own as easily as we defined Maximize()1Bits.

If you want to jump directly into an example, check out the quickstart guide. It assumes some familiarity with evolutionary computing concepts, so you may need to cross reference the terminology and diagrams in this file while you are working through the example.

Terminology

Island: a population with multiple agents which can communicate with other islands for immigration and emigration.

Population: a mutable set of scored solutions from which the Pareto Frontier is calculated.

Pareto Frontier: a set of non-dominated solutions.

Dominated Solution: a dominated solution is worse in every regard (as captured by the objectives) than another solution, or worse in one regard and equal on others. For example, if there are three objective functions, each of which is to be maximized, then a solution scoring (3, 9, 4) would be dominated by one scoring (5, 11, 4), but not one scoring (5, 11, 3).

Objective: a single goal in the broader optimization problem.

Fitness: how strong a solution is as determined by the objectives.

Agent: not an Akka actor, but a part of an asynchronous evolutionary system. Each one runs on a separate thread.

Creator Agent: often shortened to "Creator", a Creator Agent generates a set of solutions and adds those solutions to the population.

Modifier Agent: often shortened to "Modifier", a Modifier Agent retrieves some number of solutions from the population, calls a function on that set of solutions to produce new solutions based on the input, and adds those new solutions to the population.

Mutator Agent: A type of ModifierAgent that applies a one-to-one mapping over a set of solutions, and adds all the results.

Crossover Agent: A type of ModifierAgent that applies a two-to-one function over a set of solutions, taking part of each input solution and combining them to produce new solutions.

Deletor Agent: often shortened to "Deletor", a Deletor Agent retrieves some number of solutions from the population and deletes the bad ones (for whatever definition of bad it's working with) from the population.

Emigration: an island sending solutions to another island.

Immigration: an island receiving solutions from another island.

The Model

Asycnchronous Evolutionary Computing

Asynchronous multi-agent evolutionary computing systems consist of a common population and multiple "evolutionary agents" that operate on the population. These agents, working in parallel, gradually push the overall fitness of a population upwards. (Assuming that the modifiers have a chance of improving fitness, and the deletors remove solutions that tend to be worse than average.) This system is easily parallelizable, as there is only one piece of shared memory - the set of solutions currently in the population. Much of the work (the work of computing new solutions, mutating existing solutions, and deciding which solutions to delete) can be distributed across multiple CPU cores, or even multiple machines.

This diagram illustrates each of the major components in Evvo and their roles:

+-------------------------------------------------------------------------+
|                                                                         |
| EvvoIsland                                                              |
|                                                                         |
+-------------------------------------------------------------------------+
|                                                                         |
|                                                   +------------------+  |
|  +---------------+       Generates new solutions  |                  |  |
|  |               |<-------------------------------| Creator Agent(s) |  |
|  | Population    |                                |                  |  |
|  |               |                                +------------------+  |
|  +---------------+                                                      |
|  |               | Reads some solutions           +------------------+  |<--+
|  |  - Objectives |------------------------------->|                  |  |   |
|  |               |                                | Modifier Agent(s)|  |   |
|  |  - Solutions  |<-------------------------------|                  |  |   | Immigration +
|  |               |         Derives new solutions  +------------------+  |   | Emigration
|  |               |                                                      |   |  Peer-to-peer gossip
|  |               | Reads some solutions           +------------------+  |   |  protocol for
|  |               |------------------------------->|                  |  |   |  sharing solutions
|  |               |                                | Deletor Agent(s) |  |   |  increases
|  |               |<-------------------------------|                  |  |   |  scalability without
|  |               |        Chooses some to delete  +------------------+  |   |  converging to local
|  +---------------+                                                      |   |  optima.
|                                                                         |   |
+-------------------------------------------------------------------------+   |  This is how Evvo
                                   ^                                          |  takes advantage of
                                   |  Immigration / Emigration                |  parallelism.
                                   v                                          |
+--------------------------------------------------------------------------+  |
|                                                                          |  |
| EvvoIsland     [Same contents as above, abbreviated for clarity]         |  |
|                                                                          |  |
+--------------------------------------------------------------------------+  |
                                   ^                                          |
                                   |  Immigration / Emigration                |
                                   v                                          |
+--------------------------------------------------------------------------+  |
|                                                                          |  |
| EvvoIsland     [Same contents as above, abbreviated for clarity]         |<-+
|                                                                          |
+--------------------------------------------------------------------------+

                                    .
                                    .
                                    .

                                and so on

Quickstart

The quickstart guide will walk you through writing and running a problem using Evvo. It solves a variant on the traveling salesperson problem with two objectives. If you're interested in seeing more of the developer API or understanding how to use Evvo, check this out next.

Downloads

Evvo v0.0.0 has been released! Keep in mind, consistent with the warning above: the APIs used here are not stable, and this code is not production-ready. But we hope you have fun experimenting with this release!

To get the dependency, use this for maven:

<dependency>
    <groupId>io.evvo</groupId>
    <artifactId>evvo_2.13</artifactId>
    <version>0.0.0</version>
</dependency>

Or this, for sbt

resolvers += Resolver.sonatypeRepo("releases")
libraryDependencies += "io.evvo" %% "evvo" % "0.0.0"

Parallelism

Setting up Servers

Evvo is dockerized. Follow the instructions to get started running your own network-parallel instance.

Serializability

Because we have to ship Islands to remote servers, Islands need to be serializable. All of the code provided by Evvo is serializable, but the creators, modifiers, deletors, and objectives that you provide must also be serializable for the Islands to serialize and deserialize correctly.

See the relevant section of the Scala cookbook on serialization. Note that serialized classes should also have referential transparency, that is, they should not reference variables from an external scope. A class defined within an object (or another class, or a code block) that references variablees defined in the outer object (or class, or code block) may cause serialization issues if those values are not present in the deserialization context. In general, extending Creator, Modifier, or DeletorFunction, with case classes, and ensuring that those case classes take all the data they need as arguments will be sufficient to ensure that there are no serialization issues.

If you use a LocalIslandManager to create LocalEvvoIslands, your data will still be serialized and deserialized, albeit on the same machine. This means that some of the most flagrant serialization exceptions can be caught early by testing with LocalIslandManager.

Contributing

See CONTRIBUTING.MD for information on how to contribute code to Evvo.