Tuesday, June 26, 2012

Evolving music

Back when I worked as a computer programmer I spent some time seeing whether a genetic algorithm would help with one of our ongoing tasks. A genetic algorithm works in the same manner as biological evolution. It contains these steps:

1. Create a large number of solutions in which the pieces of the solution are generated randomly. It is likely (almost guaranteed) that no solution is very good. That's OK.

2. Test the solutions and rate them on how well they solve the actual problem. This corresponds to survival of the fittest.

3. Toss out the lowest scoring solutions.

4. Mate pairs of high scoring solutions. This means randomly select pieces of two solutions to create an offspring solution. Yep, this corresponds to sexual reproduction.

5. Randomly tweak the offspring solutions. Add in some genetic mutations.

6. Go back to step 2 with the offspring solutions for perhaps a few hundred (or thousand) generations. The best solution is the one with the highest score at that point.

I first heard about genetic algorithms in an article that had an example something like this (feel free to skip this paragraph): A company had several warehouses in which some products were easy to get to and some were harder. Which were easy and which were hard varied between warehouses and were dependent on what arrive from the factory and when in a particular week. There are several trucks taking products to several stores, the amounts of each depending on what the store ordered. Given the way product sits in the warehouse there is a cost to getting it on the truck. There is a cost, depending on the truck's route of getting the product to the store. How much of which product should be taken out of which warehouse and delivered to which store to achieve the lowest cost? Genetic algorithms provided answers with lower cost than previous methods.

I won't go into the type of problem I tried to solve with genetic algorithms (eyes will glaze if they haven't already). I was able to get a an answer for a simple case, but not when I made it a bit more complex. One way to say it is that I needed a solution with a cost lower than a particular amount and my program couldn't get it to come out that low.

I've shifted to the world of music now. And so have genetic algorithms.

Researchers of the Imperial College of London created sound samples from random sequences of computer generated pitches (step1 above). They then asked participants to listen to the sound samples and rate them from "I can't stand it" to "I love it!" (step 2). They followed steps 3 to 6 to create a new series of sound samples. It didn't take long before the samples developed chords, a bass beat, and fragments of melody. However, the results didn't improve after about 900 generations. Given the algorithm and what it allowed to vary, this may have been the best it could do.

That led to some interesting questions. Even when music is carefully composed and performed, what is the role of consumer in our Western music? How has that role changed with widespread ability to download, manipulate, and share music?

I know of software programs that analyze the music of a particular composer then create original works in the style of that composer. Many people freak out at the mention of a computer "composing," but the computer wouldn't get very far without the original human composer's work. This may be another way for a computer to generate music, though I see it still required humans to determine what is good. Even so there are hints that humans could be less involved. The researchers used methods of measuring chords and rhythm as a way to verify what the participants did. Perhaps these measuring tools could be used instead of the humans deciding what they liked and didn't like. But -- so far -- humans are still needed to write the genetic algorithm programs.

The authors created the site Darwin Tunes to allow participants to rate the sound samples. The site now has audio clips to explain what was done and a selection of about 4000 generations of sound samples. They also wrote a six-page scientific paper (I understood the basics, but not all of the concepts).

No comments:

Post a Comment