The Genetic Algorithm

The genetic algorithm, instead of trying to optimize a single solution, works with a population of candidate solutions that are encoded as chromosomes. Within the chromosome are separate genes that represent the independent variables for the problem at hand (see Figure 6.1).

Figure 6.1: Encoding candidate solutions into chromosomes.

From the simple example in Figure 6.1, we take the parameters from our problem and create a chromosome that represents the two unique independent parameters. The parameters could represent bit strings, floating-point variables, or simple binary-encoded integers.

Through selection of fit chromosomes from the population and use of genetic operators such as recombination and mutation, better fit chromosomes will result in the population. This represents a summary for Holland's schema theorem and is the basis by which it works.

The genetic algorithm consists of three fundamental steps (with a large number of variations possible within each step). These steps are shown in Figure 6.2.

Figure 6.2: Genetic algorithm high-level flow.

The genetic algorithm is performed in three distinct steps, excluding the initial creation of the population. During the evaluation process, the fitness of the population is calculated. Next , a subset of the population is selected based upon a predefined selection criterion. Finally, the selected subpopulation is recombined and the result is a new population. The algorithm begins again with the new population and the process continues until some constraint is reached and the algorithm ends.

Initialization

Creating the initial population provides the starting point for the algorithm. Typically, this is done by randomly creating chromosomes, but can also be done by seeding the population with known fit chromosomes (see Figure 6.3).

Figure 6.3: Initialization of the genetic pool.

Note  

One important constraint is that the initial population must be diverse. This can be ensured by performing a secondary step to check that each chromosome is somewhat different. Without adequate diversity, the algorithm may not produce good solutions.

Evaluation

The evaluation step simply provides a way to rate how each chromosome (candidate solution) solves the problem at hand. This step involves decoding the chromosome into the variable space of the problem and then checking the result of the problem using these parameters. The fitness is then computed from this result (see Figure 6.4).

Figure 6.4: Evaluation of the population.

Selection

Selection is quite possibly the most important and most misunderstood step of the genetic algorithm. In the selection step, chromosomes are selected for propagation to future populations based upon their fitness (how well they solve the problem at hand). This is a double-edged sword since if selection involves only the highest-fit chromosomes; the solution-space becomes very limited due to a lack of diversity. If selection is performed randomly, there is no guarantee that future generations will increase in fitness. The result of the selection process is a set of chromosomes that will take part in recombination (mating, if you will). See Figure 6.5 for a depiction of the selection process.

Figure 6.5: Selecting chromosomes based upon their fitness.

Large varieties of selection algorithms exist. Figure 6.5 shows a selection algorithm known as "Roulette-wheel" selection. Roulette-wheel selection performs selection from the population based upon the fitness of the chromosome. The higher-fit the chromosome, the more likely it will be chosen (and re-chosen) for propagation to the next generation. Put another way, the probability of selection is proportional to the fitness of the chromosome. From Figure 6.5, chromosome 2 has been chosen twice for propagation, chromosome 3 twice, and chromosome 5 only once. Chromosomes 1 and 4 were not selected at all, and disappear from the subsequent population.

Recombination

In recombination, pairs of chromosomes are recombined, possibly modified, and then placed back into the population as the next generation. The original sets of chromosomes are commonly referred to as the "parents" with the resulting chromosomes being the "children." One or more genetic operators are applied with some probability. Some of the possible operators include mutation and crossover, which are analogous to natural genetics . Samplings of genetic operators are covered in the next section. The process of recombination is illustrated in Figure 6.6.

Figure 6.6: Recombining chromosomes for a new population.

The result of recombination is a new population of chromosomes. The process continues again at evaluation until the problem represented by the chromosomes is solved , or some other exit criterion is met (such as convergence, or a maximum number of generations).