文档库

最新最全的文档下载
当前位置:文档库 > GENERATING MUSIC THROUGH GENETIC ALGORITHMS

GENERATING MUSIC THROUGH GENETIC ALGORITHMS

Science Research Programme 1996

GENERATING MUSIC THROUGH GENETIC ALGORITHMS

Lim Yu-Xi1, Lua Kim Teng2

ABSTRACT

Genetic algorithms attempt to embody Darwin’s Theory of Evolution in a series of computational steps, usually to derive optimal solutions to a given problem. This process is normally attributed to thinking and creativity but can be simplified in this case to a series of converging solutions. We have attempted to apply genetic algorithms to the composition of music, where the optimal solutions are the better sounding pieces. The main aim of this experiment was to derive an algorithm and find suitable values for its parameters. There was reasonable success in this experiment, which had a narrowed scope of classical music. One of the main problems encountered was defining what is good music.

INTRODUCTION

Intelligence and evolution are intimately linked. Intelligence is a natural part of higher lifeforms, but it can be broken down into simple steps and be simulated to a limited extent. One of the most daunting aspects of intelligence is creativity. Non-deterministic creativity is the spontaneous generation, derivation and selection of ideas. Interestingly, such a process can be found in another part of life – evolution.

Charles Darwin and Alfred Wallace presented their joint paper on the Theory of Evolution in 1858. It presented an idea which was highly controversial at the time when the word of the Roman Catholic Church was powerful. They proposed that the multitude of species that we observe today is the result of selective pressures against those that became extinct and for those that survive till today.

Such pressures work on the physical manifestations of the various traits of a given organism. Such traits are expressions of the organism’s genes, and the whole collection of genes is the organism’s chromosomes, or its genome.

Undesirable traits are gradually removed from the collection of genes, also know as the gene pool. This is because organisms having such undesirable traits have lower fitness, and are less likely to reproduce and propagate their genes. The opposite happens for desirable traits as they increase in frequency in the gene pool.

It is not always that undesirable traits become eliminated from the gene pool, not is it always that the gene pool will be dominated by a certain most desirable gene. Various combinations of genes can have different effects from the individuals from which it is derived. From here, it can be seen that it is likely that there will be several dominant chromosomes or genomes after a time. Each of these chromosomes will have desirable combinations of genes.

The genes do not just stagnate but undergo mutation at a constant rate. Random point mutations can change a specific gene to another. Other mutations reverse short portions of the

1 Science Research Programme student, Raffles Junior College, Singapore

2 Department of Information and Computational Science, National University of Singapore

chromosomes, duplicate them, or delete them from the chromosome. These usually produce inferior organisms that quickly perish, but sometimes, a better adapted organism may arise and it will multiply and go on to compete with the existing ones.

There is also a process called crossing over, which occurs during sexual reproduction where the chromosomes from male and female organisms intermingle to give new combinations.

The fitness of the gene pool is only one indication of the chance of a certain species surviving. Gene pools which exhibit great diversity are more likely to weather severe changes in environmental conditions where previously disadvantageous genes are now desirable. Gene pools with great diversity may have a lower average fitness value when compared to one with a narrow range but high fitness.

These evolutionary processes can be applied to problem solving, in a technique known as evolutionary computing, which is a form of asymptotic convergence. We attempted to apply evolutionary computing to the computer composition of music. Evolutionary pressures in this case was our taste of music, and the pieces which sounded best were most likely to propagate and multiply. The chromosome is a short piece of music, technically known as a phrase. Each note is a gene, and thus complex interactions between the genes are now easily observed. No gene will sound good by itself, as only the quality of only a group of genes can be determined. The computer was provided a few rules to decide how good each chromosome sounded, and assigned a fitness value to each one. From there, a few are chosen to undergo crossing over and mutation. These then go on to become the next generation and the cycle repeats.

Simulating creativity on a computer is one of the hardest aspects of artificial intelligence. Getting a computer to compose music is one step in that direction. The uses of computer generated music are diverse. Simple modification would allow the computer to compose music to fit a certain mood, theme, motif or even lyrics. Adaptive music in computer games and virtual reality will help improve the totality of the sensory immersion.

PROCEDURE

After planning what areas of music composition we should cover and the programming requirements, we started by collecting musical samples.

It had been decided that we would narrow our scope to classical music because of its availability, the number of distinct styles and its well documented and fixed set of rules. The musical samples collected were thus classical music pieces by various composers like Beethoven, Chopin, Handel, Liszt, Mozart, and Scarlatti.

These musical pieces were to be analysed mathematically to determine what combinations of pitches, durations, and volumes were most frequent. For simplicity, it was assumed that a greater frequency of occurrence means better sounding combinations.

Most of the pieces were collected from the Internet in the MIDI format. They were then converted our own format which eliminated chords and polyphony and had only the three attributes which we were interested in. Thus, the file was a sequential list of the attributes of the note with the highest pitch then.

At first, the frequency of the occurrences of various combinations of the three attributes was examined. For example, there were counts of the occurrences of various pitches and durations of a given note. Another tally taken into consideration was the attribute present in one note and its value in the next, for example, the frequency of occurrence of a given pitch after another given pitch.

Thus, six sets of bigrams were assembled: pitch-pitch, volume-volume, duration-duration, pitch-volume, pitch-duration, and volume-pitch. The values were normalised, i.e. the total number of occurrences was counted and the probability of a given combination occurring was calculated. In all 80 songs with well over 10000 notes were analyzed. This processed data formed the basis of one of the criterion for determining the fitness value of a chromosome. If a chromosome had a sequence which had a high probability of occurrence, it would have a higher fitness value.

One of our first tests relied solely on this data to generate and select chromosomes. We did not expect much from it and indeed the notes generated were only a little better than purely random noise.

After that, several more rules were defined to restrict the type of notes produced. They were as follows:

Notes cannot be too far apart in terms of pitch

Notes cannot be too short or too long

Notes should be to the key of C Major

There should not be too many rests

Notes should be of certain intervals

Repetitive notes should be avoided

Each rule had a different weight, which controls how much it affected the final fitness value. The rules themselves had their own variables which can be adjusted. For example, the rule regarding note length, which was a lookup table of values, could have each element individually modified.

Admittedly the relevance of certain rules could be questioned. The rule that stated that repeated notes should be avoided is one example as many good songs do have strings of repeated notes. Still, it was discovered that without this rule, the algorithm tended give very long strings of repeated notes. This is due partially to the rule which restricted the difference in the pitch of adjacent notes.

Another change we made was to further restrict the scope of the input data. We had decided that the most probable cause for the seemingly random nature of the songs by the first algorithm was most probably due to the diverse range of styles present in the input data. This time, we restricted ourselves to all the different movements of Inventions.

Other variables that we could control were the rate and extents of each type of mutation and the rate of crossover. We could also adjust the percentage of the population selected to give rise to the next generation and how this selection is done – best few or roulette wheel. Selecting the best few meant we taken only those chromosomes which fitness value exceeded a certain threshold. Roulette wheel means that the selection is pseudo-random but chromosomes with higher fitness values have a grater chance of reproducing. The latter method is a closer approximation to the real world, but takes a longer time to yield results. The quality of results from both methods varied only slightly, though in theory, the roulette wheel method should preserve better genes that just happen to have very poor neighbouring genes. As mentioned in the introduction, a more diverse gene pool is better in drastically changing conditions, but for the purposes of these series of experiments, the conditions are quite fixed for the duration of each experiment.

The main aim of the experiment was to derive the algorithm and to find suitable values for its parameters. The algorithm was coded in Borland C++ 4.5 but some of the data processing was done using BASIC programs. The starting population was created randomly from the bigrams using a modified roulette wheel selection. The roulette wheel of generating the chromosomes meant that genes with higher fitness have a greater chance of making it to the new chromosome. It creates a fitter initial population at the expense of the diversity of the

gene pool. The algorithm was left to run until the average fitness of the population exceeded a desired value. Due to changes in the method of determining the fitness value, this desired value changes throughout the experiment. Generally, it was when the average population fitness showed little improvement over a long time.

The population size was quite small too, as early preliminary experiments showed that a large population only served to increase computation time. The rate of mutation was relatively high due to this small population size.

RESULTS

Due to the qualitative nature of the results and the different methods of assessing the quality of the results, no actual values can be presented here to document the progress of the algorithm. The following results are descriptions of the effect of various changes to the parameters of the algorithm described above.

Initially, the results were very hopeful. With slight changes to the fitness-determining rules, the algorithm generated a reasonable sounding piece of music that was quite different from the input. Subsequent runs, however, showed that the algorithm was quite incapable in the required creativity. Other than a few minor variations, the music the algorithm produced was essentially the same.

There are several values we could change at this point of time: the rate and extent of mutation and the rate of crossover. Increasing the rate of crossover only served to lengthen the time required before the chromosome reached the desired fitness level. Increasing the rate of mutation had the same effect but changing either the rate or extent of mutation did increase the extent to which the music from each run of the algorithm varied. This seems to indicate something amiss in the selection process.

The selection process – the method of determining the fitness value and choosing chromosomes for the next generation, also underwent various changes. Starting off from the original roulette wheel selection, the authors also tried to use only the chromosomes possessing the highest few fitness values for spawning the next generation. As stated in the procedure, no significant differences were noted.

The rules for determining fitness changed through the course of the experiment. The problem was that the resulting fitness value could not be used as a basis of comparison between tests, but this was a problem we had to tolerate because of the trial-and-error method we used for this experiment. The rules were developed from the crude one based on a list of probabilities to several rules encompassing duration, pitch, note intervals, key, and frequency of rests. The most significant improvement occurred when the range of songs was drastically reduced from 80 to 5. This narrowed down the number of different styles. It also implied that the algorithm will have to be restricted to composing music from a given “seed” song, somewhat restricting its potential uses.

Another improvement came with the restriction of the note duration and pitches. The note durations were restricted to certain few. This was done by having a lookup table where each duration is assigned a fitness value which is added to the total. Mid-range note durations were favoured – not too long or too short. Dotted notes were avoided too by giving them a lower fitness value in the lookup table.

The pitches were restricted to the middle few octaves by a lookup table, where the closer the note is to the middle octave, the higher its fitness value. Certain pitches were favoured to give the effect of having a fixed key signature for the phrases. In the case of this series of experiments, the key chosen was C Major, thus natural notes were favoured over sharps and flats by assigning them a higher fitness value from a lookup table.

The difference between adjacent note pitches was also restricted to give the phrases more continuity, but this resulted in long series of repeated notes being favoured. This problem was settled by the implementation of another rule which discouraged this.

The relatively high crossover frequencies may be the cause of the relatively homogenous final population that is observed with each run of the program. However, lower crossover frequencies do result in lower average fitness values.

The final rules and their associated algorithms and parameters are listed below:

Determining fitness by frequency of occurrence

Only three sets of bigrams were used for this experiment as the effects of velocity (volume) could not be demonstrated on the hardware we used. The three bigrams used were pitch-pitch, duration-duration and pitch-duration. By checking each note in the phrase with the corresponding entry in the bigram, a frequency of occurrence obtained. Each of the three values were multiplied by a factor specific to each one – 0.015 for pitch-pitch occurrences, 0.010 for duration-duration and 0.005 for pitch-duration. The total for the whole phrase was calculated like this.

Notes should not be too far apart

Each semitone corresponded to one unit and Middle C had the value of 72.

The function is as follows:

GENERATING MUSIC THROUGH GENETIC ALGORITHMS

Where x is the fitness value for a given note, and p and p’ are the pitches for the current and the following note respectively.

Notes should not be too long

Each note duration was checked against a lookup table and 0.050 was divided by the value found. The values for the table are as shown:

Note Value

Demisemiquaver 25

Semiquaver 15

Quaver 10

Crotchet 5

Minim 10

Semibreve 30

Breve 40

Dotted demisemiquaver 30

Dotted semiquaver 30

Dotted quaver 30

Dotted crotchet 20

Dotted minim 15

Dotted semibreve 20

Dotted breve 30

Table 1

Notes should be in C Major

The position of each note within an octave was derived using a modulo function given that there are 12 semitones in an octave. This would give C a value of zero. The resulting value was used to reference a lookup table and 0.020 was divided by the value in the table to give the fitness value. The table is shown below:

Note Value

C 10

C# 40

D 15

D# 40

E 20

F 10

F# 30

G 10

G# 40

A 15

A# 25

B 20

Table 2

It can be observed that not all the notes in C Major are equally favoured.

These values are the result of modifications to them at our discretion.

Notes should be near the middle octave

The procedure is somewhat similar to the one above, but this time, the octave is located by dividing the note pitch by 12 and the constant numerator is 0.015. The lookup table values are as follows: 50, 40, 30, 20, 8, 5, 8, 20, 30, 40, 50, 60, with the lowest octave first.

Notes should be of the correct intervals

Each interval was determined by having the difference of the two adjacent notes’ pitches modulo 12. This was then used to find a value in the lookup table. The resulting fitness value is 0.025 divided by this value. The sum was then taken for the whole phrase. The lookup table is as follows:

Interval Value

None 50

Minor 2nd 60

Major 2nd 60

Minor 3rd 60

Major 3rd 60

Perfect 4th 20

Perfect 5th 15

Minor 6th 60

Major 6th 30

Minor 7th 60

Major 7th 50

This implementation of the table allows for keys other than C Major.

Notes should not be the same

For each consecutive repetition of a note, 0.100 is subtracted from the fitness value of the whole phrase.

CONCLUSION

Genetic algorithms can be used, to a limited extent, to generate music. The music is strongly influenced by the statistical data input and does not vary significantly even with the changing of other factors. Thus we have met the main aim of generating music using a genetic algorithm, but have not been able to meet our goal of obtaining simulated creativity.

There are many ways in which this experiment can be improved upon. Due to time limitations, we were unable to test the algorithm with different groups of songs for the

statistical analysis. Other types of music could be attempted too – pop, rock, country, or even Eastern or Oriental music. The algorithm was designed to compose only short phrases, but a simple modification could yield another algorithm that can manipulate and combine these phrases to give a complete song. A more extensive set of rules could be set to ensure better music. We had even considered implementing an artificial neural network (ANN) to determine the fitness value. The level of complexity of the music generated could be increased by allowing the algorithm to generate songs with chords. As suggested in the introduction above, the algorithm could be modified to compose music to fit a certain mood or set of lyrics.

REFERENCES

David B. Fogel, Evolutionary Computation, 1995, IEEE Press

John R. McDonnell, Evolutionary Programming IV, 1995, The MIT Press

Scott Robert Ladd, Genetic Algorithms in C++, 1996, M&T Books