Weston Cann and Dr. David Michael Cottle, Mathematics
Currently, there is a wide variety of computer applications available for aiding musicians. Most common are applications whose purpose is to help render the performance of a piece (sequencers) or help the user prepare the score of a piece. Less common are applications designed to aid the composer in exploring musical possibilities. This project is an attempt to add to this second body of applications.
The specific aim of this project was to create a computer program that would take a melody and create a harmonization for it. The application utilizes techniques from computer science known as genetic algorithms. These algorithms operate on a set of randomly generated possible solutions to a problem, dubbed a population. Each member of the set is evaluated in terms of its fitness as a solution to the problem. Processes analogous to evolution and natural selection are repeatedly applied to the population in an effort to increase the fitness level of each member, hopefully producing a few individual solutions whose quality renders them an optimal solution to the problem. In the case of this project, the population of solutions is a set of possible harmonizations to a given melody.
This program was designed using Macintosh implementations of the C programming language – first Symantec THINK C, and later Metrowerks CodeWarrior. It grew out of work begun in a course in computer programming and composition, taught by Dr. Cottle (faculty mentor, noted above) at Brigham Young University during winter semester 1995. Portions of the program as it now stands were developed for a course in genetic algorithms, unofficially attended at Utah State University during summer quarter 1995, taught by Dr. Nicholas Flann. The first functional version was completed in April 1996. Four areas of program design will be discussed in this report: how the melody is input, how the harmony is output, the type of genetic algorithm used, and the criteria used to determine the fitness of a harmonization.
The melody to be read is stored in a standard text file, read at runtime. The program also asks the user which key the melody is written in. Each note in the melody is represented by a string of characters which signifies its pitch and duration. Pitch is represented in a natural way: “G#” represents a G sharp, a “B” represents a B, etc. No consideration is made for the octave the pitch is in. Representation of duration is somewhat less intuitive, but was selected to simplify programming. A “1” stands for an eighth note, a “2” for a quarter note, a “4” for a half note, and so on. Under this scheme, “C# 2” would represent a C sharp with the duration of a quarter note. Each string of characters representing a note should be separated from other note strings by a space.
As output, five possible harmonizations for the given melody are stored in a standard text file. These harmonizations are represented by a string of the numbers 1-7. Each number represents a standard triad/chord relative to the key the melody is in6- for example, a “5” would represent the triad CEG in the key of F. Note that these numbers correspond to the Roman numerals commonly used to notate harmonic progressions in music; thus, the “5” mentioned above would be commonly notated as “V”, and referred to as the dominant. Each chord is assigned the duration of a single beat in a piece. For simplicity, this was assumed to be one beat per quarter note for all melodies processed by the program.
The genetic algorithm used in this program was modeled after a “simple genetic algorithm,” but altered slightly to include a process known as “crowding.” The process begins by randomly generating the population of possible harmonizations; in this program, the population size is 100. The fitness level of each member of the population is then calculated. A number (26 in this case) of these harmonizations are randomly selected, and members of this subpopulation are crossed with one another to produce new harmonizations with elements of the old in them. Each member of the new subpopulation replaces the member of the entire population most similar to it if the new one has a higher fitness level; similarity is measured by the number of identical chords in the same position of the harmonizations. A mutation is then introduced into each harmonization by randomly changing one of its chords to another. The fitness of each member is recalculated, and the entire process is repeated until the average fitness level of the population is not noteably improved by repetition, or until some number of repetitions have been completed.
Determining the fitness level of each harmonization is somewhat problematic; the question “What makes good harmony?” can be difficult to answer. Five criteria were selected, and a certain amount of fitness points awarded to each harmonization meeting them. A harmonization receives: 1) 30 points if its last chord is “1”, the tonic; 2) 1 0 points if its first chord is ” 1 “, the tonic, or “5”, the dominant; 3) one point for every chord that is different from the last n chords (n is given by the user at the start of the program); 4) one point for every chord which contains a note from its corresponding point in the melody.
How successful is this program at realizing its goal? From a traditional standpoint, the current version of the program produces harmonies that are much less satisfactory than the work of the average first year music theory student. However, the harmonies produced did follow a natural cadence at times, and when they didn’t, the sense of polytonality was mild and pleasant. Jarring changes typical of more purely random methods were avoided. The project has been semi-successful; however, it seems that further consideration is necessary. For example, while the fitness criteria were carefully chosen, the amount of points given to a harmonization for meeting them was somewhat arbitrary. It may be that experimentation with these parameters is all that is needed to make the program more effective at realizing its goal. So reflection on whether or not such an algorithm as the one used here can be effective at musical tasks may be premature. Underway are changes to the program to investigate the possibility of greater success. 2
References
- Goldberg, David E. 1989. p. 10- 14, 116. Genetic Algorithms in Search, Optimization, and Machine Leaming, Addison-Wesely
- The author wishes to gratefully acknowledge the programming assistance of David Brian Walton, the instruction received from Dr.
Flann at USU, and especially the support of Dr. Cottle and the composition faculty of BYU during this project.