Evolutionary Algorithms on the JVM via Scala — a minimal introduction by Mikołaj Koziarkiewicz

Dig deeper into the world of machine learning and AI with Senior Software Engineer Mikołaj Koziarkiewicz and how it is worthwhile to consider other machine learning approaches. 

You will also be introduced to a basic overview of evolutionary algorithms via Scala.

Unless you’ve just woken up from a several-year cryostasis, you’re probably aware of the recent resurgence of machine learning and AI. This is yet another cycle of enthusiasm (historically interspersed with so-called Winters), and this one is fueled mostly by interest in recommendation systems and the advances — in algorithmics and supporting hardware — of neural networks for machine vision and other purposes.

It is therefore worthwhile to also consider other machine learning approaches, not as significantly blessed by the current hype. So, let’s talk about evolution.

Darwin in the machine

The generic proper term for any sort of heuristic approach that is inspired and/or mimics the process of evolution is Evolutionary Algorithms. As you can see from this list, there are quite a few categories, depending on what you choose to mimic and how you go about doing that.

Our primary area of interest for this blog entry will be genetic algorithms. These, are, the ones most people who have any idea about EA are probably aware of, potentially excepting genetic programming.

First of all, let’s say you have an optimization problem 'X'.

When setting up a solution using genetic algorithms, you first encode your problem 'X' into a set of genes, that are nothing more than simple values (integers, strings etc.), possibly with some constraints. This genetic encoding will be used to randomly generate a population of individuals, each possessing their own combination of gene values — that is, their genotypes.

In other words, each genotype represents a solution to the problem 'X'. That solution is a phenotype of the individual. For a biological comparison, your genotype is whatever DNA and other auxiliary genetic structures float about your body, and your phenotype comprises your body as a whole.

Other than a genotype and phenotype, you also need a fitness function. This function accepts a phenotype and returns a numerical score of how well the phenotype solves problem 'X'. This score is used to select the “best” genotypes as eligible to be included into the following generation of the population.

The next generation is then created. In the simplest approach, it’s done by passing through the selected individuals and filling up the remainder of the population quota randomly. However, usually instead of that, some genetic operators are applied to the selected genotypes, boiling down mostly to these categories:

• recombination operators — “mix up” selected genotypes to create new ones — emulated sexual reproduction,
• mutation operations — randomly change one or more values of a genotype. The primary benefit here is to escape local optima of the solution space.

The evolutionary run then repeats itself until a termination condition is found, such as:

• reaching some value threshold of the fitness function,
• going through a set number of generations,
• subsequent generations not bringing enough improvement over the previous ones,
• and so on.

You end up with one or more “optimal” genotypes, expressing phenotypes that are the best solutions to your problem that the genetic algorithm can find.

Digression: a little bit of context

(this section is completely optional, only providing some flavor to the article)​

For many years, when running evolutionary algorithms on the JVM, the JGAP project was the way to go. In fact, the original prototype of 'helisa' used JGAP as a backend, while being developed for an investigation into the subsequent series of blogs posts about traffic analisis(which are eventually coming, I swear!).

However, JGAP seems to be abandoned currently, even missing the doc page for over a year. Moreover, it is a very…​ venerable project, up to the point of using “raw” Lists instead of generic ones, etc.

Fortunately, a new contender appeared in the meantime. It’s called jenetics, and it already is both quite featureful and growing in popularity. Therefore, the current incarnation of 'helisa' uses jenetics as a backend.

Using GAs in Scala

For this blog, we are going to be using the jenetics library, with the slight caveat that it does not have a (stable) Scala API. However, a frontend called 'helisa' has been written by Yours Truly that allows for exactly that.

Encoding our problem

Let’s say we need to guess a number:

• between 0 and 100,
• that we know is even,

our genotype, phenotype and our fitness function could look like this:

import com.softwaremill.helisa._ // <1>

val genotype =
  () => genotypes.uniform(chromosomes.int(0, 100)) // <2>

case class Guess(num: Int) // <3>

def fitness(toGuess: Int) =
  (guess: Guess) => 1.0 / (guess.num - toGuess).abs // <4>

1. Importing all the magic in the API.
2. A producer of genotypes, each genotype expresses a single gene (which is the possible value of the “guess”).
3. The representation of a solution to the problem (the phenotype).
4. The fitness function — the closer to the target number, the higher the fitness score.

val Number = 72

val evolver =
  Evolver(fitness(Number), genotype) // <1>
    .populationSize(10)
    .phenotypeValidator(_.num % 2 == 0) // <2>
    .build()

val run = evolver.iterator() // <1>

val resultAfter2 = run
  .drop(2)
  .next()

println(resultAfter2.bestPhenotype)

val resultAfter100 = run
  .drop(97)
  .next()

println(resultAfter100.bestPhenotype)

Some(Guess(80))
Some(Guess(72))