ppiotrow / scalagen

Scala actors toolkit to solve problems in scalable way using genetic agorithms

scalagen

Scala actors toolkit to solve problems in generic and scalable way using genetic algorithms

User manual

The fastest way to understand library is to take a look at BackpackExample

To use library developer has to implement few things:

• custom genome class - it extends trait Genome,
• Procreator.recombine - crossover operator takes two custom genotype objects as argument and return new genotype object,
• Procreator.mutate - mutation operator takes one genotype and return its mutation,
• Evaluator.eval - objective function takes genotype as an argument and return its value,
• Godfather.initialGenomes - initial population generator should return collection of genotypes to start evolution with ( the better they are the faster good results may be obtained).

User can also manipulate algorithm's parameters. And these are:

• Controller.optimalPopulationSize - the size of population that Controller will try to reach and maintain,
• Controller.maxToKillOrCreate - the maximum number of phenotypes that controller will try to kill or create to be as close to optimalPopulationSize as possible and to replace as many phenotypes as possible, (it is clearly described in Controller.calculatePopulationChange code doc),
• Procreator.mutationProbability - probability of mutation in newly created genome,
• RandomKiller.randomKillRatio - determines the ratio of the number of random deaths to deaths,
• EndOfAlgorithm.maxTimeBetweenImprovement - timeout to stop the algorithm since last best result(default 30 seconds).

Actors

Library uses a few types of actors to model genetic algorithm. These actors are:

• Phenotype, it contains genotype,
• Godfather, holds references to population of Phenotypes.
• Evaluator, it implements the objective function so it can evaluate Phenotype value,
• Controller, it tries to keep the correct population size but also to replace effectively old phenotypes with new ones,
• EndOfAlgorithm, it makes decision when to stop algorithm. The Evaluator notify it every time when it finds the new best phenotype,
• Procreator, implements mutation and crossover operators so it can create new genotype from parents,
• DeathItself, kills specified Phenotype,
• RandomKiller, kills random phenotype from time to time.

Objective function

The objective function value can be minimized or maximized. This behavior is determined by two implementations from scalagen.population package:

• MaximizeValue,
• MinimizeValue. This traits can be mixed into implementations of Controller, EndOfAlgorithm and Evaluator actors.

Population updates

Controller chooses some number of phenotypes to be killed. From the rest of the population it selects pairs. They will procreate and have a child.

In package scalagen.population there are two traits with some example implementations:

• PopulationKilling, represents strategy of selecting phenotypes to be killed,
• PopulationReproduction, represents strategy of selecting parents pairs.

Compilation

Type sbt in project directory. Then type projects. You can see project list containing:

• *root
• scalagen-core
• scalagen-examples

Root is your current project and it is parent project for core and examples. Type compile to compile both of them.

You can switch to projects using command project {project-name}. In scalagen-core you can perform tests using test command. In scalagen-example you can type run to run examples.

Contribution

If you would like to contribute to scalagen, your help is very welcome. You may

• work on some existing issue,
• make up your own improvement,
• write some example using library.

Download

SBT

libraryDependencies += "com.github.scalagen" % "scalagen_2.11" % "0.4.0"

Gradle

compile 'com.github.scalagen:scalagen_2.11:0.4.0'

Maven

<groupId>com.github.scalagen</groupId>
<artifactId>scalagen_2.11</artifactId>
<version>0.4.0</version>

License

Copyright 2014 Przemek Piotrowski
Copyright 2014 Tomasz Rozbicki

Licensed under the Apache License, Version 2.0 (the "License");
you may not use this file except in compliance with the License.
You may obtain a copy of the License at

   http://www.apache.org/licenses/LICENSE-2.0

Unless required by applicable law or agreed to in writing, software
distributed under the License is distributed on an "AS IS" BASIS,
WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
See the License for the specific language governing permissions and
limitations under the License.

scalagen's Issues

create example backpack algorithm

Using our library one should implement sample algorithm

Documentation update

We should update documentation after main changes

Inform endOfAlgoriithm about best result

Some actor, probably controller or good father, should inform endOfAlgorithm about best result.

EndAlgorithmActor implementation

As per README:
EndAlgorithmActor, it makes decision when to stop algorithm and all the actors. It knows few of best genotypes with their born timestamps,

[prioryty low] add checkstyle

Add some checkstyle to sbt. For example to deal with unused imports

Controller actor implementation

As per README:
Controller, it tries to keep the correct number of Fenotypes by killing and procreation order. It should realize some sellection strategy.

Random might be bootleneck

Probably current Random is shared between threads. You should done some benchmark and repeat it after using
import scala.concurrent.forkjoin.ThreadLocalRandom.{current => Random}

Backpack example hangs

If i remove condition alue > 61 then program really its not hanging but calculating for 5 seconds and then go IDLE. After timeout it returns result. Im working at this but library is probably not stable

Deadletters in test and example

To investigate (sometimes the tests finish with this message):
[INFO] [05/25/2014 16:30:08.016] [RandomKillerIntegrationTestActorSystem-akka.actor.default-dispatcher-8] [akka://RandomKillerIntegrationTestActorSystem/user/$$v] Message [scalagen.message.Death$] from TestActor[akka://RandomKillerIntegrationTestActorSystem/user/$$z] to TestActor[akka://RandomKillerIntegrationTestActorSystem/user/$$v] was not delivered. [1] dead letters encountered. This logging can be turned off or adjusted with configuration settings 'akka.log-dead-letters' and 'akka.log-dead-letters-during-shutdown'.

upgrade akka 2.3.4 -> 2.3.5

Add sample PopulationKilling implementation

For example strategy "kill n of the worst"

DeathItself actor implementation

As per README:
DeathItself, kills specified Fenotype.

RandomKiller actor implementation

As per README:
RandomKiller, kills random fenotype TODO

MutationPropability

Mutation should be optional. I see it like this

procreate = {
val recombined = recombine(male, female)
if(Random.nextDouble < 0.04) mutate(recombined) else recombined
}

0.04 is given eg. by constructor

add timeout to procreator

Procreator might not get response from phenotypes

Improve typesafe

Why should I cast Genome to my custom genome to perform mutation and crossover?
Why i have to mix MinimizeValue or MaximizeValue few times in my code? There is a chance that one actor will try to minimize value and the other one to maximize.

Some ideas?

Configure integration tests

Integration tests should be moved to the src/it/scala dir.
More: http://www.scala-sbt.org/release/docs/Detailed-Topics/Testing#integration-tests

Unique parrents in RouletteWheel

RouletteWheel can produce parents (x, y) where x==y.

Its dangerous to just select y after x is removed, because we can get no element when.
*wheel has only one element
*we removed last element in wheel and then our random index points to place, where normally would be removed index

LICENSE.txt file

Decide what license to use and provide LICENSE.txt file. I would like to use Apache license which is well known to developers.

Add sample PopulationReproduction implementation

For example the best phenotype pairs with more phenotypes than second phenotyme etc

update of libraries

New version of akka is available.
Its not possible yet to migrate to scala 2.11 because of sbt lack of support

RandomKiller optional

In my opinion RandomKiller should be optional for algorithm.

I would see usage like
extends GoodFather with RandomKiller(0.01)

I think that section can be usefull
http://doc.akka.io/docs/akka/current/scala/actors.html#Extending_Actors_using_PartialFunction_chaining

Trait should also add context.watch on created phenotypes in some smart and elegant way