Evolving a Melody - Using Genetic Algorithms as a Music Composition Tool

Just as an essay, a story, or a movie have a theme running through them, sometimes more than one - so does a musical composition. A piece of music, often starts with a theme, which is also as one of the main recurring motifs throughout the piece. It's nice to hear a recurring motif. It's somewhat interesting to hear some variations on a recurring motif, or a group of related motif.

I started with a fairly simple motif and I wanted to save it as a MIDI file. There are several ways to create a MIDI file, with MIDI sequencers and MIDI controllers, such as a keyboard. In this project I wanted to use as Perl as possible. So I decided to create this motif using the MIDI::Simple module

MIDI::Simple is somewhat limited, e.g. it can only handle a single track. This was not an issue for me here, since I only needed on track to start with. Despite its limitations, I like it because it creates a music DSL (Domain Specific Language) within Perl.

use MIDI::Simple;
new_score;

Volume 127;  
n hn , G4;
n qn , C5;
n en , Bf4;
n en , C5;
n qn , D5;
n qn , A4;
n en , Bf4;
n en , C5;
n qn , D5;
n qn , G5;
n dhn , F5;




write_score 'motif.mid';

This codes the file motif.mid

Using this code one can dump the events from that MIDI file:

use MIDI;
my $file = shift @ARGV;
die " no file specified " unless $file;
my $opus = MIDI::Opus->new({'from_file' => $file});
my @tracks = $opus->tracks();
foreach my $track (@tracks) {
	foreach my $e ($track->events) {
		next unless $e->[0] =~ /note/;
		print join "\t" , @{$e} , "\n";
	}
}

And here is the dump:

event     delta ch note velocity
note_on	    0	0	55	64	
note_off	192	0	55	0	
note_on	    0	0	60	64	
note_off	96	0	60	0	
note_on	    0	0	58	64	
note_off	48	0	58	0	
note_on	    0	0	60	64	
note_off	48	0	60	0	
note_on	    0	0	62	64	
note_off	96	0	62	0	
note_on	    0	0	57	64	
note_off	96	0	57	0	
note_on	    0	0	58	64	
note_off	48	0	58	0	
note_on	    0	0	60	64	
note_off	48	0	60	0	
note_on	    0	0	62	64	
note_off	96	0	62	0	
note_on	    0	0	67	64	
note_off	96	0	67	0	
note_on	    0	0	65	64	
note_off	288	0	65	0

event - type of event
delta - time difference since the previous event
ch - MIDI channel
note - note number - following the MIDI spec for note numbers
velocity - in MIDI this means the volume of the specific note

My next task was to explore similar melodies, variant motifs, that I could use in my composition. One way of doing was going back to the keyboard (the piano, or MIDI contoller) and play the melody, tweak it. However, for this project, I wanted to see if I could use an algorithm to explore the Melody Space, so to speak, and find similar melodies, but not too similar.

To that end, first I had to figure out what similar means to me in this context. In Western tonal music, in the common equal temperament tuning, when a melody is transposed up or down, that is, when all the notes are transposed up or down by the same number of semi-tones (keys on the keyboard), the melody sounds the same.

Thus similarity does not depend on specific notes. It depends on the intervals between notes. Furthermore, rhythmic patterns are also part of the essential characteristics of a melody. For this particular piece I decided that similar rhythmic patterns were more significant to me than melodic similarities.

What I looked for was a method to create a lot of similar melodies, where I can score the melodies according to similarity, and gives similarity of different characteristics different weights. Given that as the an informal statement of the problem, I needed a method to provide a lot of approximate solutions.

A few years back I used genetic algorithms to synthesize sound. Genetic algorithms is an approach that uses concepts of darwinian evolution to solve problems. It's not guaranteed to find a solution. When it does, it can sometimes arrive at very good solutions, sometimes, solutions that humans might not find. When it doesn't find a solutiont, it can quickly arrive at good approximations. That is exactly what I wanted, pretty good approximations. That would make a somewhat unorthodox use of genetic algorithms.

To use genetic algoritms one needs two have :

• Genetic representation of solutions
• Genetic operators
• Fitness function

The concept is that a large population of random solution is created. All solution are tested using a fitness function, created for the specific problem. The scores given to each solution, referred in GA as a chromosome, determine which chromosomes get to breed, and how many descendants they get to have. There are several methods that can be used to determine the exact numbers.

The breeding is done by taking two or more parents, taking part of each parent's genes (parameters), and creating a new chromosome for the next generation. Once the next generation is created, the process repeats until a solution, or the maximum number of generations specified, has been reached.

As I already stated previously, to encode the melody I don't need the exact notes, but rather the intervals between them. I also need the durations. There are a several modules on cpan that implement existing algorithms for string similarity. If I encode the intervals and the durations as strings, I can leverage those modules to determine the similarity between. I decided to encode intevarls as characters. Ascending intervals as upper case characters, and descending intervals as lower case characters, with 0 representing the 0 interval, that is, a repeating note.

I also decided to encode the durations as characters. In this case the character stands for the numbers 1-16, which is the length of the note in 16th notes. The first note need not be encoded, since we're only dealing with intervals, the first note can always be the same note.

To associate each note with its duration, each note is followed by its duration, the exception being the first parameter, which is the duration for the first note.

The following code reads a midi file with a melody and encodes it as a chromose according to the encoding described above:

use MIDI;
my $file = shift @ARGV;
die " no file specified " unless $file;
my $opus = MIDI::Opus->new({'from_file' => $file});
my @tracks = $opus->tracks();
my $track = shift @tracks;
my $prev_note = 0;
my @chromosome;
#event delta channel note velocity
foreach my $e ($track->events) {
	next unless $e->[0] =~ /note/;
	if ($e->[0] eq 'note_off' || 
	    $e->[0] eq 'note_on' && !$e->[4]) {
		push @chromosome , chr($e->[1] / 24 + 64) ;	
	}
	elsif ($e->[0] eq 'note_on') {
		my $interval = $e->[3] - $prev_note;
		$prev_note = $e->[3];
		next if $interval == $e->[3];
		if ($interval > 0) {
			push @chromosome , chr($interval + 64);
		}
		elsif ($interval < 0) {
			push @chromosome, chr(abs($interval) + 96);
		}
		else {
			push @chromosome,'0';
			
		}
	}
}

print join ' ' , @chromosome;

The results looks like this:

H E D b B B B B D e D A B B B B D E D b L

The module I used to create the variant motif is AI::Genetic::Pro

my $ga = AI::Genetic::Pro->new(
	-fitness	=>	\&fitness,
	-type		=> 	'listvector',
	-population	=>	1000,
	-crossover	=>	0.9,
	-mutation	=>	0.02,
	-parents	=>	2,
	-selection	=> 	['RouletteDistribution','uniform'],
	-strategy	=>	['Points' , 2],
	-history	=>	0,	
);

fitness is the fitness function provided by me.
type - type of parameter vector.
population - how many chromosomes (candidate solutions) are in the population.
crossover and mutation are the probabilities that crossover and mutation will occur. The probability for mutation is usually kept low, 0.01 or 0.02.
parent - the number of parents
select - how the parents are selected
strategy - the breeding strategy - in this case a 2 point crossover
history - specify how many of the top scoring chromosomes to keep for the next generation as-is. Generally genetic algorithms improve the score over a sufficient number of generations, but they are not guranteed to improve over any single generation. Keeping a the few top scoring solutions (chromosomes) for the next generation guarantees that the top scorers in each generation are at least as good as in the previous generation.

Next is initializing the population:

$ga->init([
		['A'..'P'],
		['a'..'k','A'..'K',0],
		['A'..'P'],
		['a'..'k','A'..'K',0],
		['A'..'P'],
		['a'..'k','A'..'K',0],
		['A'..'P'],
		['a'..'k','A'..'K',0],
		['A'..'P'],
		['a'..'k','A'..'K',0],
		['A'..'P'],
		['a'..'k','A'..'K',0],
		['A'..'P'],
		['a'..'k','A'..'K',0],
		['A'..'P'],
		['a'..'k','A'..'K',0],
		['A'..'P'],
		['a'..'k','A'..'K',0],
		['A'..'P'],
		['a'..'k','A'..'K',0],
		['A'..'P'],
		['a'..'k','A'..'K',0],
		['A'..'P'],
		['a'..'k','A'..'K',0],
		['A'..'P'],
		['a'..'k','A'..'K',0],
		['A'..'P'],
		['a'..'k','A'..'K',0],
		['A'..'P'],
		['a'..'k','A'..'K',0],
        ['A'..'P']
	 ]);

The first of each pair is a duration gene, the second a note gene. Now to make it work:

#run the genetic algorithm for 60 generations
$ga->evolve(60);

#get the 40 top scoring solutions
my @top = $ga->getFittest(40);

#print them out
foreach my $t (@top) {
	print join ',' , $ga->as_array($t);
	print "\n";

}

The fitness function is specific for each problem, however, it's invoked as an object method. It starts with

sub fitness {
    my ($self,$chromosome) = @_;
}

$chromosome is a reference to an AI::Genetic::Pro::Chromosome object.

The fitness function in this specific case reads the encoded original motif. Then it takes the two encodings and generates from them an interval string, a durations string, and an inverted interval string. An inverted melody is sometimes used in music. I figured the algorithm might find an interesting variant similar to the inverted melody - however it's given a very low weight in the scoring. Then I used the modules String::LCSS , String::Trigram , and String::Similarity to determine similarity between the candidate solutions and the original motif.

After a few runs, experimenting with relative weights, I had several dozen variant motif. At this point I selected a few that seemed interesting for me to use. This process is not a strict algorithmic composition process. I did not commit in advance to do whatever the machine tells me.

The five variant motif I selected came from two runs:

• 35_res2.mid
• 38_res2.mid
• 40_res2.mid
• 25_res2.mid
• 27_res3.mid

My next step (in an upcoming post) will be to implement an algorithm that would find where and when in the piece these motif might be used to create a skeleton for a coherent musical structure.