Early evolutionary algorithms embodied a small number of fixed representation schemes, independent of the problem domain. Today, evolutionary algorithms employ a wide range of representations, both general and problem specific.
Binary representation has largely fallen out of favor, but real vector representations are still common for parameter optimization problems. For combinatorial optimization problems, there is a considerable literature both on problem-specific representations and operators, and on the relationship between problem structure and representation, allowing a rational choice of representation for particular problems.
Classifier systems evolve sets of logical rules to perform a classification task (Figure 5). There is a limited range of variation in the representations - probabilistic rules and so forth. By contrast, GP has spawned a wide range of representations, including terms (Figure 6), grammars, program execution graphs, linearized trees, stack-based programs, and machine-code programs.
If Max_summer_temp = [30, 35] degC and Min_winter_temp = [-15, -5] degC and Rainfall = [1000, 2000] mm and Winter_rainfall = [500, 1000] mm Then Present = seasonal Figure 5 GARP-style classifier rules.
While classifier systems and GP are now well studied, with significant theoretical bases, they are inherently more complex than GAs, so the theory is far from complete. Thus, the convergence theory for GP is far less developed than for GAs; fitness landscape analysis is inherently more challenging than for GAs, with relatively few studies having been performed; and representation issues are poorly understood, doubtless explaining the plethora of current representations.
Evolutionary operators were a primary driver of early research. This emphasis has decreased, but they still generate advances, in both general-purpose and problem-specific operators.
Early work focused on generating mutation operators of varying levels of disruptiveness. More recently, adaptive mutation operators, which adapt to the differing requirements of evolution at different stages, have become important.
An early theme was removing the biases in one-point crossover; more recently, we have seen the rise of multi-parent recombination operators. While less readily available in packages, multiparent operators, especially differential recombination, offer significant advantages in evolutionary speed without sacrificing robustness.
A major change is the dominance of tournament selection, which first randomly samples k individuals from the population (without replacement), then selects the fittest. Its advantages include efficient implementation, simple tuning (larger tournament sizes give higher selection pressure), and weak requirements (requiring merely a fitness ordering, not numeric fitness values).
Figure 6 GP term mutation and crossover.
Was this article helpful?