Being Creative
with
Genetic Algorithms and Typeclasses

Agenda

• Typeclass definition
• Introducing genetic algorithms
• Using typeclasses with genetic algorithms

What is a typeclass?

Ad-hoc polymorphism! ???

What is a typeclass?

Where to start?

Java!

What is a typeclass?

From the Arrays class:

static <T> void sort(T[] a, Comparator<? super T> c)

The Comparator type:

int compare(T o1, T o2)

What is a typeclass?

Using our own type:

public class IntHolder {

    private int i;

    public IntHolder(int i) {
	this.i = i;
    }

    public int getInt() {
	return i;
    }
}

What is a typeclass?

And our own Comparator

public class IntHolderComparator implements Comparator<IntHolder> {

    public int compare(IntHolder i1, IntHolder i2) {
	return i2.getInt() - i1.getInt();
    }
}

We can now sort collections using our own IntHolder type:

scala> val array = Array(new IntHolder(100), new IntHolder(50))
array: Array[IntHolder] = Array(IntHolder(100), IntHolder(50))

scala> Arrays.sort(array, new IntHolderComparator)

scala> array
res0: Array[IntHolder] = Array(IntHolder(50), IntHolder(100))

What is a typeclass?

And now in Scala

(This example lifted from Martin Odersky's paper: Type Classes as Objects and Implicits)

trait Ord[T] {
  def compare(a: T, b: T): Boolean
} 

An Ord instance for a specific type:

object intOrd extends Ord[Int] {
  def compare(a: Int, b: Int): Boolean = a <= b
}

What is a typeclass?

This instance can be used when necessary:

def sort[T](xs: List[T])
           (ord: Ord[T]): List[T] = ...

scala> sort(List(3, 2, 1))(intOrd)
res1: List[Int] = List(1, 2, 3)

What is a typeclass?

// implementation as before
implicit object intOrd extends Ord[Int] ...

// implementation as before
def sort[T](xs: List[T])
           (implicit ord: Ord[T]):List[T]

scala> sort[Int](List(4, 3, 6, 1, 7))
res4: List(1, 3, 4, 6, 7)

What is a typeclass?

No implicit in scope:

scala> sort[String](List("z", "y", "x", "w"))

<console>:28: error: 
    could not find implicit value
    for parameter ord: Ord[String]

What is a typeclass?

Generally, an implicit parameter which itself is parameterized:

def function[A](/* regular params */)(implicit t: Typeclass[A])

You will start to see this pattern everywhere.

View this as Enhancing a type, you're effectively giving new functionality to an already-created type.

One way to think of this is adding your own interface to sombody else's types

What is a typeclass?

Some other examples you may be familiar with:

Play JSON Reads

val nameReads: Reads[String] = (JsPath \ "name").read[Person]

Implemented as:

def fromJson [T] (json: JsValue)(implicit fjs: Reads[T]): T

Of course, a similar construct for Writes too.

What is a typeclass?

Some other examples you may be familiar with:

Plenty of examples in Typelevel Cats, such as:

def flatMap[U](f: V => WriterT[F, L, U])
              (implicit semigroupL: Semigroup[L]): WriterT[F, L, U]

What is a typeclass?

Some other examples you may be familiar with:

Plenty of examples in Typelevel Cats, such as:

def flatMap[U](f: V => WriterT[F, L, U])
              (implicit semigroupL: Semigroup[L]): WriterT[F, L, U]

Proposal:

I believe implementing a genetic algorithm is a great opportunity to use typeclasses

Genetic Algorithms

Definition

From Wikipedia:

a search heuristic that mimics the process of natural selection

Genetic Algorithms

What are we going to do

10 Randomly generate some stuff

20 Work out which of the stuff is the best

30 Use the best stuff to seed random generation of some more stuff

40 GOTO 20

Genetic Algorithms

Representing Stuff

We need a way to represent whatever we're generating

A binary string:

type Chromosome = Vector[Boolean]

Genetic Algorithms

The steps of the algorithm

Given a population of chromosomes

Give a weighting to each chromosome by applying a fitness function

Select a mutation pool randomly, respecting the weighting

Perform a random crossover on each chromosome in the mutation pool

Maybe twiddle some arbitrary number of bits

This is your new population.

The Fitness Function

def iterate[A](fitness: A => Long)(pop: Population): Population

The fitness will depend on what our algorithm is representing

We need to convert our chromosomes to real elements

trait Genetic[A] {
  def asA(c: Chromosome): A
}

Updating our iterate signature:

def iterate[A](fitness: A => Long)
              (pop: Population)
              (implicit g: Genetic[A]): Population

Creating The Mutation Pool

Randomly select from the population, giving a higher chance of selection to the fitter chromosomes

type RouletteWheel = Double => Option[Chromosome]

def rouletteWheel(mcs: Vector[(Chromosome, Long)]): RouletteWheel

Creating The Mutation Pool

How do we test this properly?

With ScalaCheck of course!

What is a property of this roulette wheel selection, given it is essentially a random selection?

Testing The Mutation Pool

Suggestion:

If a single chromosome takes over half of the wheel, then asking for the midpoint of the wheel will always return that chromosome

Testing The Mutation Pool

Suggestion:

If a single chromosome takes over half of the wheel, then asking for the midpoint of the wheel will always return that chromosome

Testing The Mutation Pool

Suggestion:

If a single chromosome takes over half of the wheel, then asking for the midpoint of the wheel will always return that chromosome

Testing The Mutation Pool

The Test

type MeasuredChromosome = (Chromosome, Long)

forAll(listOf(arbitrary[MeasuredChromosome]),
       arbitrary[Chromosome],
       listOf(arbitrary[MeasuredChromosome])) { (lefts, mid, rights) =>

  val middleScore = 1 + (lefts ::: rights).map(_._2).sum
  val midWithWeight = (mid, middleScore)
  val measuredPop = lefts.toVector ++ (midWithWeight +: rights.toVector)

  rouletteWheel(measuredPop)(0.5) ?= Some(mid)
}

[info] + Should give appropriate weightings: OK, passed 100 tests.

Can we think of more properties?

Testing The Mutation Pool

Aside: Depending on the property-generated values

In order to test our iterate function in its entirety, we need to plug in a way to generate a function to select from a mutation pool

We want this to be random in our full implementation, but deterministic in our tests

Testing The Mutation Pool

Aside: Depending on the property-generated values

We can change our iterate function to look like:

def iterate[A](
  fitness: A => Long,
  nextDouble: () => Double)
  (pop: Population)
  (implicit g: Genetic[A]): Population

In our tests we can generate streams of known doubles and plug them into a function with that signature

In our full implementation, we can simply plug in scala.util.Random.nextDouble

Next Step: Crossover

Take a chromosome from the mutation pool and a chromosome from the original population, pick a random point, and switch the bits

Next Step: Crossover

Take a chromosome from the mutation pool and a chromosome from the original population, pick a random point, and switch the bits

Next Step: Crossover

Take a chromosome from the mutation pool and a chromosome from the original population, pick a random point, and switch the bits

And then throw the chromosome from the original population away.

Next Step: Crossover

Take a chromosome from the mutation pool and a chromosome from the original population, pick a random point, and switch the bits

And then throw the chromosome from the original population away.

Testing Crossover

Again with ScalaCheck!

Property: Given paired fragments of a chromosome, we can construct a chromosome before and know how it should appear after.

Testing Crossover

Again with ScalaCheck!

forAll(posNum[Int], posNum[Int]) { (crossoverPoint, rightLength) =>
    def splitChromosome = for {
      left <- listOfN(crossoverPoint, arbitrary[Boolean])
      right <- listOfN(rightLength, arbitrary[Boolean])
    } yield (left, right)

    forAll(splitChromosome, splitChromosome) { case ((al, ar), (bl, br)) =>
      val a = (al ++ ar).toVector
      val b = (bl ++ br).toVector
      val expectedNew = (al ++ br).toVector

      crossover(a, b, crossoverPoint) ?= expectedNew
    }
  }
}

[info] + Crossover happens at the correct place: OK, passed 100 tests.

(And we'll add () => Int on to our iterate signature too)

Final Step:
Add random mutations

This may allow the algorithm to jump away from a local maximum, finding a more optimal solution

Simple: randomly select a few bits to flip

Final Step:
Add random mutations

This may allow the algorithm to jump away from a local maximum, finding a more optimal solution

Simple: randomly select a few bits to flip

Final Step:
Add random mutations

This may allow the algorithm to jump away from a local maximum, finding a more optimal solution

Simple: randomly select a few bits to flip

Should be straightforward to test

Ship It!

Our final iteration signature:

def iterate[A](
  fitness: A => Long,
  nextInt: () => Int,
  nextDouble: () => Double,
  nextBool: () => Boolean)
  (pop: Population)(implicit g: Genetic[A]): Population

As long as we have a Genetic typeclass for our type, we can use this function with an appropriate fitness function to run a genetic algorithm

The Genetic Algorithm In Action

Finding the optimal solution to a function

The Genetic Algorithm In Action

Finding the optimal solution to a function

The graph is our fitness function

We just need a way to describe the binary strings as numbers

implicit val geneticInt = new Genetic[Int] {
  def asA(c: Chromosome): Int = {
    c.foldLeft(0) { (i, bool) =>
      val s = i << 1
      if(bool) s + 1 else s
    }
  }
}

The Genetic Algorithm In Action

The results

The Genetic Algorithm In Action

The results

The Genetic Algorithm In Action

The results

Population size of 30, for 1000 iterations of the algorithm

Another Implementation

Modern art?

We can provide a Genetic typeclass for any type, and our algorithm will run with an appropriate fitness function.

How about creating a typeclass for java.awt.image.BufferedImage?

Another Implementation

The idea:

Use the Chromosome binary string to encode the (x,y) coordinates for 50 triangles, and also an RGB value for each triangle

Assuming a 1024x1024 picture:

• Each (x,y) will take 2 x 10 bits (60 bits per triangle)
• Each triangle will take 3 x 8 bits for its RGB value (24 bits)
• One more RGB value for the background colour (24 bits)

For 50 triangles, the length of the chromosome is 4224 bits

Another Implementation

What is the fitness function now?

What does it mean for one image to be "fitter" than another?

Lets just compare with an image that already exists!

Another Implementation

A poor man's image comparison

Given both images

For each pixel, subtract one RGB value from the other

Sum all of the values

The smaller the total, the fitter the generated image

Not the most efficient!

Another Implementation

Problem?

How do we use a fitness function to compare images when all we have to work with is BufferedImage => Long?

Currying of course!

BufferedImage => BufferedImage => Long

Simply set the base image when calling our iterate function

Another Implementation

The Results

Population size 30, 1000 iterations

Another Implementation

The Results

Population size 30, 2000 iterations

Another Implementation

The Results

Population size 30, 3000 iterations

Another Implementation

The Results

Population size 30, 4000 iterations

Another Implementation

The Results

Population size 30, 5000 iterations

Another Implementation

The Results

Population size 30, 5700 iterations...

... and three full days of computation!!

Conclusions

Genetic algorithms are not very efficient!!

Typeclasses provide a very neat interface to our algorithm: all of the non-specific code is nicely encapsulated

It's possible to use an inherently random tool like ScalaCheck to be deterministic in our testing

What Else?

Some other suggestions for a genetic algorithm:

Code: unit tests are our fitness function, use chromosome to generate a random AST

Racing cars

A game playing bot?

Can you think of any?

Thank You

More information

• The Mona Lisa in C#
• David Goldberg's Genetic Algorithms Book
• The code from this talk