Annotated Bibliography
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.
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.
Other Music Tech Related Papers
On-line Resources