Violin Music Notation
To play a single musical note on a violin a particular length of bow is required. When playing music the bowing direction must change frequently to prevent running off the ends of the bow. Sheet music can be marked to indicate where to change direction to achieve the best from the music. Particular passages should played on the upstroke of the bow, others on the downstroke. Some sections require a constant bow direction whereas other are better if the bow changes direction. Finding where these bowing changes should be to produce the initial annotated music is a lengthy business based on educated guess work.
Here is a complex search space currently laboriously explored by hand. Automation would at least speed up the markup process with final polishing done by the composer, perhaps it could even produce playable results within minutes instead of hours.
As this is an entirely new problem the first step is to make an analysis from the viewpoint of a genetic algorithm. A representation must be found to hold a potential solution to the problem. Music can be thought of as a sequence of notes each associated with the bow length required to play that note. An appropriate representation here seems to be a sequence of numbers equivalent to the bow lengths. In addition at each note the bow may either change direction (c) or not change direction (n).
1 2 3 4 5 6 7 8 9 8 7 6 5 4 3 2 1 n n n n n c n c n c n c n n c n n
Rules dictated by the music can also be encoded alongside. Bow direction maybe required to be upward (U), downward (D), changing (C), or not changing (N).
1 2 3 4 5 6 7 8 9 8 7 6 5 4 3 2 1 n n D D D c n C n c n U U n c n n
Each individual carries different lower-case values but identical upper-case values and lengths. Obvious mutation operators would swap letters around but this could create illegal solutions, ones which did not follow the rules. Illegal solutions could be repaired or given penalty points during evaluation but neither is ideal. Separating fixed and variable parts of the solution avoids both problems. Then only the variable part need undergo mutation and crossover.
1 2 3 4 5 6 7 8 9 8 7 6 5 4 3 2 1 - - D D D - - C - - - U U - - - - n n c n n c n n c n n
The fixed upper section is common to all individuals and so can be factored out of the individuals and placed in the evaluation function. The variable lower section consists of only two possibilities and is therefore suited a binary vector representation.
Evaluating the performance of an individual is a matter of simulating the position of the bow on the strings. Better or lower scores awarded for the fewer changes of direction. Unfortunately it now becomes apparent that illegal solutions are still possible. For example, an individual may exist in which no direction changes are specified and the bow could then overrun. Correcting this requires a more complex evaluation function which not only changes direction as direct by the individual but also when it must in order to continue playing.
This initial analysis of the problem took under an hour but never made it to the implementation stage. Subsequent thought highlighted certain detrimental effects of standard binary mutation. A single change to the first note in an individual may dramatically change the meaning the remaining notes as the evaluator is forced to make different decisions. This simulation of the music in the evaluation function is another problem. To prevent the bow from overrunning much time must be spent backing up and trying alternate direction choices. Many evaluations must be made over the duration of a genetic algorithm which would be slow as a result.
The alternative which was chosen for the final implementation modified the evaluation function to remove the need for backups. Now an infinitely long bow is simulated and the amount of that bow required by an individual is measured. Again scores could be assigned according to the number of direction changes but also on how much bow length required. Better scores are given to individuals who come close to the actual bow length.
This design is remarkably similar to that used for The Blues, only a evaluation class and main program body are different. The evaluation object is used to store the fixed sections of music and during evaluation gaps in the music are replaced with the information stored within the individual. The main program creates other objects including those controlling unity fitness, roulette wheel selection, single bit mutation, and one point crossover all of which are already found within the toolkit.
In the end such a simple algorithm was not capable of coping with the rigours of a real musical example and instead a small toy data set was used to test the algorithm. Here it is presented as above with note lengths on top and bowing rules on the bottom.
6 7 8 5 7 6 8 6 6 8 5 7 7 5 8 - - U U U - - - C - - - - D D
A target bow length of 30 was chosen for the test and the random initialisation phase managed to produced a individual which required a bow of length only 33. Because of the simple generational model constant improvement was not guaranteed and by the 43rd generation the best individual was 39 units long. However by the 71st generation other avenues had been explored and the target of 30 had been reached. Overall this seems a reasonable result given the time taken on its development.
MUTANTS proved its worth with this algorithm, almost all of the code was already in place. Design considerations took about an hour and implementation around four more. Although the algorithm has not been attempted without the use of the toolkit I would anticipate taking slightly longer to complete all the work essential to the algorithm without it. The saving in time is significant but not huge for someone familiar with coding genetic algorithms.
More important is that with the toolkit fully implemented dozens of variations could be made in almost no additional time. Simple changes to the main program body would give different fitness function, mutation and crossover operators. Some are bound to show better properties than others. In a single day this problem could be taken from scratch and numerous possible algorithms designed and implemented. Each additional specialised component written will give rise to many additional algorithms.