Page  00000001 Evolving Decentralized Musical Instruments Using Genetic Algorithms Assaf K. Talmudi Institute of Sonology and Department of Composition, Royal Conservatory, The Hague, The Netherlands Abstract Western music's reproduction paradigm is based on one important dualism: the functional and hierarchical distinction between score and instrument, between a unit of sequential memory and an execution unit. This paper presents computer experiments using physical modeling and evolutionary computation schemes aimed at exploring designs of decentralized mechanical music instruments: instruments whose large-scale musical behavior is solely the result of local physical interactions between simple elements. In a decentralized mechanical instrument, musical memory is an emergent global property of the system, indistinguishable from the execution process. Such a system is both a score and an instrument. The paper starts by discussing the difference between sequential memory systems and systems exhibiting emergent decentralized musical behavior. Next, the use of particle system simulation for exploring virtual decentralized instruments is demonstrated. The paper continues by showing how a genetic algorithm was used to evolve decentralized instruments so as to reproduce a given musical behavior. Key Words: Emergent phenomena, Decentralized Instruments, Genetic Algorithms, Particle System Simulation. 1 Rise and Fall of the Autopiano Before approaching the subject of decentralized instruments it might be helpful to consider the apogee of hierarchical, centralized instruments: the pianola. Invented in the late 19th century, the pianola (also known as the player piano) is best described simply as a self-playing piano. In a Pianola, a traditional piano is fitted with a pneumatic mechanism that controls the movement of the piano keys. Figure 1: a pianola advertisement from the beginning of the 20th century. The paper roll containing the music score is seen in the middle of the upper part of the instrument (picture: The music score is represented by tiny perforations on interchangeable rolls of paper, which move over a cylinder with slits, one slit for each key. Pressurized air passing through the perforations in the paper roll moves the keys according to the score. In order to reproduce a piece of music, all that is required from the user of a pianola is placing a paper roll - on which the score of a specific music piece is encoded - on the cylinder and then using the two foot-pedals to generate the air pressure as needed. Although it enjoyed commercial success in the first decades of the 20th century, the pianola never became an important tool for music making (with the exception of music by Conlon Nancarrow). Even as a means of commercially distributing music the pianola enjoyed only a short-lived success, and was rapidly driven to extinction by the introduction of the phonograph. As a musical instrument, the pianola became a collector's curiosity, but as a mechanical manifestation of an important paradigm of western music reproduction, the pianola is still relevant. Proceedings ICMC 2004

Page  00000002 2 Score/Instrument Dualism With its paper rolls acting as a soul, and its pneumatic and acoustic mechanisms acting as a body, the pianola is a perfect mechanical representation of score/instrument dualism - a fundamental concept in the history of Western music reproduction. According to this concept the reproduction of music depends upon the workings of two distinct units: a sequential memory unit - a score, and an execution unit - an instrument. These two units are connected by a one-way linear translation mechanism. The instrument itself is considered as capable of executing only isolated local musical events. The temporal arrangement of these events is created in advance, appropriately encoded and stored as a score to enable performance at a later time. During music reproduction, the score is decoded sequentially and translated into actions of the instrument. A quick glance at the history of western music will reveal that this dualism was refined considerably during the last four hundred years: A comparison of a 17t century opera score by Monteverdi and a 20th century opera score by Strauss may easily serve to show the historical process by which the score has become a more detailed and less ambiguous sequential description, while the instrument is asymptotically approaching the capability of neutral execution. The score/instrument dualism has proved to be an immensely powerful concept and has made possible the great developments and achievements of western music over the last five centuries. Distribution of musical knowledge, the study of music and the possibility of coordinating large groups of musicians are all to some extent dependent on this dualistic and hierarchical paradigm of music reproduction. But this dualism has its limits, both as an approach towards generating music and as an analytical tool. These limits have been exposed by developments in music during the last century. Many forms of twentieth century music have been consciously or unconsciously challenging the validity of the dualistic hierarchical model of music reproduction, the obvious examples being improvised music and electronic music. The instrument/score dualism has also proved to offer little possibility for interaction with a piece of music, a question addressed by many musicians in the computer music world. I would now like to add another challenge to this dualism, this time attacking the score-instrument dualism at its mechanical core. 3 Sequential vs. Emergent Memory What will a mechanical music instrument that does not obey the instrument/score dualism look like? As a matter of fact, many such instruments already exist. Consider windchimes hanging from a window: when a light breeze blows through the chimes the chimes start colliding with each other and a melody is produced. Where is this melody stored? Explicitly it is not stored anywhere in the system. Implicitly, it is stored everywhere through the system. This melody is an emergent phenomenon arising as a result of the interactions between chimes, wind, gravity and all the other elements comprising the system. Which is exactly the problem with wind chimes as an example of a decentralized music instrument: depending on the point of view, it is either infinite in size, comprising of every particle in the universe, or else it contains a stochastic element (these two statements do not in fact contradict each other, remembering that truly stochastic systems are infinite in dimensions). However, by means of computer simulations, it is possible to investigate the properties of much simpler systems that exhibit a behavior similar to wind chimes but do not contain any stochastic element. Using computer simulations of a system that obeys simple Newtonian physics, I will sketch a basic architecture for such an instrument. (For additional treatment of the topic of music and emergence see, for example (Miranda, 2000).) 4 A Basic Decentralized Instrument 4.1 Particle System Simulation For the purpose of exploring simple designs of decentralized mechanical instruments I use the technique of physical modeling by way of particle system simulation. The technique allows the simulation of a Newtonian physical system in real time using a digital computer, and has been applied to sound synthesis and control by several recent authors, notably in (Muth and Burton, 2003) and (Castagne and Cadoz, 2000). Within the framework of the computer simulation, three basic building blocks will be used in constructing all the following instruments: 1. A bell, simplified and modeled as a particle with a fixed mass. In the model, a bell rings, e.g. plays a sound sample, when its acceleration reaches a peak and that peak is above a preset threshold. 2. A spring with a specific spring coefficient K. 3. A fixed point These building blocks are combined into structures in a two-dimensional space, which is assumed to have small friction and no gravity. Bells may be connected to other bells or to a fixed point with springs. An external impulse can be exerted to one bell to set the system in motion. The behavior of the system is then simulated by the numerical solution of the governing set of ordinary differential equations, using the simple Euler's Method (Gershnfeld 1999). During the simulation, peaks in the acceleration of the dfferent bells are found and a bell sound with an appropriate pitch is played when a bell in the model rings. The simulation runs in real time, offering audible and Proceedings ICMC 2004

Page  00000003 visual representation. Thus a music machine constructed out of bells and springs can be designed, simulated and its audible result can be examined. 4.2 Initial Designs and Results fied.~~) Slhqg. K z iknw s C Bell Figure 2: the simplest mechanical music instrument The first instrument is the simplest possible (figure 2). It is composed of a single bell, which is tuned to the note C. The bell is connected by a spring with spring coefficient KI to a fixed point. At time to, an external impulse force is exerted to the bell. Imagine listening to such a device. What melody will it play? Since the bell is going up and down and the acceleration is oscillating periodically, it will simply repeat the note of C at a constant tempo, gradually getting softer, loosing energy as a result of friction until the notes die out (figure 3). Figure 3: the melodic impulse response of the system shown in figure 2. Throughout the rest of the paper I will refer to the perceived musical behavior of such a system, as the melodic impulse response of the system. This term describes the melody that the instrument plays when the C bell is hit with an impulse. A melodic impulse response will be given in traditional music notation. Note that the melodic impulse response of an instrument is related to the physical impulse response, but the two are not identical. A melodic impulse response is best thought of as the melody one would hear if one were to strike the C bell slightly. The next step is to build a slightly more complicated music machine by adding another bell, tuned to D, and connecting it both to the first bell and to the fixed mass (figure 3). Hitting the C bell with an impulse will produce the following response: Figure 5: the melodic impulse response of the instrument shown in figure 4 The exact periods of the notes will depend on the spring coefficients K,, K2, K3 and on the friction. *A Figure 6: a two octave music instrument, only 11 springs out of 264 are shown Now consider two chromatic octaves, or 24 different bells (figure 4). Each bell is connected to 10 neighboring bells, and all are connected to the same fixed point (only the first 11 connections are shown in the diagram). In the next simulation the spring coefficients are randomly distributed between 0.1 and 5.0, all masses are equal to 1.0, and friction is set to 0.9999. Hitting the C bell with an impulse and running the simulation for 1000 steps yields the following melodic impulse response: Figure 7: the melodic impulse response of the instrument from figure 4 Listening to the result of such a model makes it clear that it has a very rich musical behavior, which on the one fixed point spring D Bell C Bell 3 Figure 4: a slightly more complex instrument Proceedings ICMC 2004

Page  00000004 hand is not periodic but on the other hand does not sound like a random sequence (sound examples can be obtained from the author). Two interesting facts arise while considering the richness of the musical behavior generated. The first is that the musical behavior depends only on local mechanical interactions between the parts, and is not directed by high-level rules; Although it clearly contains certain melodic and rhythmic motives (rhythm is not notated above to avoid a much more complex figure), these are generated bottom-up, without any global coordinating mechanism. The second interesting fact is that the interaction is deterministic. No stochastic processes are needed for generating such a rich behavior. Given the same configuration of spring coefficients, the sequence can be precisely reproduced. In the case of the pianola, the melody was stored on a roll of punched paper, and instructions were translated into musical phenomenon. In the case of the melody above, it is quite hard to say where it is stored, although from the fact that it can be accurately reproduced one has to agree that it is stored somewhere, somehow. In the system above, the memory unit can not be distinguished from the execution mechanism. The instrument and the score are in fact just two different ways of looking at the same object. Changing the instrument, for example by changing some of the spring coefficients, will change its "score" - its large-scale musical behavior. I now have the basic design for a two-octave decentralized mechanical music instrument, capable of some global behavior. The next step is to ask whether it is possible to tune such an instrument, for example by finding specific configuration of spring coefficients, so it will exhibit a given global musical behavior. Is it possible to design an instrument that will play in C major? Or one that, when hit, will play the Star Spangled Banner? In other words, can emergent behavior of a system be harnessed, or "'tuned", to a specific musical goal? Although the idea of providing the white house with a mechanic sculpture that will spontaneously play the American anthem is pleasing, It might prove to be, just like the white house, too ambitious. Therefore I will concentrate on one specific characteristic. One possible global characteristic of a music fragment is the note distribution in the fragment. For a fragment containing N possible different pitches {X1,X2...,X,}, the probability of pitch xi: is found by counting the occurrences of the note in the fragment and dividing this number by the total number of notes in the fragment. For example, the note distribution in the melody of The Star Spangled Banner is given in figure 8. The next section will describe the use of a genetic algorithm to design an instrument that will exhibit the same distribution of notes as that of The Star Spangled Banner. The use of GA in this context is motivated by the fact that a direct design approach will not work in this case, since the higher-level outputs of the system (the melodic response) is not directly predictable from the input for the model (the spring coefficients). A GA offers an efficient way of searching the vast and multi-dimensional space of possible spring configuration. \\ 4 ",l J " II -" J W " I0 I II I"0 - (a) m CL cl c#1 dl d#1 el fl f# gl g#1 al a#1 bl c2 c#2 d2 d#2 e2 f2 f#2 g2 g#2 a2 a#2 b2 note (b) Figure 8: (a) the first nine bars of The Star Spangled Banner by J. Stafford Smith (b) the note distribution in the same melody. 5 Evolving Instruments With a GA Genetic algorithms (Koza, 1992) (Mitchell, 1998) is a common name for a family of evolutionary-inspired methods that have shown to be highly effective for searching vast multi-dimensional possibility spaces. GA's have been used to evolve emergent decentralized computation systems (Mitchell, Crutchfield and Das, 96), and to several musical problems ((Biles, 94) being one of the first famous attempts; (Todd and Werner, 99) offer further discussion of the subject)). In the following experiment, a genetic algorithm was used to evolve mechanical music instruments to exhibit specific note probability distribution in their melodic impulse response. The target note distribution was chosen to be the note distribution of The Star Spangled Banner. During a GA run, a population of instruments is searching the space of possible configurations of spring coefficients. Each candidate instrument in the population is constructed according to its genome, its list of spring coefficients. This instrument is then played, and an assessment of its statistical similarity to the target melody is made. Candidates that exhibit higher similarity to the target melody have higher chances to survive and reproduce Proceedings ICMC 2004

Page  00000005 5.1 Population A population is defined as a group of candidate instruments. All the instruments in the population are of the form depicted in figure 4, each constructed out of 24 bells of different tones, or two octaves. Each bell is connected to 10 neighboring bells and to the fixed point. In total there are 264 springs in an instrument. Different instruments have different configurations of spring coefficients. The description of an instrument, its genome, is simply a list of 264 spring constants, represented as a list of 16bit floating point numbers. This list describes the coupling between the bells in the machine. That is not to say that all the springs are actually contributing to the dynamics and to the melodic impulse response. During the evolution of the population, the value of some spring coefficients can become as small as being practically zero, and have no effect on the behavior of the instruments. 5.2 Fitness Evaluation For each candidate instrument, the melodic impulse response of an instrument is obtained: given a list of 264 spring coefficients describing an instrument, a model of the instrument is constructed. An impulse force is then exerted to the C bell and the simulation is calculated for 1000 time steps, with friction set to 0.999, and the sequence of notes played by the instrument is collected. From the melodic impulse response of the candidate, a note probability distribution P(inst) is calculated. The fitness of a candidate instrument is defined to be the mean square difference between P(nst) and the note probability distribution of the target melody P(target).A low fitness means a good correspondence between the distribution of notes in the melodic impulse response of the instrument and that of the target melody. For example, in The Star Spangled Banner there is no occurrence of the note Eb. An instrument whose impulse response contains Eb will have a higher fitness, and so will be less likely to reproduce and survive than an instrument with the same impulse response only without the Eb. (To a biologist, as to most people, high fitness will sound positive, however, when using evolutionary schemes to obtain similarity between elements, it makes more sense to calculate the distance from the target, resulting in high fitness being negative.) 5.3 Selection and Reproduction The genetic algorithm uses an elite selection mechanism, in which for each generation, only a fraction of the population, containing the instruments with the highest fitness, is chosen for survival and reproduction. This fraction was set to be 20 percent in the experiment. From this elite group, random pairs of candidates are combined to produce new candidates. Each point in the new candidate's genome is randomly chosen from either one parent or the other. The resulting new candidates are then mutated. Since the genome is comprised of floating point numbers, a distinction is introduced between the chance of a point in the genome to be mutated and the range of possible mutation. The mutation process randomly selects a fraction of the points in the genome, the mutation percentage, each chosen point is then multiplied by a random value between 0.0 and the mutation factor. 5.4 Results The genetic algorithm experiment was ran for 800 generations, with a random initial population of 1000 candidate instruments. The elite fraction was set to be 0.2 (meaning 200 individuals of each generation are kept, while 800 new individuals are created), mutation chance (the probability for a spring coefficient to be changed in the new generation) was set 0.1, and mutation range was 0.9 (meaning the mutation can range from 0.1 to 1.9 of the original value). Several runs of the experiment exhibited similar results. As expected, during the first generations, no member of the population exhibited much statistical similarity with the target melody (if it did it would have been by pure chance.) 0,09 0,08 0,07 0,06 S0,05 0,04 0,03 0,02 0,01 1 51 101 151 201 251 301 351 401 451 501 551 601 651 701 751 generation Figure 9: best fitness per generation for a GA run of 800 generations During the first generations, instruments with only the slightest resemblance to the target melody are taking over the population (figure 10b). At different points in the run, evolutionary leaps appear. Both mutation and sexual reproduction appear to be contributing to these leaps, with sexual reproduction appearing to be responsible for the bigger leaps. After 800 generations, an instrument with high statistical similarity to the target melody is found (figure 10c). Some runs have evolved instruments exhibiting note distributions that were almost identical to the target distribution, achieving fitness values as low as 0.002, with less than one percent of the notes outside the desired distribution. Listening to the result of such an instrument makes it clear that it bears statistical resemblance to the Star Spangled Banner. Proceedings ICMC 2004

Page  00000006 0,15 2 0,1 Q. s g s a ua g note note (a) 0,08 0,07 0,06 0,05 | 0,04 - 0,03 0,02 0,01 1:~:~I 1:~:~I i note memory. The experiment described evolved instruments that reproduce a given note distribution. It is likely that other high level musical features can be implemented in an instrument using the same approach, depending solely on the inventiveness of the researcher, success in expressing an effective fitness function and available computation resources. In order to explain the potential relevance of these results, it is convenient to go back to the pianola once more. Consider a melody reproduced by a pianola and the same melody reproduced by a decentralized mechanic instrument made of springs and bells. What is the difference in the way in which the two instruments accomplish the same task? In the case of the pianola, the melody is fully encoded in a temporal manner in the perforations of the paper roll which functioning as a central sequential memory unit. The reproduction process does not depend on the melody, indeed it is indifferent to the melody. The decentralized instrument does not have such a memory unit. Musical reproduction is achieved because the dynamics of the instrument are to a certain extent analogous to the dynamics of the original melody. The instrument captures the dynamics of the melody. When wind chimes are hit by wind, a melody emerges. When people sing together, a melody emerges. Intuitively and traditionally, we think of the two processes underlying the two melodies as being very different. We explain the melody of the wind chimes in terms of the dynamics of the physical system involved. When we think of a human song we tend to think about it in terms of higher-level cognitive and cultural concepts such as musical context, musical syntax and so on. The idea of a decentralized music instrument, whose melody is just an emergent property of its simple dynamics does not need such concepts. Even at the current heuristic stage, the simulation of a decentralized music instrument suggests that the conventional instrument-score dualism might be a wise practical choice at times, but is not an inevitable one, and certainly not one that has to influence us too much when we are contemplating the basic phenomenon of music. Indeed in a decentralized instrument the distinction between the two fundamental elements of a musical performance becomes blurred. In doing so, it suggests a non-syntactic causal approach to music creation and analysis, which might shed further light on the processes underlying music creation and music appreciation. (b) 0,18 0,16 0,14 - 0,12 | 0,1 Q.. 0,04 0,02 note (c) Figure 10: (a) note distribution of the first nine bars of The Star Spangled Banner by J. Stafford Smith. (b) note distribution of the best instrument after 800 generations, with fitness 0.002 (c) note distribution of the target melody, compared with figure b the increase in similarity is visible 7 Acknolwledgments 6 Conclusions In this paper I have shown that using computer simulations and genetic algorithm strategies it is possible to design a simple mechanical instrument which reproduces a certain global musical behavior without the need of a central coordination unit, or any kind of sequential Parts of the research discussed in the paper were carried at the Santa Fe Institute during the Complex Systems Summer School, June-July 2003. I would like to thank Tom Carter and Neta Cohen who provided advice and guidance in designing the experiments, and Eytan Kazav, Paul Berg, Proceedings ICMC 2004

Page  00000007 Jonathan Shapiro, Peter Todd and David Calef for discussions and criticism of the paper. References Biles, J., GenJam: A genetic algorithm for generating jazz solos. In Proceedings of the 1994 International Computer Music Conference (ICMC'94), Aarhus, Denmark, International Computer Music Association, 1994. Castagne, N. amd Cadoz C., Phyiscal Modeling Synthesis: Balance between Realism AND Computing Speed,. In Proceedings of the COST G-6 Conference on Digital Audio Effects (DAFX-00), Verona, Italy, 2000 http,:4/ i un iv /-d af /F inix b ~ is ~dfCas~oi AD. xJ000.)f Gershenfeld, N., The Nature of Mathematical Modeling, Cambridge, MA, Cambridge University Press, 1999. Koza, J. R., Genetic Programming: On the Programming of Computers by Means of Natural Selection. Cambridge, MA: MIT Press, 1992 Miranda, E., The Music of Emergent Behaviour, What Can Evolutionary Computation Bring to the Musician, www~wcsLso-ny-fr/downl(-)sr-id rs/20O-ni t e 02000.df, 2000 Mitchell M., An Introduction to Genetic Algorithms (Complex Adaptive Systems), Cambridge, MA.,MIT Press, 1998. Mitchell M., J. P. Crutchfeild, and R. Das, Evolving cellular automata with genetic algorithms: a review of recent work. In Proceedings of the First International Conference on Evolutionary Computation and Its Applications (EvCA'96). Moscow, Russia: Russian Academy of Sciences, 1996. Muth D., E. Burton, Sodaconductor. In Proceedings of the New Interfaces for Musical Expression (NIME'03), Montreal, Canada: McGill University, 2003. Todd, P.M., and Werner, G.M., Frankensteinian approaches to evolutionary music composition. In N. Griffith and P.M. Todd (Eds.), Musical networks: Parallel distributed perception and performance (pp. 313-339). Cambridge, MA, MIT Press/Bradford Books, 1999. Proceedings ICMC 2004