Page  501 ï~~Genetic Algorithms as a Tool for Melodic Development David Ralley University of Illinois Department of Computer Science, 1304 Springfield Ave., Urbana, IUl., 61801 david@cmp-rs.music.uiuc.edu Abstract:One of the fundamental challenges of music composition is the development of existing material. Melodic development is often described as an organic process in which key characteristics of a melody are rearranged, isolated and permuted to form new material. This paper explores the possibility of using an interactive genetic algorithm as a means for developing a user supplied melodic idea. Results are mixed, showing the limitations of the human echoic memory in interactive aural evaluations. 1 Introduction The process of musical composition has at its core two problems, one of which is common to other artistic endeavors-discovery of novel and interesting material, and one which is more unique to music-the processing of ideas through systematic permutation and recombination of themes. The fact that variations of a musical idea play such an important role in serious music, and that these variations are somehow derived through recombination and mutation of original material suggests that the process of finding developmental material from extant melodies might be a problem that could be undertaken by a genetic algorithm (GA). The reader is refered to Goldberg (1989) for details of GA construction and operation. 2 Related work Hartmann (1990), McIntyre (1993), Putnam (1994) and Homer and Goldberg (1990) have all made use of GA techniques for music composition. This work builds primarily upon that of Homer and Goldberg, and adds an interactive evaluation process found in Cladwell and Johnson (1990). Iteractive evaluation requires the use of data reduction methods, such as cluster analysis, and in this work the similarity between melodies was done with a simple string matching algorithm that looked for the longest match between two strings of notes. The actual similarity function is: St W,(P)+W2(P;)+W3(P)+W4(P)+W,(P 1) where Stis the overall similarity metric, P is the prime pitch similarity, P is the inverted pitch similarity, P= is the retrograde pitch similarity, P. is the retrograde inversion similarity, Pl is the relative pitch similarity, and W1W5 are the user supplied weights for evaluation. Relative values deal with the distance between two successive elements in the underlying alphabet. 3 Representation The representation of melodies includes two parts, a header, and a list of melodic events. Notes are stored as intervallic offsets from some starting pitch and starting index in an alphabet, which are specified in the header. Assuming that alphabet 0 is a major scale Mary Had a Little Lamb, shown in figure 1, would be represented by: (7160)(0-1-1 1 100-100120) The header information shows that this melody begins on note 71 (B above middle C), which is the sixth note of scale 0. Most mutations alter a single bit, changing one note into an adjacent note in the alphabet.Iif the bit happens to be in the header, can change the entire pitch content of the individual. Mutations on the body of the string are implemented so that they effect one note, not subsequent notes. Additional mutations can reverse a string, or invert it by multiplying all the pitch offsets by -1. The initial population was seeded with melodies similar to the user's input melody. To do so, some rudimentary spectral analysis was performed, finding the distribution of pitches and intervals in the user's input. This information was then used to determine initial melodies stochastically so that the I C MC P ROC E E D I N G S 199550 501

Page  502 ï~~population retained a certain amount of similarity to the starting melody. Each population is subdivided into some number of clusters, and from each cluster there is one representative centroid chosen. The size of the search space is dependent on the length of the initial melody and the size of the pitch alphabet. The selection scheme uses binary tournament selection with replacement as outlined in Oei et al (1991), which has been to less likely to be susceptible to sampling noise than proportional selection. Reproduction is standard one point crossover. For the test system, all notes were given the same duration, all similarity metric weights were set at.5, and the mutation rate was set to.001. A population size of 100 was used, as this was proportional to the string length and alphabet sized used in the sample input. 4 Experimental Results There were no problems deriving interesting output from recombination and mutation of the user's input. The GA was able to produce a large number of interesting melodic variations of initial material. If anything, the system was too cautious, as there was a propensity toward homogeneity caused by the mediating tendencies of the population seeding mechanism, coupled with the averaging aspects of the clustering algorithm. The real problem with such a system is its subjectiveness. There is no way to really measure the success or failure of such a system if the solution the user desires is not predetermined, and the acceptability of the final melodic material is entirely up to the user. 5 Summary & Conclusions This paper raises more questions than it answers. Some of these questions have to deal with algorithmic decisions made during the course of the experiment: would niching be a more effective means of data reduction than clustering? Could increasing tournament size during selection increase the speed and efficiency of the search? Could the distance between an incorrect element in a string and the correct one in the alphabet be used to guide the proper mixing of notes in the melodies? This system could easily be expanded to cover any aspect of musical language that can be quantized into a dictionary. Rhythm is one such obvious extension, but it is not inconceivable that timbre might also be developed using GA techniques. Although this research calls into question the ability of a human evaluator to guide a musical GA through melody space to an explicit goal, it does show that a GA can be used as a tool for music composition, either though interactive evaluation and subjective success, or through algorithmic evaluation towards a single goal state. A more complete version of this paper is available at http://cmprs.music.uiuc.edu/--david/icmc.ps. References Cladwell, C., & Johnson, V.S. (1991). Tracking acriminal suspect through "face space" with a genetic algorithm. Genetic Algorithms and their Applications: Proceedings of the Fourth International Conference on Genetic Algorithms, 416-421. Goldberg, D.E. (1989). Genetic alroithms in search, optimization and machine learning. Reading, AddisonWesley. Hartmann, P. (1990). Natural selection of musical identities. Proceedings of the International Conference on Computer Music, 103-106. Homer, A. & Goldberg D. E. (1991). Genetic algorithms and computer-assisted composition. Genetic Algorithms and Their Applications: Proceedings of the Fourth International Conference on Genetic Algorithms, 437-441. McIntyre, R.A. (1993). Bach in a box: the evolution of four part baroque harmony using the genetic algorithm. In J. Koza (Ed.) Genetic Algorithms at Sta'nford 1993 (pp. 135-144). Stanford: Stanford University Press. Oei, C.K., Goldberg, D.E. & Chang, S-J. (1991). Tournament selection, niching and preservation of diversity. (LUiGAL Report No. 91001). Urbana, Ill.: University of illinois at Urbana-Champaign. Putnam, L.B. (1994) Genetic programming of music. Unpublished manuscript viewed April 20, 1995 at http://nmt.edub-jefu/notes.htinl. Yin, X., & Germnay, N. (1993). A fast genetic algorithm with shadrig scheme using cluster analysis methods in multimodal function optimization. Artif icial Neural Nets and Genetic Algorithms: Proceedings of the internat ional Conference, 450-457. 502 ICMC PROCEEDINGS 1995