Genetic Algorithms

Published March 30, 2018

This week I recreated Roger Johansson’s Evolving Mona Lisa, which attempts to ‘evolve’ an image (the Mona Lisa) from a number of randomly-placed and randomly-colored triangles. In particular, this project does the following:

* Setup a random DNA string  (application start)

1. Copy the current DNA sequence and mutate it slightly
2. Use the new DNA to render polygons onto a canvas
3. Compare the canvas to the source image
4. If the new painting looks more like the source image than the previous
    painting did, then overwrite the current DNA with the new DNA
5. Repeat from 1

The full code for my version is here and you can see it (slowly) recreate Vermeer’s Girl with a Pearl Earring here.

DNA Encoding:

Building off of this rubric from Johansson’s website, and working in javascript, I began by choosing how to encode this DNA. Because I wanted the option to later expand this project to use larger polygons (or even to include polygons with random # of vertices as part of the mutation function), I wrote the DNA as a JSON blob with an array for points. It looked something like this:

// create DNA for "parent"
let numPolygons = 50; // number of polygons in each DNA sequence
let polyDimensions = 4; // number of vertices per polygons

for (let i = 0; i < numPolygons; i++) {
  let poly = {
    points: [],
    col: color(floor(random(255)), floor(random(255)), floor(random(255)), newPolyAlpha)
  };
  for (let i = 0; i < polyDimensions; i++) {
    poly.points.push({
      x: floor(random(width)),
      y: floor(random(height))
    })
  };
  parent.push(poly);
}

Fitness:

The fitness function iterates through every pixel in the source image and every corresponding pixel in the canvas and compares the two. It adds up the difference in red, green, blue and alpha values between the two images and this becomes that DNA strand’s fitness score. It then compares this score to the previous best score and uses the best one as the next frame’s ‘parent.’

Mutation:

The mutation function proved to be more complex than the fitness function for this script. My primary question was (and still is) at what level to implement mutation for the best results. In my mind there are a couple of ways to implement mutations in the reproduction algorithm. These are:

  • Mutate per polygon: a ‘mutated’ polygon would be replaced by an entirely new randomly generated polygon,

  • Mutate per vertex: a ‘mutated’ vertex would be replaced by an entirely new randomly generated vertex,

  • Mutate per vertex per axis: a ‘mutation’ would occur on a per-axis basis (i.e. a vertex of a polygon could have either x or y or both values mutated)

In my version, I am mutating per vertex, with an extra possible mutation per polygon for the color. Because the mutation can happen in any of N number of places in each polygon (corresponding to the number of vertices), I’ve made the mutation rate quite low (0.1 %).

Results:

Evolving a black square
After 1122 successful mutations


Evolving Vermeer's Girl with a Pearl Earring
Girl with a Pearl Earring after 5,266 successful mutations / 1,989,200 total mutations

Evolving a sphere by comparing each random point distance from origin (0,0,0) point with the radius of a sphere
Evolving a sphere with mouse interaction!

Optimization

I made a few different attempts to ‘optimize’ my program, all of them unsuccessful :)!

  • Draw each new DNA sequence (step #2 above) to an offscreen graphics buffer. I figured a certain amount of render time might be dedicated to drawing to the screen (as opposed to figuring out what to draw), so drew all the new DNA tests to an offscreen buffer (using P5’s built-in createGraphics() method), only drawing every 10th successful generation to the actual canvas. This seemed not to make a difference, so maybe the render time is identical…

  • Loop through several DNA tests (steps #2-4 above) each frame. I tried this in case the requestAnimationFrame() javascript method on which p5’s draw() loop is built might be time-limited AKA have a desired maximum framerate (ie. 80 or 90 fps) which could be circumvented by running a loop inside draw(). I first ran one-test-per-frame and reached around 80 fps on my brother’s gaming computer, then ran 100-tests-per-frame and reached 0.8 fps. So, no real difference in number of tests!