# Being Creative

with

Genetic Algorithms and Typeclasses

Noel Markham (47 Degrees)

with

Genetic Algorithms and Typeclasses

Noel Markham (47 Degrees)

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

Ad-hoc polymorphism! *???*

Where to start?

From the `Arrays`

class:

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

The `Comparator`

type:

`int compare(T o1, T o2)`

Using our own type:

```
public class IntHolder {
private int i;
public IntHolder(int i) {
this.i = i;
}
public int getInt() {
return i;
}
}
```

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))
```

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
}
```

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)
```

```
// 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)
```

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]
```

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

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.

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]
```

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]
```

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

From Wikipedia:

a search heuristic that mimics the process of natural selection

`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`

We need a way to represent whatever we're generating

A binary string:

`type Chromosome = Vector[Boolean]`

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.

`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
```

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
```

With ScalaCheck of course!

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

Suggestion:

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

Suggestion:

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

Suggestion:

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

```
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?

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

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`

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

`11101000101010001`

`00010111001110001`

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

`1110100`**0101010001**

`0001011`**1001110001**

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

`1110100`**1001110001**

`0001011`**0101010001**

And then throw the chromosome from the original population away.

`11101001001110001`

And then throw the chromosome from the original population away.

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

```
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)

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

`1000101000100011111`

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

`100`**0**101000**1**000111**1**1

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

`100`**1**101000**0**000111**0**1

Should be straightforward to test

```
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 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
}
}
}
```

Population size of 30, for 1000 iterations of the algorithm

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`

?

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

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

Lets just compare with an image that already exists!

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!

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

Population size 30, 1000 iterations

Population size 30, 2000 iterations

Population size 30, 3000 iterations

Population size 30, 4000 iterations

Population size 30, 5000 iterations

Population size 30, 5700 iterations...

... and three full days of computation!!

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

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

A game playing bot?

Can you think of any?

More information