Optimisation and all that jazz

Computer scientists can find inspiration in the strangest of places to help solve some of the toughest mathematical problems. One such mathematical problem is called optimisation; you do it every day when you decide what favourite songs go on your play list, or work out the shortest route to school. Optimisation is about finding the best solution: deciding on the best choice from a range of options. Optimisation is important commercially too. How do you connect all the houses on a new estate together with the least amount of electrical wiring or fewest sewer pipes, for example? What’s the best route for your delivery trucks to take round the shops with the minimum mileage (while trying to avoid using the motorway at rush hour) and so on. Solving these problems isn’t easy, particularly when you have many, many options to choose from. Jazz it up

Music, and in particular jazz improvisation, would seem an odd place to look to help solve this classical optimisation problem, but that’s just where a rather cunning method called ‘harmony search’ found its inspiration. When jazz musicians play together they select the musical notes in their instruments to give the best overall harmony with the rest of the group. This often happens in stages. One musician will play a tune; others will remember it and work out what notes they want to play along with it. As time progresses, and remembering the music they have played before, they move note by note to blend together, making more and more beautiful music. In effect they are doing an optimisation. Each musician has to choose the right notes for their instrument in the right order to make the best group harmony possible.

Music by numbers

Now, rather than having musical notes from particular musical instruments (like Do, Re, Mi, …), you can have a string of numbers (100, 200, 300, …), and these numbers can represent the possible options in the problem you want to optimise. Like notes in a tune, each ‘instrument’ can play a range of notes (take particular values). It’s just about finding the right set for each for the group to ‘play’ the best solution. Rather than looking for the most harmonious, beautiful music to emerge, you instead calculate how good your solution is in another way. For example, you might take the numbers (notes) in your solution (tune) and use them to calculate how many miles the truck drives, or the length of sewage pipe needed.

Verse one

You start with a set of random solutions (tunes). This is like having multiple groups of jazz musicians selecting their first tune in their jazz improvisation session. You then see how good these solutions are. Ranking and storing these solutions in your harmony memory, like a top 10 with the best solution at Number 1, you play on.

Many a good tune

In the next stage, like the jazz musicians, you can randomly change the numbers (notes) within your instrument’s range to see if that helps improve things. You can also choose other suitable notes stored in the harmony memory to see if that does the trick, or do a pitch adjustment – change the value slightly from the value in memory to see if that improves things. Each resulting solution is then given a test. Is it any good? If it isn’t, for example if a solution misses out plumbing in the toilet at No 42, it is equivalent to a really bad tune, and so isn’t likely to be any use. You rank and store the new solutions in the harmony memory. Even poor solutions can be usefully stored, way down at the bottom of the ranking, as it might be possible to use bits of them to make much better solutions. After all, many great musical tunes made use of strange harmonies. You then play on till you get a super good solution you’re happy with, or you run out of allocated time on your computer, and the optimisation musical is over.

Drawing on a study of human musical creativity, and being able to solve tough maths problems, it’s fair to say that optimisation by harmony is a hit with many computer scientists!