Tweaking the Parameters and Processes

While there are a variety of methods that can be altered for the genetic algorithm (such as the method for selection or recombination), the rates at which operators are applied can also be manipulated. It turns out that there is no optimal set of methods and parameters that can be used to universally solve all problems. Each problem must be tweaked to solve it faster, or in a more optimal way (and in some cases, just to solve it at all). In this section, we'll discuss a number of ways that the genetic algorithm can be tailored for a particular application.

Selection Method

We've discussed the probabilistic selection method, the higher the fit of the chromosome, the higher the probability that it will be selected. The problem with probabilistic selection is that a fit chromosome might not be propagated to the following generation. To ensure that the most fit chromosomes are retained, a strategy called elitist selection ensures that the best chromosomes are selected for recombination in the next. This is done by automatically propagating the top 10% of the chromosomes to the next generation.

One final interesting selection mechanism is called tournament selection. In tournament selection, two or more chromosomes are selected from the population. Those chromosomes then compete for the right to move into the next generation. The winner of the competition is based upon the highest fitness. This process is performed twice, resulting in two parents that are used for recombination.

Population Size

The size of the population is a very important element of the genetic algorithm. If the population is too small, too little genetic material may be present to find a solution to the problem at hand. The population size is also linked to the rates at which the crossover and mutation operators should be applied.

Genetic Operators

We've discussed the crossover and mutation operators, but many others exist which can be useful for experimentation for a given problem. Another operator known as inversion has been shown to be useful in certain classes of problems. This operator simply reverses some subset of the genes within the chromosome (useful in an asexual context).

Other Mechanisms

Population seeding is an interesting technique to give the genetic algorithm a good start in optimizing a problem. Rather than initializing the population with random chromosomes, the developer inserts chromosomes that represent known good solutions to the problem. This can lead to premature convergence (loss of diversity within the genetic pool) so extra care must be taken with this technique.

Breeding schemes are another interesting avenue for experimentation, some of which have roots in practices of animal husbandry and horticulture. R. Hollstein investigated a variety of selection methods, as shown in Table 6.2 [Hollstein 1971].

 

Table 6.2: Selection Methods Investigated by R. Hollstein (table created by author).

Method	Description
Progeny Testing	Fitness of offspring controls subsequent breeding of parents
Individual Selection	Fitness of individual controls future use as a parent
Family Selection	Fitness of family controls use of all family members as parents
Within-family Selection	Fitness of individuals within a family controls selection of parents for breeding within family
Combined Selection	Two or more of the prior methods combined

A final option is the self-adaption of the genetic operators and/or rates by which they are applied. Thomas Back [Back 1992] reported interesting results in evolving the rates of mutation and crossover along with the chromosome. Using this, not only does the GA find the solution to the problem at hand, but also the correct rates by with the genetic operators should be applied.

Probabilities

The probabilities for which the genetic operators are applied to the population are very important. For example, if the mutation operator is set too high, the result is the destruction of any useful genetic material within the population and a shift to simple random search. If the rates are set too low, the search for a solution to the given problem may take much longer than is necessary.

Unless self-adaption is used (per Thomas Back), the correct rates are typically found through experimentation. A good starting point is to set the rate so that 70% of the selected parents have the crossover operator applied to them and one mutation is permitted in every other selection.

Depending upon the encoding method selected for the problem, some genetic operators can simply be destructive. A good understanding of the encoding and the effects of operators is therefore necessary to know when and how often to use them.