Page  274 ï~~GeNotator An Environment for Investigating the Application of Genetic Algorithms in Computer Assisted Composition. Kurt Thywissen Hong Kong University of Science and Technology Kowloon, Hong Kong kurt@cs.ust.hk Abstract A computer assisted composition tool for investigating the application of evolutionary techniques, particularly Genetic Algorithms, in the composition of music is presented. The nature of such an application is examined, taking inspiration found in natural evolution, genetic algorithm theory and similar aesthetically based, but nonmusical uses of a genetically based search heuristic. A formal model of "musical evolution" is presented, with particular attention paid to the ways in which a genetic algorithm can be used to effectively manipulate compositional structures within a hierarchical model of composition. The result is a prototype application called GeNotator, which allows the composer to experiment with various musical structures by evolving them with a genetic algorithm, and subsequently generate audio in either of two standard formats: Csound and MIDL 1. Introduction Composing music is a creative process, and like any creative process, it can be described in terms of an aesthetic search through the space of possible structures that satisfy the requirements of that process; in our case, creating interesting music. Compositions tend to exhibit varying degrees of structure, where the composer labours by crafting and evolving initial ideas into satisfying end products. Richard Dawkins, in The Blind Watchmaker [Dawkins, 1986], describes lucidly how objects of apparent high structure (living organisms) can come about via evolutionary principles rooted in natural selection. He also extends this notion to a form of Universal Darwinism [Plotkin, 1995] whereby the creative generation of intellectual ideas themselves derive from such a process of iterative refinement of competing ideas, or "memes" as he likes to call them. The success of employing evolutionary techniques in artistic endeavours is best exemplified by the work of William Latham and his Mutator and Form Grow systems for evolving 3D computer sculptures [Latham et al., 1992]. His results can only be described as extraordinary, surreal and distinctly organic. Latham observes, "The machine has given me freedom to explore and create complex... forms which previously had not been accessible to me, as they had been beyond my imagination." Inspired by the work of Dawkins and Latham, GeNotator is an attempt at transferring these evolutionary concepts to the domain of music making. Its main "evolutionary" mechanism is the Genetic Algorithm (GA) [Goldberg, 1989], which has proven to be a very effective way of blindly seeking out acceptable candidate structures from large search spaces. In GeNotator, the GA is used to guide the composer through the search space of possible compositions. 2. Background GeNotator was originally conceived as a Masters thesis in 1993 [Thywissen, 1993], written in C++ on an SGI. It built off an experimental application called MuTonator [Thywissen, 1992] - a simple MIDI-based tool for evolving tone-rows using an iterative fractal approach. At the time only Horner [Horner et al., 1991 ] had detailed the use of GAs in computer assisted composition, specifically their use in thematic bridging. Since then, their popularity in computer music in general has grown - now found in various applications from instrument design [Horner, 1993], to searching for near-optimum synthesis parameters for matching instruments [Horner, 1995], and other computer assisted composition systems [Jacob, 1995]. For those unfamiliar with GAs and how they are typically used in composition, the following is a brief introduction. GAs operate on populations of chromosomes (genotypes), each a codified competing "solution" whose genetic content is mapped onto the problem domain via a domain-specific representation scheme (RS). This RS allows candidate genotypes to be decoded into domain specific solution candidates (phenotypes) and then be assigned a relative fitness score via a so called fitness function. In traditional GA usage, fitness is an objective function that evaluates how closely a given phenotype approximates (or attains) an ideal solution in the problem domain. Typically, the GA starts by generating an initial random population of chromosomes. This population then undergoes evolution where pairs of chromosomes are picked to exchange genetic material via a process called crossover. Crossover is the mechanism that allows offspring to inherit and combine genetic material from their parents. Fitter chromosomes tend to be selected for crossover over inferior ones in a way that is proportional to chromosomal fitness. Another genetic operator is mutation where chromosomes occassionally can have a randomly selected gene altered, thus adding new genetic material to the gene pool. Through this iterative process of crossover and mutation, less fit genetic material gradually dies and fitter genetic material propagates to subsequent generations. This continues until sufficiently "superior" chromosomes evolve which marks the point of termination of the GA. In computer music, the challenge is to find a representation scheme which maps the chromosome makeup to musical entities such that music can be "evolved". The objective fitness function is usually reinterpreted as subjective where instead the composer's taste and judgment dictate the relative success rate of competing musical structures represented by the chromosomes. As Biles[1994] observes, this is often the "bottleneck" in a GA-based system as GAs typically operate on relatively large populations of candidate Thywissen 274 ICMC Proceedings 1996

Page  275 ï~~chromosomes, each of which must be evaluated by the listener. One way to minimise this population explosion is to concentrate on defining higher level generative processes that are parametrically controlled; it is then these parameters which are evolved by the GA. The generative processes thus define boundaries to the composition's form space, within which the GA can evolve interesting parameter combinations. This is certainly the case with Latham's work [1992], where the user is typically given only 9 items to select between at each iteration of evolution, yet each of those nine items already exhibit a high degree of pre-defined structure (as opposed to purely random starting conditions). Other computer music approaches effectively also do this, where the generative processes drive either melodic development [Ralley, 1995], rhythmic patterns [Horowitz, 1994] or other well-defined structures such as fitting a melody to a pre-selected chord sequence and song structure [Biles, 1994]. The problem with this is that the composer still needs a degree of analytical skill in deriving these generative processes in the first place. However, once in place, anyone can theoretically act as "composer" and evolve music within the predetermined form space. There is a second approach that is worth briefly mentioning, and which is to somehow model the composers taste itself, thus freeing him/her from having to laboriously judge a large population. One proposed method of doing this is to use a neural network to try to deduce a pattern of taste, trained by observing past user judgments [Thywissen, 1993, Biles, 1994]. Another approach is to assist chromosome fitness evaluation by allowing the user to define rules that, when satisfied, contribute to the chromosome's fitness score [Thywissen, 1993]. 3. Evolving Music with GeNotator GeNotator is an attempt to define a comprehensive framework for musical evolution. Figure 1 gives a high level view of its principal philosophy. In it, we can picture a composition as an amorphous whole of interrelated parts where each plays an important role in the compositions overall structure. These parts may be a melody, a rhythmic structure, harmony, instrumentation or form. "Blind" composition involves applying the genetic algorithm to aspects within this amorphous whole such that permutations of the composition space can be evolved. surface, resembles any mainstream MIDI-based compositional GUI environment with piano-role editing and an "arrangement" editor. However, to complement this is a framework, with GA at its heart, for evolving music. Before going into detail about this framework, it is worth discussing briefly how GeNotator distinguishes between two different types of user/composer. 3.1 "Meta-composer" vs. "Gardener" GeNotator operates at two distinct interactive levels, which, are best described in terms of user sophistication: the meta-composer vs. the gardener (to borrow terminology from Latham). Both, incidentally, could be the same person. The meta-composer tends to have a more analytical understanding about the form and structure of a composition and what he/she wants to achieve, and uses the GA to assist the creative process by generating and refining ideas. Contrasted with this is the gardener who escapes from analytical thought entirely (is, in fact, not permitted to think in terms of structure definition), and instead only needs to know what he/she likes. This is related to the observation that people tend to be far more sophisticated in listening than in creating music ("I don't know anything about music, but I know what I like"). meta-composer! gardener I geoye struc- phentyp Figure 2 - Meta-composer vs. gardener. Both types of user have differing interfaces to a given composition. A typical scenario involves the meta-composer "publishing" a compositional structure genotype; the gardener is subsequently a consumer who interactively evolves a published meta-composition into any number of phenotypes - figure 2. 3.2 Internal Organisation of GeNotator GeNotator uses a hierarchical model to represent any given composition. It also has a simple grammar scripting language that can be used to generate instances of hierarchically organised compositions. The smallest compositional element is the phrase, which is defined as a sequence of possibly concurrent note events. Collections of phrases can be organised into systems, and systems arranged as children to other systems to any level of abstraction - figure 3. A pianorole editor and percussion map editor allow editing of phrases, while a hierarchic "arrange window" allows editing of systems. A phrase-evolver applies the GA to phrase development, and a system-evolver applies the GA to system development. In this way, the composer can target the GA at different levels within a composition, either breeding new structures, or developing existing ones further within the form space. The GA lives in a COMPOSITION'" Amorphous whole where " aspects can be selectively targeted and evolved Figure 1 - Evolving different aspects of a composition. In terms of its place in the tradition of computer assisted composition, GeNotator is best described as a hybrid-algorithmic composition tool which, on the ICMC Proceedings 1996 275 Thywissen

Page  276 ï~~generic form-space manager that collectively handles the house-keeping of chromosome genepools. Figure 3 - Principal architectural components of GeNotator. Additionally, the GA may be applied to a defined musical grammar in order to explore the syntactic permutations permitted by it. The grammar scripting language contains some basic musically useful syntax and can refer to existing phrases and systems as well as user-defined and parametrically controlled event generators. An event generator is an algorithmic process that takes input parameters and generates output in the form of phrases and systems. 3.3 Evolving Phrases In GeNotator, a phrase is a list of notes - each described in terms of a pitch, a relative start time, a duration, and a loudness value. Notes may occur sequentially or concurrently within any given phrase, and a phrase is typically associated with an instrument, although with percussive phrases, each note maps to a different percussive sound in the traditional MIDI manner. Phrases are thus ideally suited for representing melodic, harmony/chordal, and rhythmic structures. In melodic evolution, the GA can operate on several different aspects of a given melody, each represented by a population of chromosomes. These aspects are: pitch content, rhythmic content and dynamics content - figure 4. F2W1 which are then the basis for further evolution. It can also take several "favourite" parent chromosomes and splice them to generate hybrids. If the composer is operating with large populations, fitness rules can be activated to augment the subjective fitness function, whereby chromosomes automatically accumulate points if they fulfill a particular active rule. The composer can then filter out low scoring chromosomes and concentrate only on evaluating the high scoring ones. Typical pre-defined rules specify desired keys/scales/modes, note durations, note density and interval constraints. Evolving harmony/chordal structures is done in a similar way, although here phrases comprise lists of concurrent note groupings, each representing a chord. Chord progressions can be evolved, as well as the pitch content of individual chords. Again, fitness rules may be activated where, for example, acceptable chord sets can be specified. Rhythmic/percussive evolution differs from both melodic and harmony/chordal evolution in that the GA operates on clusters of possibly concurrent note events - each a separate pattern assigned to a particular percussive instrument lasting one measure - figure 5. Figure 5 - A measure of concurrent patterns, one for each percussive sound. For any given rhythmic/percussive phrase, the GA evolves a range of differing parameters, from individual pattern populations, to populations of pattern groupings and instrument combinations. Fitness rules can be activated to promote chromosomes that fulfill particular required features such as choice of percussive instrument family, density level, amount of syncopation and use of down-beat and general dynamics. This is similar in approach to Horowitz' [1994] use of GAs to evolve rhythmic structures, in that it serves as a straight forward method of encoding rudimentary rhythmic knowledge into the fitness function. It is also a logical extension of how GeNotator augments melodic and harmony/chordal evolution with rule-based fitness evaluation. 3.4 Evolving Systems System evolution is fundamentally different from phrase evolution in that the chromosome genes encode the activation of a selection of system operators. System operators are well-defined processes that manipulate the content of the system being evolved. GeNotator currently has five pre-defined operators: transpose, retrograde, invert, augment/diminute, and growth. The first four are interpreted with their traditional meaning; the last allows systems to grow new content by either copying mutated versions of existing systems or simply creating a fractally derived structure of empty systems which the user can populate with phrases. Figure 4 - Independent evolution of differing aspects of a phrase. In this way, the composer can either evolve all three collectively, or just concentrate on one particular aspect of the melody. GeNotator allows evolution to be applied to previously recorded material by using the source to generate a population of mutated instances Thywissen 276 ICMC Proceedings 1996

Page  277 ï~~3.5 Meta-Composing. As already indicated, "meta-composing" sets the scene for the gardening of music. The meta-composer will typically use a combination of pre-recorded and evolved phrases and systems, together with GeNotator's grammar scripting language and parametrically controlled event generators to formulate a meta-composition. Such a composition has built-in evolutionary potential that is bounded by the structure defined by this combination of the grammar, event generators, and phrase content. This bounding is important in order to constrain the composition form space. GeNotator is flexible in this regard since the degree of bounded structure can either be minimal, or highly constrained depending on what the composer wants to achieve. Simple production rules are used to define any given grammar, which GeNotator can evaluate to generate a hierarchical composition consisting of phrases and systems, which are thus legal "phenotypes" of the genotypic grammar. Listing I gives an example. COMP = seq(INTRO, MIDDLE, END); INTRO iterate(2, par(I1, 12, 13)); MIDDLE = terate(rand(2, 4), par(M1, choice(M3, M4))); END lterate(2, par(E1, opt(E2), E3)); I1 phrase("percussion'); 12 = phrase("bass"); 13 = phrase(synth'); M 1 eventgen(chordprog"); M2 = eventgen("melody.gen", M1); Listing 1 - Example of a GeNotator grammar. Given a grammar definition, GeNotator automatically generates a chromosomal structure that maps all the choice routes in the grammar to individual genes. Added to this definition are event generator parameters and any pre-defined systems/phrases. Collectively, this packaging is the genotype structure definition (figure 2) and is "publishable" for interactive consumption. 3.6 Gardening Music. Gardening music involves taking a genotype structure definition and feeding it into GeNotator's gardening interface in order to interactively search through its form space without regard for internal structure. Again, the GA plays an important role in this search, and the user has the option to evolve the composition at differing levels of abstraction. At the highest level, GeNotator can be asked to generate a small number of phenotypes. These may vary quite wildly since every aspect of the genotype is subject to genetic manipulation by the GA. However, this is often the desired effect in order to get maximum initial variability. Here, GeNotator also allows the user to select two or more parent phenotypes for crossfertilization. For more interactive control, the user may ask GeNotator to list individual phrases, event generators, and system/phrases in the genotype structure definition, and selectively evolve them as the meta-composer would. So if a particular melody or rhythmic structure is of interest, it can be targeted and selectively evolved. 4. Conclusions and Future Work In so far that GeNotator provides a comprehensive approach to musical evolution within a hybrid compositional environment, there is much yet to explore. In terms of musical output, GeNotator can certainly evolve interesting music, but it is often a matter of balancing good starting conditions with a degree of form space bounding. Grammars help a lot here, as do the parametrically controlled event generators, which is really GeNotators key to allowing end-users "garden" music. The meta-composer still needs a degree of analytical aptitude in order to capture an interesting genotype structure definition, and it is perhaps here that initial enhancements should be focused. One avenue of interest is to provide automated grammar generation from existing music, or to apply the GA to the evolution of grammars themselves. Other planned enhancements include allowing the user to extend the built-in fitness rules via a simple rule definition language. The same goes for the event generators and system operators, which should ideally also be userextendible (currently they are hard-coded). Finally, GeNotator's gardening interface could be separated out into a standalone application. With the growth of the Internet, combined with the fact that many PCs now come with fairly sophisticated sound cards with built-in MIDI, a GeNotator gardening interface could manifest itself as a Web browser plug-in. This would allow users across the net to exchange, combine and mutate favourite musical genotypes and phenotypes within GeNotators framework. References [Biles, 1994] John A. Biles, GenJam: A Genetic Algorithm for Generating Jazz Solos., Proceedings of the 1994 International Computer Music Conference. [Dawkins, 1986] Richard Dawkins, The Blind Watchmaker. Penguin Books, 1986. [Goldberg, 1989] David E. Goldberg, Genetic Algorithms in Search, Optimization and Machine Learning. Addison Wesley, 1989. [Homer et al, 1991] Andrew Homer, David E. Goldberg, Genetic Algorithms and Computer Assisted Composition. Proceedings of the 1991 International Computer Music Conference. [Homer et al., 1993] Andrew Homer, James Beauchamp, Norman Packard, Timbre breeding. Proceedings of the 1993 International Computer Music Conference. [Homer, 1995] Andrew Homer, Wavetable Matching Synthesis of Dynamic Instruments with Genetic Algorithms. Journal of the Audio Engineering Society, Vol. 43, No. 11, Novemberr 1995. (Horowitz, 1994] Damon Horowitz. Generating Rhythms with Genetic Algorithms. Proceedings of the 1994 International Computer Music Conference. [Jacob, 1995] Bruce L. Jacob. Composing with Genetic Algorithms. Proceedings of the 1995 International Computer Music Conference. [Latham et aL., 1992] William Latham, Stephen Todd. Evolutionary Art and Computers. Academic Press, 1992. [Plotkin, 1995] Henry Plotkin. Darwin Machines and the Nature of Knowledge. Penguin Books, 1995. [Ralley, 1995] David Ralley. Genetic Algorithms as a Tool for Melodic Development. Proceedings of the 1995 Internationa Computer Music Conference. [Thywissen, 1992] Kurt Thywissen. Evolving Melodies with MuTonator. M.Sc. programming assignment, Univ. of York, 1992. [Thywissen, 1993] Kurt Thywissen. GeNotator: An Environment for Investigating the Application of Genetic Algorithms in Computer Assisted Composition. Univ. of York M.Sc. thesis, 1993. ICMC Proceedings 1996 277 Thywissen