Figure 1.13 Fitness and gene values for Example 1.6A.
While Example 1.6A helped to illustrate the operation of a real‐coded GA, practical GAs typically have several additional features to increase their efficacy. We will now briefly consider some of these additional operators.
Scaling
Scaling the fitness values of a population can result in improved algorithm performance. Scaling algorithms are only used in the context of roulette wheel selection. Consider a situation early in an evolution. Suppose individual A is significantly more fit than the remainder of the population. In this case, many copies of individual A will become part of the mating pool. In fact, without scaling, copies of individual A can rapidly dominate the population, leading to premature convergence and a failure to fully explore the search space. In this case, the scaling algorithm could be used to reduce the fitness of individual A so that it does not become as common as quickly, permitting the evolution to explore other avenues.
Conversely, late in the evolution, suppose that individual B is slightly better than the rest of the population. Because the fitness of most individuals is quite good, the chances of individual B being put into the mating pool are not much more than that of an average individual. In this case, it is appropriate to scale the fitness of population member B so as to increase its likelihood of being put into the mating pool. Another purpose of scaling is that for roulette wheel selection, all fitness values need to be positive.
Many scaling algorithms take the form of (1.6-15). Therein, a and b are coefficients, which vary by algorithm, and f′ denotes the scaled fitness. Expressions for a and b are listed by method in Table 1.4. In this table, fmin, fmax, favg, and fmed denote the minimum, maximum, average, and median fitness of the population.
Another scaling method approach is quadratic scaling. In this algorithm, the scaled fitness is calculated as
(1.6-16)
Table 1.4 Linear Scaling Methods
| Method | a | b | Comments |
|---|---|---|---|
| Offset scaling | 1 | −fmin | Ensures positive fitness |
| Standard linear scaling |
|
favg (1 − a) | Most fit individual k times more likely to be in mating pool than average |
| Modified linear scaling |
|
fmed (1 − a) | Most fit individual k times more likely to be in mating pool than median |
| Mapped linear scaling |
|
−afmin + 1 | Minimum fitness mapped to 1; maximum fitness to k |
| Sigma truncation | 1 | −(favg − kfstd) | Average fitness maps to kfstd |
where a, b, and c are given by
In (1.6-17), kmax and kmin are algorithm constants selected such that kmax > 1 and 0 < kmin < 1. In this approach, an individual with a fitness equal to the population average is scaled to 1, the most fit individual has a scaled fitness of kmax, and the least fit individual has
