Page  479 ï~~Genetic Algorithms and Computer-Assisted Music Composition Andrew Homer and David E. Goldberg University of Illinois at Urbana-Champaign Urbana, IL 61801 Abstract Genetic algorithms (GAs) have been used with increasing frequency and effectiveness in a variety of problems. This paper investigates the application of genetic algorithms to music composition. A technique of thematic bridging is presented that allows for the specification of thematic material and delegates its development to the genetic algorithm. Some preliminary results are then discussed with an eye toward future work in GAassisted composition. 1 Introduction Genetic algorithms (Goldberg, 1989; Holland, 1975) have been applied to a wide array of problem domains from medical image registration (Fitzpatrick, Grefenstette, & Van Gucht, 1984) to stack filter design (Chu, 1989). The accessibility of their interface has contributed to experimentation on problems from many diverse disciplines. Unlike most traditional optimization techniques, GAs don't rely on a particular problem structure or problem-specific knowledge. The general effectiveness of GAs in blindly optimizing problems in no small part accounts for their growing popularity. It is this accessibility and effectiveness that suggests that GAs might provide a powerful tool in the computer-assisted composition of music. Various approaches to computer-assisted composition have been employed in generating music. These range from the relatively straightforward mapping of functions to compositional parameters (Dodge, 1988) through elaborate stochastic feedback models (Tipei, 1989; Xenakis, 1971). Recent work using neural network composition methods to learn and generalize structures from existing musical examples is also of particular interest (Todd, 1989). The approach adopted in this paper is one of thematic bridging (Horner and Goldberg, 1991). Thematic bridging is the transformation of an initial musical pattern to some final pattern over a specified duration. This method is often characteristic of phase or minimalist music and was chosen because of the fact that it lends itself so naturally to GA encoding. The bridging is brought about through modifying or reordering elements of intervening patterns through a sequence of operations. The elements themselves may be discrete pitch, amplitude, or duration values. The resulting musical output consists of the concatenation of each partially developed pattern (or some variation of it) through the final pattern. The initial pattern itself is not part of the output, but could be a part of a preceding section as the final pattern. As a simple example, with an initial note pattern (Gb,Bb,F,Ab,Db), a final pattern (F,Ab,Eb), and a note duration of 17, a bridge could be as follows: operation description resulting pattern delete the last note of the initial pattern Gb Bb F Ab rotate the pattern Bb F Ab Gb delete the last note B b F Ab mutate the first note Eb F Ab rotate the pattern F Ab Eb ICMC 479

Page  480 ï~~musical output: Gb Bb F Ab Bb F Ab Gb Bb F Ab Eb F Ab F Ab Eb In addition to the thematic patterns and bridge duration, the basic operation set for transforming patterns must be specified. In the example above, the operation set includes atomic operations that change and delete notes, and an operation for rotating the pattern as a whole. Some operation sets may not be capable of bridging the initial and final patterns over the duration specified, regardless of the sequencing. This suggests an iterative approach, where the problem is run to convergence and subsequently rerun with modifications if results are unsatisfactory (figure 1). For example, if the thematic patterns are dissimilar and the bridge duration is short, relatively high-level operations may be needed to bring off the transformation. choose thematic patterns, bridge, Run Results yes duration, and GA/CAC acceptable? End operation set. no Modify thematic patterns, duration, or operation set Figure 1: Iterative modification in GA-assisted composition. Thematic bridging contrasts with more conventional algorithmic composition techniques in that the transition rules are not explicitly applied. Instead, the GA selects a sequence of operations or atomic transition rules to apply from a user-supplied operation set in constructing the bridge. This bridging bears some resemblance to the interpolation of melodies in neural network algorithmic composition (Todd, 1989), though learning is not a part of the bridging process. 2 Genetic algorithms and thematic bridging Genetic algorithms are a randomized optimization technique which search the problem space using populations of candidate solutions (Goldberg, 1989). Generally, the user supplies a fitness function that evaluates a given potential solution. The procedure begins with a random initial population of potential solutions and genetic operators are applied to produce new populations over successive generations. The best candidate solution seen over all generations is then chosen as the answer to the problem. No guarantees are made as to the optimality of this answer, but generally it is a very good solution. The standard 3-operator GA uses selection, crossover, and mutation. These genetic operators work together to efficiently explore the solution space by propagating and recombining the best individuals in each generation. ICMC 480

Page  481 ï~~The fitness function for thematic bridging consists of two parts. The initial part determines how close the bridge comes to arriving at the final pattern. This entails checking that the right elements appear in the resulting pattern, and in the correct order. The second part grades how well the bridge duration matches the desired duration. 3 Results The problem, an operation set, and GA have been programmed in Smalltalk. A short piece has been created by the GA using thematic bridging for pitch and amplitude development. The piece is entitled "Epistasis" and consists of five voices in canon (the voices play the same material at different times) over six bridge passages. The GA was run for each of the passages independently, given the thematic patterns and duration of each. The musical output was then scheduled among the five voices so that the passages would overlap. The thematic material itself is quite simple, which is something of a challenge since its development must sustain interest. 4 Future Work Several extensions to the work presented in this paper follow quite naturally. The thematic material used to date has been relatively simple; more sophisticated material and textures are needed to determine the general effectiveness of the technique. Experiments using control flow and other customized operations are likely to be fruitful. Beyond pitch, amplitude, and rhythmic development, manipulation of timbre (sound quality) via music synthesis techniques or MIDI control changes promises further compositional control using the same basic technique (interpolation may be used between discrete values for continuous changes). 5 Conclusions This paper has applied genetic algorithms to music composition through a technique of thematic bridging. The technique is only one method of using GAs in computer-assisted composition, but it raises many of the issues common to other approaches. Finally, several directions for further study have been outlined and discussed which promise interesting musical results in future genetic composition. Acknowledgments This material is based upon work supported by the National Science Foundation under Grants CTS8451610 and ECS-9022007 and the CERL Sound Group at the University of Illinois. Musical realization of this work was facilitated by Symbolic Sound Corporation's Kyma Workstation. References Chu, C. (1989). A genetic algorithm approach to the configuration of stack filters. Proceedings of the Third International Conference on Genetic Algorithms and Their Applications, 112-120. Dodge, C. (1988). Profile: A musical fractal. Computer Music Journal 12(3): 10-14. Fitzpatrick, J. M., Grefenstette, J. J., & Van Gucht, D., (1984). Image registration by genetic search. Proceedings of IEEE Southeast Conference, 460-464. Goldberg, D. E. (1989). Genetic algorithms in search, optimization, and machine learning. Reading, MA: Addison-Wesley. ICMC.481

Page  482 ï~~Goldberg, D. E. (1990). Real-coded genetic algorithms, virtual alphabets, and blocking (IIIiGAL Report No. 90001). Urbana: University of Illinois, Illinois Genetic Algorithms Laboratory. Holland, 3. H. (1975). Adaptation in natural and artificial systems. Ann Arbor: The University of Michigan Press. Homer, A. and Goldberg, D. (1991). Genetic Algorithms and Computer-Assisted Music Composition. Proceedings of the Fourth International Conference on Genetic Algorithms and Their Applications. Tipei, S. (1989). The computer: A composer's collaborator. Leonardo, 22(2): 189-195. Todd, P. (1989). A connectionist approach to algorithmic composition.Computer Music Journal 13(4): 27 -43. Xenakis, I. (1971). Formalized music. Bloomington: Indiana University Press. ICMC 482