Category Archives: genetic programming

More procedurally rendered eggs in HTML5 canvas

The first Project Nightjar game was a big success, with 6 thousand players in the first few days – so we’ll have lots of visual perception data to get through! Today I’ve been doing a bit more work on the egg generator for the next citizen science camouflage game:

egglab3

I’ve made 24 new, more naturalistic base images than the abstract ones I was testing with before, and implemented the start of the genetic programming system – each block of 4×4 eggs here are children of a single randomly created parent, each child is created with a 1% mutation rate. The programs trees themselves are 6 levels deep, so a maximum of 64 binary composite operations.

All the genetic programming effort will happen in HTML5, thus neatly scaling the processing with the number of players, which is going to be important if this game proves as popular as the last – all the server has to do then is keep a record of the genotypes (the program trees) and their corresponding fitness.

One catch with this approach is the implementation of globalCompositeOperation in HTML5, the core of the image synthesis technique I’m using, is far from perfect across all browsers. Having the same genotype look different to different people would be a disaster, so I’m having to restrict the operations to the ones consistently supported – “source-over”,”source-atop”,”destination-over”,”destination-out”,”lighter” and “xor”.

Genetic programming egg patterns in HTML5 canvas

Part of the ‘Project Nightjar’ camouflage work I’m doing for the Sensory Ecology group at Exeter University is to design citizen science games we can build to do some research. One plan is to create lots of patterns in the browser that we can run perceptual models on for different predator animals, and use an online game to compare them with human perception.

The problem is that using per-pixel processing in order to generate the variety of patterns we need is hard to do quickly in Javascript, so I’m looking at using genetic programming to build image processing trees using the HTML5 canvas image composition modes. You can see it in action here, and the source is here. Here are some example eggs built from very simple test images blended together, these are just random programs, but a couple of them are pretty good:

random-eggs

A nice aspect of this is that it’s easy to artistically control the patterns by changing the starting images, for example much more naturalistic patterns would result from noisier, less geometric base images and more earthy colours. This way we can have different ‘themes’ for levels in a game, for example.

I’m using the scheme compiler I wrote for planet fluxus to do this, and building trees that look like this:


'("op"
  "lighter"
  ("op"
   "source-in"
   ("op"
    "source-out"
    ("terminal" (124 57 0 1) "stripe-6")
    ("terminal" (42 23 0 1) "dots-6"))
   ("op"
    "copy"
    ("terminal" (36 47 0 1) "stripe-7")
    ("terminal" (8 90 1.5705 1) "red")))
  ("terminal" (108 69 0 1) "green"))

Ops are the blend mode operations, and terminals are images, which include translation and scale (not currently used). The egg trees get drawn with the function below, which shows the curious hybrid mix of HTML5 canvas and Scheme I’m using these days (and some people may find offensive :) Next up is to actually do the genetic programming part, so mutating and doing crossover on the trees.


(define (draw-egg ctx x y program)
  (if (eq? (program-type program) "terminal")
      (begin
        (set! ctx.fillStyle
              (ctx.createPattern
               (find-image (terminal-image program) 
                           image-lib) "repeat"))

        ;; centre the rotation
        (ctx.translate 64 64)
        (ctx.rotate 
            (transform-rotate (terminal-transform program)))
        (ctx.translate -64 -64)

        ;; make the pattern translate by moving, 
        ;; drawing then moving back
        (ctx.translate 
            (transform-x (terminal-transform program))
             (transform-y (terminal-transform program)))

        (ctx.fillRect 
            (- 0 (transform-x (terminal-transform program)))
            (- 0 (transform-y (terminal-transform program)))
            (* 127 2) (* 127 2))

        (ctx.translate 
            (- 0 (transform-x (terminal-transform program)))
            (- 0 (transform-y (terminal-transform program)))))
      (begin
        ;; slightly overzealous context saving/restoring
        (ctx.save)
        ;; set the composite operation
        (set! ctx.globalCompositeOperation (operator-type program))
        (ctx.save)
        (draw-egg ctx x y (operator-operand-a program))
        (ctx.restore)
        (ctx.save)
        (draw-egg ctx x y (operator-operand-b program))
        (ctx.restore)
        (ctx.restore))))

Spork Factory: Amorphous Computing

Departing in a new direction after evolved light follower robots, take 500 processor cores spread out in space. Give them a simple instruction set which includes a instruction to copy (DMA) 8 bytes of their code/data to nearby cores (with an error rate of 0.5%). Fill the cores with random junk and set them running. If we graph the bandwidth used (the amount of data transmitted per cycle by the whole system) we get a plot like this:

bandwidth

This explosion in bandwidth use is due to implicit emergence of programs which replicate themselves. There is no fitness function, it’s not a genetic algorithm and there is no guided convergence to a single solution – no ‘telling it what to do’. Programs may arise that cooperate with each other or may exhibit parasitic behaviour as in alife experiments like Tierra, and this could be seen as a kind of self modifying, emergent Amorphous computing – and eventually, perhaps a way of evolving programs in parallel on cheap attiny processor hardware.

In order to replicate, the code needs to push a value onto the stack as the address to start the copy from, and then call the dma instruction to broadcast it. This is one of the 500 cores visualised using Betablocker DS emulator display, the new “up” arrow icon is the dma instruction.

Thinking more physically, the arrangements of the processors in space is a key factor – here are some visualisations. The size of each core increases when it transmits, and it’s colour is set by a hash of the last data transmission – so we can see the rise of communication and the propagation of different strains of successful code.

The source is here and includes the visualisation software which requires fluxus.

Spork Factory: evolving a light follower robot

Continuing with the structured procrastination R&D project on evolvable hardware, I’m proud to report a pretty decent light following robot – this is a video of the first real-world test, with a program grown from primordial soup chasing me around:

After creating a software model simulation of the robot in the last post, I added some new bytecode instructions for the virtual machine: LEYE and REYE push 1 on the stack if we are detecting light from the left or right photoresistor, zero if it’s dark. LMOT and RMOT pop the top byte of the stack to turn the motors on and off. The strategy for the genetic algorithm’s fitness function is running each 16 byte generated program on the robot for 1000 cycles, moving the robot to a new random location and facing direction 10 times without stopping the program. At the end of each run the position of the robot was compared to the light position, and the distances were averaged as the fitness. Note that we’re not assigning fitness to how fast we get to the light.

This is pretty simple stuff, but it’s still interesting to look at what happens over time in the genetic algorithm. Both motors are running at startup by default, so the first successful programs learn how turn one motor off – otherwise the robot just shoots off and scores really low. So the first generations tend to just go round in circles. Then they start to learn how to plug the eyes in, one by one edging them closer to the goal – then it’s a case of improving the sample rate to improve accuracy, usually by using jmps and optimising the loops.

This is an example of a fairly simple and effective solution, the final generation shown in the animation above:

loop:
  leye 
  rmot 
  nop nop nop nop nop 
  reye 
  lmot 
  or 
  nop nop nop nop
  rmot 
  jmpz loop

Some explanation, the right and left eyes are plugged into the left and right motors, which is the essential bit making it work, the ‘nop’s are all values that are not executable. The ‘rmot’ before the ‘jmpz’ makes the robot scan around in circles if there is no light detected (strangely, a case which doesn’t happen in the simulation). The argumant to ‘jmpz’ is 0 (loop) which is actually the 17th byte – so it’s cheekily using memory which has been initialised to zero as part of it’s program.

This is a more complicated and stranger program which evolved after 70 generations with a high fitness, I haven’t worked out what it’s up to yet:

  pshl 171 
loop:
  lmot 
  leye 
  pip 111 
  pip 30 
  rmot 
  reye 
  pshl 214 
  nop 
  lmot 
  jmp loop

Evolvable hardware

I’m modding a robot toy for the next Spork Factory experiment, the chassis provides twin motor driven wheels and I’m replacing it’s brains with a circuit based on the ATtiny85 for running the results of the genetic algorithm, and a pair of light dependant resistors for ‘seeing’ with.

Here’s the circuit (made in about 20 minutes after installing Fritzing for the first time). It’s quite simple – two LDR’s provide input, and some transistors are needed to provide enough power to the robot’s motors (it’s using PNP transistors as they were the first matching pair I could find, which means logical 0 is ‘on’ and 1 is ‘off’ in the code).

The robot needs to be emulated in software so the genetic algorithm can measure the fitness of hundreds of thousands of candidate programs. We need to simulate the effect of motor speeds on it’s position and velocity – here is a test running the right motor at a constant rate, and gradually increasing the speed of the left motor.

This is the code snippet that calculates the velocity from the 2 motor speeds – more work is needed to plug in the correct values for the distance between the wheels and the actual rotational speeds of the motor drives.

// update dir and pos from current motor speed
float relative_speed_diff=m_left_motor-m_right_motor;
float angle=atan(relative_speed_diff);
    
// rotate the direction by the angle
float nx=(m_dir.x*cos(angle))-(m_dir.y*sin(angle));
float ny=(m_dir.x*sin(angle))+(m_dir.y*cos(angle));
m_dir.x=nx;
m_dir.y=ny;
    
// update the position
m_pos=m_pos.add(m_dir);

Spork factory

A system for creating an abundance of useless software for tiny devices. Spork Factory evolves programs that run on Atmel processors – the same make as found on the Arduino, in this case the ATtiny85 – a £2.50 8 pin 8bit CPU. I’m currently simply using a piezo speaker as an output and evolving programs based on the frequency of the sound produced by flipping the pins up and down, so creating 2bit synths using the Fourier transform as the fitness function. With more hardware (input as well as output) perhaps we could evolve small robots, or even maybe cheap claytronics or programmable matter experiments.

This project reuses the previous genetic programming experiments (including jgap as its genetic algorithm framework), and is also inspired by Till Bovermann’s recent work with Betablocker in Supercollider for bytecode synthesis.

The programs generated don’t use the Atmel instruction set directly, but interpret a custom one derived from Betablocker for two reasons. Atmel processors separate their instruction memory from data (the Harvard architecture) which makes it difficult to modify code as it’s running (either uploading new evolved code or running self modifying instructions), the other is that using a simplified custom instruction set makes it easier for genetic algorithms to create all kinds of strange programs that will always run.

I’ve added an ‘OUT’ instruction, which pops the top of the stack and writes it to the pins on the ATtiny, so the first thing a program needs to do is generate and output some data. The second thing it needs to do is create an oscillator to create a tone, after that the fitness function grades the program on the amount of frequencies present in the sound, encouraging it to make richer noises.

Here are two example programs from a single run, first the ancestor, a simple oscillator which evolved after 4 or 5 generations:

out
out
nop
nop
dec
nop
nop
nop
out
nop
jmpz 254
nop
nop
nop
dup

It’s simply outputting 0’s, then using the ‘dec’ to decrement the top of the stack to make a 255 which sets the rightmost bit to 1 (the one the speaker is attached to) and then loops with the ‘jmpz’ causing it to oscillate. This program produces this fft plot:

After 100 or so further generations, this descendant program emerges. The dec is replaced by ‘pshl 81’ which does the same job (pushes the literal value 81 onto the stack, setting our speaker bit to 1) but also uses a ‘dup’ (duplicate top of the stack) to shuffle the values around to make a more complex output signal with more frequencies present:

out
out
not
nop
pshl 81
pshi 149
out
nop
out
nop
dup
psh 170
jmp 0

Some further experiments, and perhaps even sound samples soon…

Evolving musical bytecode #3

For the next attempt in BetaBlocker bytecode evolution I wanted to favour patterns that had a rhythmic nature by measuring them with this function:

(defn freq [l n]
  (defn _ [c]
    (cond
     (>= (+ c n) (count l)) 0
     (= (nth l c) (nth l (+ c n))) (+ 1 (_ (+ c 1)))
     :else (_ (+ c 1))))
  (_ 0))

Which looks for repeating values spaced apart by “n” positions, so (freq ‘(100 1 2 3 100 4 5 6 100 7 8 9 100) 4) returns 3, as it finds 3 pairs of equal values (100) distanced by the specified 4 positions.

With this fitness function:

(+ (* 50 (count (num-unique res))) ; unique notes are very good
   (freq res 4) ; equal notes every 4 beats are good
   (freq res 6)) ; equal notes every 6 beats are good

We favour rhythmic components of 4 or 6 beats and boost the uniqueness score by multiplying it by 50. After some generations, we get a high scoring individual: 23 23 13 22 7 12 17 20 12 23 23 5 0 7 12 3

Which disassembles as:

loop:
    note    ; play & remove top of stack (zero when empty)
    note    ; play & remove top of stack
    dec     ; decrement top of stack
    dup     ; duplicate - pushes a copy of stack top 
    pshi 12 ; push the value pointed at by address at 12 (self read)
    not     ; performs bitwise not on stack top
    pip 12  ; increment value at address 12
    note    ; play & remove top of stack
    note    ; play & remove top of stack
    pshl 0  ; pushes this literal number (the 0 is at address 12)
    pshi 12 ; push the value pointed at by 12 (self read)
    jmp loop

This program creates a pattern from 4 separate sources, using all 16 bytes of code:

A descending scale using the stack to store the current position.
A rising scale by self modifying address 12 (the 0 in “pshl 0”).
Playing it’s own code as a pattern of notes by using address 12 as a pointer.
Playing the bitwise NOT of it’s own code at the same time.

The result: “0 0 232 255 23 1 232 254 13 2 242 253 22 3 233 252 7 4 248 251 12 5 243 250 17 6 238 249 20 7 235 248 12 8” scores poorly for it’s rhythmic patterns, but it’s probable that this surprising local maxima was found by the early influence of the rhythmic fitness criteria on it’s ancestor populations.

This one was strange enough to warrant dialing into Betablocker DS to see how it actually sounded. Here it is in Hungarian Gypsy scale:

Evolving musical bytecode #2

Following on from the first BetaBlocker genetic algorithm bytecode experiments, in addition to the “most different notes” fitness function I added a similar calculation for the first derivative (ie. the difference between the notes in time order). This was an attempt to steer the evolution away from simple scales and into more complex patterns.

(defn deriv [l]
  (cond
   (empty? l) '()
   (empty? (rest l)) '()
   :else (cons (- (first (rest l)) (first l))
               (deriv (rest l)))))

The code to find the first derivative of a sequence of notes – eg. (deriv ‘(1 2 3 2 6 7)) => (1 1 -1 4 1). We then add this to the fitness function which looks like this:

(+ (count (num-unique res)) ; unique notes are good
   (count (num-unique (deriv res))) ; unique gaps between notes are good
   (min (count res) 20)) ; lots of notes are good (stop at 20)

This resulted in the following bytecode to emerge from the primordial soup: 23 17 7 6 23 21 9 23 8 212 3 2 4 2 180 124 – which disassembles to:

The arrows show the indirection which helps as this one is a bit tricky to pull apart. It’s the first time I’ve seen self modification emerge – it decrements the “212” and uses it as a variable for the note sequence. Combining the pshi and pdp like this is a nice trick I can make use of when programming betablocker myself.

The program is self destructive – the “pop” which otherwise does nothing of use will eventually write zeros over the program itself if it’s run for a few more cycles than the 100 I’m testing the programs for.

The output looks like this:

0 212 255 211 0 210 0 209 0 208 0 207 0 206 0 205 0 204 0 203 0 202 0 201 0 200 0 199 0 198 0 197 0 196

According to our fitness function, the interleaved zeros give it a very high scoring derivative list:

212 43 -44 -211 210 -210 209 -209 208 -208 207 -207 206 -206 205 -205 204 -204 203 -203 202 -202 201 -201 200 -200 199 -199 198 -198 197 -197 196

However the actual pattern is not so interesting, so still more work needed on the fitness criteria.

Evolving musical bytecode

At it’s core, Betablocker provides a simple virtual machine for playing with music which is ‘unstoppable’ (any combination of instructions can be executed). It started off originally as a Fluxus scheme program, then got rewritten in C++ for the Nintendo DS, and has now been ported to Supercollider. I’ve built yet another Linux commandline version, and glued it to the Java Genetic Algorithms Package via Clojure.

This means I can continue with the genetic programming experiments and try evolving programs using a real genetic algorithm framework, using the betablocker instruction set. This is mainly just for kicks, but it’s also partly to “grow” new strategies for livecoding betablocker and researching instruction sets more generally.

The first test was to try and find a program to just play note 99. I would write this in betablocker like this (using a text representation of the icon interface for convenience):

    pshl 99 ; push the literal value 99 on to the stack
    note    ; play the top of the stack as a note 

First we need a fitness function to score the results from the programs which are generated:

(defn fitness [notes]
    (- 255 (Math/abs (- (first notes) 99))))

It takes a list of the notes played by a candidate program, and measures how far away the first element is from 99 – the bigger the number, the fitter the individual program is. I gave it 8 instructions to work with and a population of 500 individuals – after just a couple of generations, this chromosome/program popped up with a top fitness of 255 – meaning it was successfully playing note 99:

99 46 213 89 7 142 23 168

Which when disassembled looks something like this:

    99       ; <-- address 0 
    nop
    nop
    nop
    pshi 142 ; pushes contents of address at location 142 (which is 0)
    note     ; play the note
    nop

This program has grown taking advantage of the fact that the memory is initialised to zero, so if it dereferences a large address like 142 it will be zero and load the contents of the first byte - 99. It's this kind of wacked out approach genetic algorithms are great at finding/abusing.

The next problem, something a bit more general - create a sequence of notes which are all different to one another. The fitness function:

(defn list-contains? [l i]
  (cond
   (empty? l) false
   (= (first l) i) true
   :else (recur (rest l) i)))

(defn fitness [a]
  (count
   (reduce
    (fn [r v]
      (if (not (list-contains? r v))
        (cons v r)
        r))
    '()
    a)))

This just counts the number of unique elements in the list - again, the higher the better. This one took longer, but eventually came up with this:

139 246 1 23 12 22 23 12 20 95 22 3

Which when disassembled:

    nop
    nop
    org
start:
    note      ; play a note
    inc       ; increment top stack byte
    dup       ; duplicate top stack byte
    note      ; play a note (consumes 1 stack byte)
    inc       ; increment again
    pip 95    ; increment address 95 (junk - doesn't have any effect)
    dup       ; duplicate again
    jmp start ; return to the start

Which plays a rising sequence of notes, with none repeated, so the highest fitness achievable:

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21

This is already doing much better than the genetic programming I was mucking about with before - indeed there seems to be some literature on evolving java bytecode, but with betablocker there is an advantage that you don't need to enforce the correctness of the programs before they can be run.

Genetic programming music patterns #2

A bit more from the growing of music programs department. (Part 1 can be found here along with reasons for doing this). I’ve been trying to generate ever so slightly more complicated patterns, such as:

(50 50 0 0 50 50 0 0)

Not too exciting, but it proves quite difficult for my naive system to generate code for. A lot of times the evolution becomes stuck in the average number pattern, eg (25 25 25 25 25 25). In genetic programming (and other similar fields) such stuck states are called “local minima” as the system can’t get itself out of a relatively stable state. The problem is that in order to get to a better solution we may need to get worse first. A good description is that you are trying to find the lowest point in some imaginary terrain, and you are stuck in a puddle at the top of a mountain.

Here is a detailed look at exactly what is happening during the evolution process of a program which almost worked. We start with this:

(20 23 1 4 3 7 11 15)

Which was scored well due to the first four elements, the code for this individual (randomly generated, as it’s the first generation) is:

(mod (mod (+ (even 31) 97 22) (- 86 53 (clock))) 25))

Notice that bits of this code are unnecessary, (+ (even 31) 97 22) could be replaced by 119. Some genetic programming systems do this automatically, the approach I’ve taken is to assign a cost to the size of the procedure which should make shorter programs fitter – but I haven’t really tested this works yet.

This code has a cost of 31684. I’m squaring what I was calling fitness before, and calling it cost instead, which makes a bit more sense.

The following generation the cost drops to 15376 with:

(33 23 13 3 29 20 11 2)

Which is starting to approach the periodic nature of the target. This is the code:

(mod (mod (+ (even 31) 97 (+ 97 31 91)) (- (max (/ 56 8 75 92) (mod 21 84)) 53 (clock))) 37)

Considerably more complex, however if we manually remove all the constant expressions, we get this:

(mod (mod 316 (- -32 (clock))) 37)

It looks like the inner modulo providing something like the periodic nature that we need:

(mod 316 (- -32 (clock))) => (-4 -14 -24 -34 -8 -17 -26 -35)

While the outer modulo attempts to scale the “rhythm” values to a range closer to the target pattern. This seems like a good strategy, lets see what happens next. Generation 5 6 and 7 rapidly refine this process by tweaking the numbers – I’ve highlighted the mutations for each generation in red:

(mod (mod (+ (even 37) 96 (+ 97 31 91)) (- (max (/ 56 8 75 92) (mod 21 84)) 53 (clock))) 37) => (32 22 12 0 28 19 10 1)

(mod (mod (+ (even 37) 96 (+ 97 31 91)) (- (max (/ 56 8 75 5) (mod 21 84)) 53 (clock))) 62) => (57 47 37 0 53 44 35 26)

(mod (mod (+ (even 37) 96 (+ 97 31 91)) (- (max (/ 62 96 75 5) (mod 21 84)) 53 (clock))) 53) => (48 38 28 0 44 35 26 17)

The cost is now 11236. Generation 13 this drops to 11025 with another minor tweak:

(mod (mod (+ (even 37) 96 (+ 97 31 91)) (- (max (/ 62 96 75 5) (mod 21 84)) 53 (clock))) 56) => (51 41 31 0 47 38 29 20)

Then, on generation 31 we get a big improvement, with the cost dropping to 2601.

(mod (mod (+ (even 37) 96 (+ (clock) 31 91)) (- (max (/ 56 96 75 5) (mod 21 84)) 29 (clock))) 56) => (50 50 0 46 50 45 0 0)

A couple of numbers tweaked and a (clock) in the previously constant addition expression – this is a good case for leaving redundant code expanded, as it can be used later on due to the processes of mutation. Removing the constant bits to find out what’s going on, this can be simplified to:

(mod (mod (+ (clock) 218) (- -8 (clock))) 56)

The outer modulo is scaling the inner one as before, which is now providing this “rhythm” pattern:

(mod (+ (clock) 218) (- -8 (clock))) => (-6 -6 0 -10 -6 -11 0 0)

Unfortunately, even after 1000 generations (50 50 0 46 50 45 0 0) remains the closest to (50 50 0 0 50 50 0 0) we get – close, but no cigar.