Page  00000001 Evolutionary Based Algorithmic Composition: A Demonstration of Recent Developments in GeNotator Kurt Thywissen Department of Computer Science, Hong Kong University of Science & Technology Abstract This demonstration will give an overview of how GeNotator is used to compose and generate music using an evolutionary based compositional model. GeNotator's interpretation of "evolutionary composition" involves defining a meta-composition in terms of a generative music grammar coupled to a genetically based framework for manipulating the defined grammar. The demonstration will focus on recent enhancements to the music grammar language and how it may now be specified entirely through a GUI structure editor that maps a range of editing windows onto constructs in the grammar syntax. It will also show how the interactive selection process inherent in its evolutionary model opens up interesting applications for the World Wide Web and provides both a novel and enjoyable way to compose music. 1 Introduction GeNotator is a hybrid compositional/algorithmic environment for composing music using an evolutionary metaphor of the compositional process [Thywissen, 96]. As described elsewhere in the literature, it addresses the problem of how to automate the process of generation and refinement inherent in much of the creative process. Inspired by similar work in the field of computer graphics [Latham et al., 1992], a framework is provided within which a meta-composer can create a piece of music that is open to independent manipulation and further evolution by a third party, and do so in such a way that requires little understanding of the internal structure of a composition. This demonstration will concentrate on how GeNotator achieves this in practice along with recent theoretical and practical developments relating to its internal mechanics. GeNotator is currently a Windows95/NT MIDI application written in C++ using the MFC class library. Additional components relating to the World Wide Web are implemented as ActiveX controls. 2 Background GeNotator is one of several previously reported systems that use so called "evolutionary" techniques in algorithmic composition [Biles, 1994]. Such techniques are also to be found in sound synthesis applications such as parameter optimization for matching instrument designs [Homer, 1995]. Common to all of these systems is the Genetic Algorithm [Goldberg, 1989], the most widely used mechanism in evolutionary computation. For more on GAs, the reader is recommended to read Goldberg [Goldberg, 1989] as a good introductory text. Briefly here, a GA is a probabilistic algorithm which maintains a population of individuals that encode parameters in the problem domain, typically for an optimization problem. The GA iteratively manipulates generations of such populations through the simple genetic manipulations crossover and mutation. By scoring chromosomes according to their performance, fitter individuals tend to eventually dominate a population as superior genetic content is allowed to evolve over time. In computer music the goal is to evolve aesthetically pleasing musical structures through interactive subjective fitness evaluation by users. Also of interest is the emerging field of Genetic Programming [Koza, 1992], which concentrates on "growing" programs. Here, a GA manipulates chromosome strings that represent program statements for a target algorithm, typically as LISP statements. GeNotator has its own tailored version of the GA and also employs with concepts to be found in Genetic Programming. In particular, is its use of generative music grammars, a feature that differentiates this work from previously reported approaches. Much research into music-oriented grammars exists [Holtzman, 1981], and it is their formal descriptive, and generative power which is of particular interest here. 3 Architectural Overview Figure 1 illustrates the main components in GeNotator. Central to the architecture is the Genotype Structure Definition (GSD). This is a data structure that packages a user defined music grammar together with an automatically generated genetic description that maps individual chromosome genes to choice routes in the grammar. The user specifies this grammar either textually or through a set of editing windows.

Page  00000002 Textual specification of grammar compilation 3.1 GeNotator's Generative Music Grammar A composition is typically specified via the built in grammar scripting language. Aside from the basic constructs of iteration, concurrency and choice, the grammar has other more musically useful constructs allowing the composer to describe objects such as scales, keys, rhythms, phrases and larger compositional structures relating to a composition's "form". Additionally, the grammar syntax is powerful enough to describe transformational rules as part of the grammar definition. This is an attempt to incorporate the linguistic notions of deep structure and transformational rules as described by Chomsky [Chomsky, 1956]. Simple examples of such transformational rules are: transposition, retrograde, inversion, key-change, canon and so on. These prove to be a very powerful generative way of creating additional variance in the genotype description, and also allow the composer to describe music that has some sense of temporal evolution and growth. 3.2 The GUI Interface Up until recently, the grammar needed to be specified almost exclusively in a text-based fashion - which is fine if one is versed in the fine art of programming. Figure 1 - Architectural overview. Once defined, the GSD serves as input to the Form Space Manager. This consists of an interactive genetic algorithm that takes the chromosome structure of the GSD and allows the user to breed and mutate phenotype instances of it. These are realized for playback and auditioning by compiling a MIDI stream using the grammar and the phenotype gene settings. The user is able to judge and score each on aesthetic merit and continue to do so iteratively in order to evolve favourites. Figure 2 - Various GeNotator editing windows for building up a grammar.

Page  00000003 One of the biggest developments in GeNotator is the provision of an alternate graphical way of specifying all the available constructs in the grammar. Figure 2 shows some of the editing windows that are available for building scales, keys, chords and so on. Additionally, a composition is now represented as a project where each component in the project is typically a rewrite rule in the grammar. Since GeNotator has a set of familiar sequencer type editors (figure 3), and can import MIDI files, the result is an integrated environment which helps hide the fact that the composer is actually constructing a formal grammar of the composition behind the scenes. Technically speaking, using the GUI for grammar specification does not generate a textual description that is then compiled, but bypasses the compilation stage altogether. By interacting with the various editing windows the user is manipulating the internal parse tree representation of the grammar itself, an approach known as structure editing. GeNotator actually permits the user to mix and match between a text-based grammar and the graphical approach within the same project. The GUI components can be seen as an alternative view of the grammar to that offered by the textual representation, and have the benefit of being easier to use for nonprogrammers - an important consideration if GeNotator is to be adopted by users not versed in programming. A simple example of this is shown in figure 4 where one sequence rewrite rule is resolvable to three different alternate sequences, and the other one to two. In this instance two genes are added to the genotype with respective cardinalities three and two. COMP S A2 A3 B2 AI A2 A3 [b] Figure 4 - A simple grammar [a] and compiled parse tree [b], with corresponding genes in chromosome structure [c]. Since all the major constructs in GeNotator's grammar syntax support "choice", and thus variability, the meta-composer is free to define any range of variance desired within a composition genotype, from highly constrained to wildly unpredictable. 4 The Compositional Process A typical scenario is for the composer to specify a grammar textually or through the provided editors. A starting point may be an existing composition imported as a MIDI file, which the user can then split up into a grammatical structure. For example, the composer may be attempting to formally describe a well defined composition grammar for the purposes of proving the validity of particular ideas in music theory. Depending on the amount of variance expressed in the grammar, the user can expect to be able to generate either a small or large variety of phenotypes from this grammar genotype, the search-space exploration of which is achieved through the Form Space Manager (see section 5.1) 5 Evolutionary Mechanisms GeNotator uses its own "butchered" version of the genetic algorithm to implement its main evolutionary mechanism. Although considerably modified, this is in line with recent trends to move away from the prevailing classical binary model [Michalewicz, 1995]. As Michalewicz observes, " solve a nontrivial problem using an evolution program, we can either transform the problem into a form appropriate for the genetic algorithm, or we can transform the genetic algorithm to suit the problem." Figure 3: Additional editing features in GeNotator. 3.3 From Grammar to Genotype As mentioned earlier, the GSD consists of a grammar and a generated chromosome template. The grammar is stored internally as a parse tree together with an optional textual representation that was used to generate it. The complementary chromosome template is constructed by searching through the parse tree representation and introducing a new gene for each choice route expressed in the grammar. The allele cardinality of the new gene corresponds to the number of alternatives dictated by the choice route.

Page  00000004 5.1 A Tailored Interactive Genetic Algorithm GeNotator is very much an example of this philosophy, and for this reason it is perhaps best to describe it as an evolution program. For example, although chromosomes are still of fixed length, each gene does not have to be binary, but may have its own cardinality independent of other genes. Additionally, it is possible to impose a probability distribution over the range of values individual genes may take during mutation. Another major difference over classical approaches is the provision for an arbitrary number of parents beyond just two during genetic crossover. The user interacts with this modified GA by controlling such factors as population size, mutation likelihood and designating which parents partake in breeding. By auditioning and scoring phenotypes, the user exerts influence on the direction the evolutionary process follows. 5.2 The Form Space Manager (FSM) The Form Space Manager (FSM) is where GeNotator's tailored GA resides along with other housekeeping facilities such as a genepool database used to maintain and retrieve generations of genetic content. Additionally, the FSM offers a hierarchic menu interface that permits users to progressively unlock deeper structural content in a given GSD. In practice, this means facilitating a way for the user to target particular aspects of a composition for manipulation. GeNotator achieves this by allowing disjoint sections of a chromosome (known as schema) to be "frozen", and thus become dominant from generation to generation: only those genes which are not dominant are effected by the evolutionary process. For example, if a user wishes to only evolve a particular phrase, the hierarchic menu system can be used to track down which genes contribute to the phrase, and then force all other genes that do not contribute to it to become dominant. 6 GeNotator and the Internet A current development has been to separate the Form Space Manager into a stand alone ActiveX control for integration into World Wide Web pages. Once embedded in a web page the control can be automated to upload published GSDs from any supplied URL address across the Internet. The ActiveX control contains the familiar interactive "gardening" interface found in GeNotator and has enough functionality to compile and play phenotype versions of the composition assuming there are compatible MIDI tone generators attached to the host PC. Thus we now have an environment whereby a composer can publish a music genotype (GSD) on the Internet, and by doing so give it a life of it's own beyond the original. This effectively "democratizes" the compositional process as third parties with little or no music knowledge are able to develop other compositional ideas further, and solely on the basis of personal taste: the compositions are perpetually "works in progress". 7 Conclusions and Future Work With the new enhancements to the music grammar and GUI, GeNotator has reached a point of functional maturity that makes composing with it relatively straightforward, and most importantly, enjoyable. It is hoped the ActiveX control will also help the system reach a wider audience via the Internet. Interesting applications beyond being simply a hybrid algorithmic environment include the prospect of royalty free generative music, or even the licensing of music genotypes in a particular musical style - something the advertising, web-content, and games/entertainment industries might find appealing. Future developments will focus on automated grammar construction. GeNotator can currently be described as an "exploitation" evolutionary system: given an explicit grammar it helps the user find interesting phenotypes within the constraints defined by that grammar. The next step is to provide for "exploration" evolution, i.e. evolving the grammar itself. Tentative steps are already being taken in this direction and it is hoped that the emerging field of genetic programming will provide further clues as to how this can be achieved. References [Biles, 1994] John A. Biles, GenJam: A Genetic Algorithm for Generating Jazz Solos. Proceedings of the 1994 ICMC. [Chomsky, 1957] Noam Chomsky, Syntactic Structures, 1957. [Goldberg, 1989] David E. Goldberg, Genetic Algorithms in Search, Optimization and Machine Learning. Addison Wesley, 1989. [Holtzman, 1981] S.R. Holtzman, Using Generative Grammars for Music Composition. Computer Music Journal 5, no. 1 (1981) pp. 51 - 64. [Horner, 1995] Andrew Homer, Wavetable Matching Synthesis of Dynamic Instruments with Genetic Algorithms. Journal of the Audio Engineering Society, Vol. 43, No. 11, Novemberr 1995. [Koza, 1992] J. R. Koza, Genetic Programming - On the Programming of Computers by Means of Natural Selection. MIT Press, 1992. [Latham et al., 1992] William Latham, Stephen Todd. Evolutionary Art and Computers. Academic Press, 1992. [Michalewicz, 1996] Zbigniew Michalewicz, Genetic Algorithms + Data Structures = Evolution Programs. Third edtion, Springer-Verlag, 1996. [Thywissen, 1996] Kurt A. Thywissen, GeNotator: An Environment for Investigating the Application of Genetic Algorithms in Computer Assisted Composition. Proceedings of the 1996 ICMC.