``Mutation is a sideshow in nature and a sideshow in genetic algorithms. I usually keep it turned off.''
John Koza, author of ``Genetic Programming''
Using a large number of individuals in a genetic algorithm results in a large number of function evaluations. A small number of individuals cannot keep track of the positions of previously discovered local maxima. Thus new generations keep falling into the same traps. If a particular individual is stuck at a local maximum, then one option is freezing it, and removing it from the reproductive cycle. This way, the algorithm can keep the size of the population in the reproductive cycle, thus the number of function evaluations, manageable. This scheme was analyzed in previous work [Yuret and de la Maza, 1993]. The population is separated into two groups; young and old. The size of the young population, which contribute to reproduction, is held constant. Individuals that survive more than a maximum number of generations are moved into the old population. This makes it likely that the old are at local maxima. This way, the old population can grow and record an arbitrary number of local maxima while the number of function evaluations per generation is held constant.
Next comes the question of the ideal size for the young population. Having a large number has several advantages. But none of these advantages is enough to offset the need for a large number of function evaluations. In particular, it is claimed that different groups in the population can optimize different parts of the gene, thereby solving different subproblems. Then, the results can be combined into a single individual via crossover. First, this presumes that the representation for the gene separates different pieces of the problem into different dimensions. In other words, the evaluation function needs to be additively separable, which is typically not the case in most numerical optimization problems. Furthermore, crossover would be an advantage if these groups were searching the space in parallel. However on a serial computer, solving a separable problem via crossover takes just as much time as solving one subproblem first, and then solving the other. Note that no crossover is necessary in the serial scheme. A favorable trait is immediately spread to all the individuals, so the individual that solves the next subproblem will actually include the solution to both subproblems.
In this thesis, I will present an algorithm that has only one active individual. Experiments suggest that, with an intelligent mutation scheme, this method is more efficient than using multiple individuals. The local maxima will be kept on a separate list, and the knowledge of their location will be used to guide the search. On a parallel computer, every processor can keep track of a separate individual searching a different region in space. The information they provide on the locations of local maxima can be combined and used to redirect individuals who get stuck. Thus the algorithm naturally accepts a parallel implementation. One might choose to focus the search into regions far away from previously discovered local maxima, or concentrate it in a region where the local maxima are most dense. In the next section I will explore the former strategy. However, there can be no one single strategy that will work well on all problems. A combination of different strategies can be the most effective solution.