Genetic Algorithms as a Method for Granular Synthesis Regulation
Granular synthesis uses combinations of short audio objects, known as grains, that can be individually described by various parameters such as amplitude, frequency, waveform, and duration. Precise control of these grains is difficult since hundreds, perhaps thousands, of them are combined at any given time in order to achieve a desired result. Genetic algorithms are used here to facilitate the regulation of granular synthesis parameters.
Granular synthesis [Xenakis, 1971; Roads 1978, 1985, 1991] uses combinations of short audio objects, known as grains, that can be individually described by various parameters such as amplitude, frequency, waveform, and duration. Precise control of these grains is difficult since hundreds, perhaps thousands, of them are combined at any given time in order to achieve a desired result. Genetic algorithms [Holland, 1975; Davis, 1987; Goldberg 1989] are used here to facilitate the regulation of granular synthesis parameters.
2. Granular synthesis
"Granular synthesis of sound involves generating thousands of very short sonic grains to form larger acoustic events" [Roads, 1985, p.143]. Typically these grains are short acoustic events (10100ms) composed of simple waveforms, FM tones [Truax, 1986, 1988; Waschka and Ferreira, 1988], or sampled material [Jones and Parks, 1988; Truax, 1987, 1989, 1990, 1992, 1993; Lippe, 1993]. In order to produce a granular synthesis segment of any substantial length, large numbers of control values are required. Thus, tools or methods allowing for high-level regulation of these parameters are required if granular synthesis is to be used as an efficient synthesis method.
In the simplest and most common cases, the higher-level controls governing grain parameters are described in terms of start and end values (e.g. frequency and amplitude), as well as the boundary values for random deviations around those parameters (i.e. tendency masks).
Several other approaches have been devised and used to control granular synthesis, such as cellular automaton [Bowcott, 1989; Orton et al., 1991], population modeling [Bowcott, 1990], non-linear functions [Hamman, 1991], and neural networks [Nagashima, 1992].
3. Genetic algorithms
Genetic algorithms are currently used in problem-solving systems based on computational models of the evolution of individual structures via processes of selection and reproduction. More precisely, genetic algorithms maintain a population of individuals that evolve according to specific rules of selection and other operators, such as crossover and mutation. Each individual in the population receives a measure of its fitness in the environment. Selection focuses attention on high fitness individuals, thus exploiting the available fitness information. Since the individual's genetic information (chromosomes) are represented as arrays of binary data, simple bit manipulations allow the implementation of mutation and crossover operations.
The entire process may be described as follows:
(i) Evaluate the fitness of all of the individuals in the population. (ii) Select parents, recombine the "genes" of selected parents to produce offspring. (iii) Perturb the mated population stochastically (mutation). (iv) Discard the old population and iterate using the new population. (See Figure 1).
Figure 1. Overall process of genetic algorithm
Each individual in the population is evaluated for its fitness using a fitness function. Given a particular individual, the fitness function returns a single number; this is the primary place in which the traditional genetic algorithm is tailored to a specific problem.
During the reproductive phase of genetic algorithms, parents are selected and mated, producing offspring which will comprise the next generation. A selection operator is used to favor the fittest parents for reproduction. High fitness individuals may be used several times for reproduction and low fitness individuals may not be used at all. Having selected two parents, their chromosomes are recombined to produce new offspring using crossover and mutation operators.
Crossover operators exchange substrings of two parents to obtain two offspring. The purpose of the crossover operator is to combine useful parental information to form new and hopefully better performing offspring. Such an operator can be implemented by choosing a point at random, called the crossover point, and exchanging the segments to the right of this point. For example, let
Parent 1 = a1 a2 a3 a4 : a5 a6 a7
Parent 2 = b1 b2 b3 b4 : b5 b6 b7
and suppose that the crossover point has been chosen randomly as indicated by the colon. The resulting offspring would be:
Child 1 = b1 b2 b3 b4 : a5 a6 a7
Child 2 = a1 a2 a3 a4 : b5 b6 b7
Crossover rate is the probability per individual to undergo recombination.
Mutation randomly alters each gene with a small probability, typically less than 1%. This operator introduces innovation into the population and helps prevent premature convergence on a local maximum.
The evolution is terminated when the population attains certain criteria such as simulation time, number of generations, or when certain percentage of the population share the same function value.
Genetic algorithms have been successfully applied to solve many optimization and other computationally intensive problems [Davis, 1991]. In music, genetic algorithms have been used for instrument design [Horner et al., 1992; Horner et al., 1993; Takala et al., 1993; Vuori and Välimäki, 1993] and as a compositional aid to generate pitch patterns [Horner and Goldberg, 1991].
4. Use of genetic algorithms for granular synthesis
When using genetic algorithms for granular synthesis regulation, each grain is considered as an individual in a genetic environment with each grain's parameters (frequency, amplitude, etc.) mapped to a chromosome's string of bits. Different measures of fitness or criteria for survival are used, along with genetic algorithm "knobs" such as crossover rate, mutation rate, and population size, to control change in the grain population. Since the entire evolutionary process is regarded as a compositional process, sonic possibilities can be explored by directing the path from which each grain's "genetic material" is determined.
Genetic algorithms offer a flexible macro-control over how each parameter can evolve from one state to another. In fact, genetic algorithms can even be designed to behave much like the traditional tendency mask approach. In real-time granular synthesis, genetic algorithms can provide interesting effects by dynamically changing crossover and mutation rates.
Since there are no strict constraints, such as the need to converge or that an initial population be randomly generated, a wide variety of evaluation functions can be used to match a composers tastes. The choice of these evaluation functions will have direct bearing on the evolution of the granular synthesis material.
The software used to produce genetic algorithm "evolutions" outputs a series of parameter values applying to an individual grain at a given point in time. These values are then converted to conform to the CSOUND score file criteria and subsequently used to generate the granular synthesis segment.
An alternative methods for high-level regulation of granular synthesis by genetic algorithm was presented. In this paper, only the classic genetic algorithm has been explored, ideas from other innovative genetic algorithms [Forrest, 1993] could be applied to granular synthesis and other areas in music. Conversely, this technique may be applied in the field of scientific auralization, where some aspects of scientific data or computer simulation are converted to audible sound to aid in the analysis and exploration of data or processes. In research using genetic algorithms, for example, the states of the evolution can be converted to sound using granular synthesis, thus enabling researcher to monitor the environment by listening.
[Bowcott, 1989] P. Bowcott. Cellular automation as a means of high level compositional control of granular synthesis. Proceedings of the 1989 International Computer Music Conference, pp. 5557, 1989.
[Bowcott, 1990] P. Bowcott. High level control of granular synthesis using the concepts of inheritance and social interaction. Proceedings of the 1990 International Computer Music Conference, pp. 5052, 1990.
[Davis, 1987] L. Davis. Genetic algorithms and simulated annealing. Pitman, London, 1987.
[Davis, 1991] L. Davis. Handbook of genetic algorithms. Van Norstrand Reinhold, New York, 1991.
[Forrest, 1993] S. Forrest. Genetic algorithms: Principles of natural selection applied to computation. Science. 261: pp. 872878, 1993.
[Goldberg, 1989] D. E. Goldberg. Genetic algorithms in search, optimization, and machine leaning. Addison-Wesley, Reading, 1989.
[Hamman, 1991] M. Hamman. Mapping complex systems using granular synthesis. Proceedings of the 1991 International Computer Music Conference, pp. 475478, 1991.
[Holland, 1975] J. H. Holland. Adaptation in natural and artificial systems. U. of Michigan Press, Ann Arbor, 1975 (reprinted by Cambridge: MIT Press. 1992.)
[Horner and Goldberg, 1991] A. Horner and D. E. Goldberg. Genetic algorithms and computer-assisted music composition. Proceedings of the 1991 International Computer Music Conference, pp. 479482, 1991.
[Horner et al., 1992] A. Horner, J. Beauchamp, and L. Haken. Wavetable and FM matching synthesis of musical instrument tones. Proceedings of the 1992 International Computer Music Conference, pp. 1821, 1992.
[Horner et al., 1993] A. Horner, J. Beauchamp, and N. Packard. Timbre breeding. Proceedings of the 1993 International Computer Music Conference, pp. 396398, 1993.
[Jones and Parks, 1988] D. L. Jones and T. Parks. Generation and combination of grains for music synthesis. Computer Music Journal, 12(2): pp. 2734, 1988.
[Lippe, 1993] C. Lippe. A musical application of real-time granular sampling using the IRCAM signal processing workstation. Proceedings of the 1993 International Computer Music Conference, pp. 190193, 1993.
[Nagashima, 1992] Y. Nagashima. Real-time control system for pseudo granulation. Proceedings of the 1992 International Computer Music Conference, pp. 404405, 1992.
[Orton et al., 1991] R. Orton, A. Hunt, and R. Kirk. Genetic algorithms and computer-assisted music composition. Proceedings of the 1991 International Computer Music Conference, pp. 416418, 1991.
[Roads, 1978] C. Roads. Automated granular synthesis of sound. Computer Music Journal, 2(2): pp. 6162, 1978.
[Roads, 1985] C. Roads. Granular synthesis of sound. In Foundations of Computer Music. C. Roads and J. Strawn, eds. MIT Press, Cambridge, pp. 145159, 1985.
[Roads, 1991] C. Roads. Asynchronous granular synthesis. In Representations of musical signals. G. De Poli, A. Piccialli, and C. Roads, eds. MIT Press, Cambridge, pp. 143186, 1991.
[Takala et al., 1993] T. Takala, J, Hahn, L. Gritz, J. Geigel, and J. W. Lee. Using physically-based models and genetic algorithms for functional composition of sound signals, synchronized to animated motion. Proceedings of the 1993 International Computer Music Conference, pp. 180185, 1993.
[Truax, 1986] B. Truax. Real-time granular synthesis with the DMX-1000. Proceedings of the 1986 International Computer Music Conference, pp. 231235, 1986.
[Truax, 1987] B. Truax. Real-time granulation of sampled sound with the DMX-1000. Proceedings of the 1987 International Computer Music Conference, pp. 13845, 1987.
[Truax, 1988] B. Truax. Real-time granular synthesis with a digital processing computer. Computer Music Journal. 12(2): pp. 1426, 1988.
[Truax, 1989] B. Truax. Composing with real-time granular sound. Perspectives of New Music. 28(2): pp. 121135, 1989.
[Truax, 1990] B. Truax. Time-shifting of sampled sound with a real-time granulation technique. Proceedings of the 1990 International Computer Music Conference, pp. 104107 1990.
[Truax, 1992] B. Truax. Composition with time-shifting of sampled sound using a real-time granulation technique. Proceedings of the 1992 International Computer Music Conference, pp. 487490, 1992.
[Truax, 1993] B. Truax. Time-shifting and transposition of sampled sound with a real-time granulation technique. Proceedings of the 1993 International Computer Music Conference, pp. 8285, 1993.
[Vuori and Välimäki, 1993] J. Vuori and V. Välimäki. Parameter estimation of non-linear physical models by simulated evolutionapplication to the flute model. Proceedings of the 1993 International Computer Music Conference, pp. 402404, 1993.
[Waschka and Ferreira, 1988] R. Waschka II and T. Ferreira. Rapid event deployment in a MIDI environment. Interface, 17:211222, 1988.
[Xenakis, 1971] I. Xenakis. Formalized Music. Indiana University Press, Bloomington, 1971.