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.

I’ve had success with:

http://www.lri.fr/~hansen/cmaes_inmatlab.html

Thanks – I’m mainly interested in implementing my own system as I want to understand how it works (rather than needing a tool for a specific job), but that looks very useful for reference – particularly as it supports so many different languages.