Genetic Algorithms (GA)
Created at 3:18 PM 1/31/2007, by Shi Yong
Forrest, S., Genetic algorithms: principles of natural selection applied to computation. Science, 1993. 261(5123): p. 872-878.
An overall summarize of classic Genetic Algorithm, which can be divided into four parts.
Haupt, R.L. and S.E. Haupt, Practical Genetic Algorithms. 2nd Edition ed. 2004, Hoboken, New Jersey: Wiley-Interscience. 272.
Part 1: A good overview of the genetic algorithm, and the implementation invented by Holland. In the simplest form, each individual of an initial population consists of a string of binary digits (genotype). In each generation, a group individuals are selected based on the fitness evaluation, genetic operations (crossover and mutation) are then applied stochastically to this group to produce a new population. The cycle of evaluation, selection and genetic operations is iterated for many generations, until a specified convergence is reached.
Part 2: Some typital applications. Multi-parameter function optimization (global minimum or maximum)
Ordering problem (the travelling salesman problem, bin-packing problem)
Automatic programming (evolve computer programs written in Lisp)
Part 3: Mathematical analysis. Mathematical analysis method is helpful for questions such as predicting if GA is appropriate for a specfic problem, and which fitness landscape is suited.
Part 4: Making Models. A wide variety of dynamic processes have made use of GA as a modeling tool, such as the evolution of ecological systems and immune system.
A highly practical introductory book of Genetic Algorithm, with many examples.
Garcia, R.A., Towards the Automatic Generation of Sound Synthesis Techniques: Preparatory Steps, in Audio Engineering Society 109th Convention. 2000: Los Angeles.
Chapter 1: An elementary introduction to optimization, the example of global minimum and the local minimum, and the introduction of traditional minimum-seeking algorithms (exhaustive search, analytical optimization, etc.). Some shortfalls of these algorithms such as extremely long searching time, no guarantee to find the global minimum, restriction of search space, etc., make them not appropriate for many problems.
Chapter 2: In this case, the number of combinations is finite, and parameters are quantized. It is ideal for dealing with parameters that can assume only a finite number of values. A good example is demonstrated by the process of searching the highest point in a park. The GA begins by defining a chromosome, which has a number of variables. Each individual with a unique chromosome is evaluated by the cost function. The cost function comes from either experience or analytical function. In the iterating process, individuals with high fitness value are selected and mated. The chromosomes of the offsprings are inherited from the parents with a randomly selected crossover. Stochastic mutations alter certain bits in the chromosomes, in order to prevent a too fast convergence. Once a proper solution is reached or a predefined number of iterations is exceeded, the algorithm should be stopped.
Chapter 3: The continuous GA allows the parameters represented by float point, within certain constraints. Generally, all variables are normalized to have values between 0 and 1. Different crossover and mutation operator are used in this scheme. On the crossover side, with the blending methods, a new offspring value is generated by combine the two parents values and a random factor on the interval [0, 1]. To introduce new offspring values beyond the extremes, an extrapolating method, such as linear crossover, blend crossover, or quadratic crossover can be used, where the best two offsprings are chosen from three candidates. A method that is a combination of an extrapolation method with a crossover method is detailed in this chapter (p.59). On the mutation side, a mutation rate is predefined; accordingly a few chromosomes are randomly selected and replaced with a uniform random on a predefined interval.
Chapter 4: A variety of interesting applications of GA are introduced in this chapter to demonstrate the usage of GA in different field, such as melody searching, visual art, word guess, best location searching, antenna array design, and the simulation of horse¡¯s evolution. Objective and subjective cost function are compared to each other in some examples. In the last instance, the evolution of various characteristics of horse in different environment is just as the case in the real life.
Advanced Methods and applications are introduced in other chapters.
Some preparatory issues of automatic generation of sound synthesis techniques is discussed in this paper. A number of classical synthesis techniques, such as additive, FM, subtractive synthesis, ring modulation, wavetable, etc., can be uniformly described by a few types of basic modulars (components and connections) and a mapping scheme (each element is mapped with a special symbol). Genetic Programming (an extension of the Genetic Algorithms) is then used to seach a sound synthesis topology that with the best fitness value (produce the most acceptable sound). The GP works with the "description" (recipe of actual topologies) rather than with the topologies themselves directly. The fitness of each produced topology can be evaluated by either objective measure (like Mean Squared Error) or subjective method (Perceptual Similarity).
Fujinaga, I. and J. Vantomme. Genetic Algorithms as a Method for Granular Synthesis Regulation. in International Computer Music Conference. 1994.
Classic genetic algorithms were used for parameter regulation of granular synthesis.The general idea of genetic algorithm as well as block diagram were introduced.The grain's parameters can be mapped to a chromosome, so that the genetic algorithms can facilitate various parameters evolving from one state to another.
Riionheimo, J. and V. Valimaki, Parameter Estimation of a Plucked String Synthesis Model Using a Genetic Algorithm with Perceptual Fitness Calculation. EURASIP Journal on Applied Signal Processing, 2003(8): p. 791-805.
GA with real value encoding is used to implement an automatic parameter extraction method for natural string synthesis. Fitness is computed from a comparison of the perceptual transformed spectra between synthesized sound and target sound by making use of the nature of human aural perception.
Lai, Y., et al., Automated Optimization of Parameters for FM Sound Synthesis with Genetic Algorithms, in International Workshop on Computer Music and Audio Technology. 2006.
An method based on genetic algorithm for automating the internal parameters of a FM synthesizer. The goal is to let the synthesized sound similar to the target sound samper. The spectral centroid,the spectral norm, and the weighted combination are chosen as the objective functions.
McDermott, J., N.J.L. Griffith, and M. O'Neill. Target-Driven Genetic Algorithms for Synthesizer Control. in 9th Int. Conference on Digital Audio Effects (DAFx' 06). 2006. Montreal, Canada.
GA was used to drive a software synthesizer to solve the target sound matching problem. Fitness function was defined in sound attributes matching. A layered learning method was used to improve the performance.
Horner, A. and J. Beauchamp, A genetic algorithm-based method for synthesis of low peak amplitude signals. Journal of the Acoustic Society of America, 1996. 99(1): p. 433-443.
GA is used in designing low peak amplitude signals by exploring many local optima of the phase space in parallel.
Other Music Tech Related Papers
Setting synthesis parameters to match particular sounds:
San-kuen Chan, Jennifer Yuen, and Andrew Horner. Discrete summation synthesis and hybrid sampling-wavetable synthesis of acoustic instruments with genetic algorithms. Proceedings of the International Computer Music Conference, pages 49-51, 1996.
Andrew Horner and Lydia Ayers. Common tone adaptive tuning using genetic algorithms. Journal of the Acoustic Society of America,100(1):630-640, July 1996.
Synchronization of sound and animation
Tapio Takala, James Hahn, Larry Gritz, Joe Geigel, and Jong Won Lee. Using physically-based models and genetic algorithms for functional composition of sound signals, synchronized to animated motion. Proceedings of the International Computer Music Conference,pages 180-183, 1993.
Angela Fraser and Ichiro Fujinaga. Toward real-time recognition of acoustic musical instruments. Proceedings of the International Computer Music Conference, pages 175-177, 1999.
Ichiro Fujinaga. Exemplar-based learning in adaptive optical music recognition system. Proceedings of the International Computer Music Conference, pages 55-56, 1996.
Evolution of components in systems with more traditional architecture
Peter Beyls. Evolutionary strategies for spontaneous man-machine interaction. Proceedings of the International Computer Music Conference, pages 171-174, 1999.
Bruce L. Jacob. Composition with genetic algorithms. Proceedings of the International Computer Music Conference, pages 452-455, 1995.
GENETIC ALGORITHMS [accessed 2007 Jan 30]
Introduction of GA with excellent interactive Java applets, developed by Marek Obitko, Czech Technical University.
Entry on Wikipedia [accessed 2007 Jan 30]
Introduction of GA by the original developer [accessed 2007 Jan 30]
Composing with Genetic Algorithms [accessed 2007 Jan 30]
Fugue Generation with Genetic Algorithms [accessed 2007 Jan 30]
GenJam: A Genetic Algorithm for Generating Jazz Solos [accessed 2007 Jan 30]