I have a problem when livecoding music, in that while I’m happy livecoding synth graphs to make sounds, I sometimes get a bit stuck coming up with patterns of notes for them to play. I generally start with something like (note (modulo clock 8)) and work my way fairly randomly from there.
In need of inspiration for making more complicated patterns with the minimum of code I thought I’d continue my sporadic ongoing mission to explore genetic programming (towards the much desired future of a machine programming itself). The idea is to use a fitness function to grow programs that make patterns I can specify. I could then use these programs as they are, generate them live, or steal ideas from the evolved code.
To give an example of a pattern, this is the first 13 notes of the famous techno number “mary had a little lamb” in major scale:
(2 1 0 1 2 2 2 1 1 1 2 4 4)
The first thing we need is an instruction set that can be used in machine generated programs. These need to be robust to any inputs, and rich enough to provide the sort of patterns we want to generate. I’ve started with a fairly minimal set:
(mod a b) : return modulo of a to b, or zero if b is zero.
(odd a) : return 1 if a is odd, 0 otherwise.
(even a) : return 1 if a is even, 0 otherwise.
(min a b) : return the minimum of a or b.
(max a b) : return the maxium of a or b.
(+ a b . . .) : addition.
(- a b . . .) : subtraction.
(* a b . . .) : multiplication.
(/ a b) : division – returns zero if b is zero
In order to drive the program we also need a (clock) function that returns the time – or more precisely, the place in the pattern we are in.
So the program: (+ (mod (time) 3) 2) repeated 5 times would result in the pattern (2 3 4 2 3) .
We also need a fitness function which will give us a measure of how close a pattern is to the one we are trying to find a program for. This could be the sum of the differences between each element of the generated pattern and that of the target pattern – where 0 is perfect and the bigger the number the worse the fit, eg:
(define (fitness pattern target) (foldl (lambda (a b r) (+ r (abs (- a b)))) 0 pattern target))
Lets try something simple to begin with – the pattern (50 0 50 0 50 0). We start with a population of 1000 randomly generated programs and pick the best one – hold on to your hats:
A complex program that surprisingly results in the pattern: (21 21 21 21 21 21). This has a fitness of 150 – and 21 is quite close to the average of 0 and 50, so although it’s disappointing, it makes sense.
We now create a new population, some of the individuals are new random programs, others are mutated versions of the previous best attempt (25%/75% if you really want to know). We also include the previous best attempt without mutation – this stops generations getting worse over time. Unfortunately in this run it takes 90 generations before a fitter individual is found:
(* 35 (even (clock)))
Which generates the pattern: (35 0 35 0 35 0) with a fitness of 45. Now it is only a matter of time, in fact the next 3 generations slowly home in:
(* 55 (even (clock)))
(* 52 (even (clock)))
(* 49 (even (clock)))
and then then on generation 104 we finally get:
(* 50 (even (clock)))
resulting in (50 0 50 0 50 0), with a fitness of 0.
More soon – code here.