Evolutionary Algorithm Variants

Representation

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.

Problem-specific representation

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.

Flexible representation

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.

Operators

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.

Variation operators Mutation 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.

Recombination operators

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.

Selection operators

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).

Torna Ora Solare

Figure 6 GP term mutation and crossover.

Was this article helpful?

0 0
Oplan Termites

Oplan Termites

You Might Start Missing Your Termites After Kickin'em Out. After All, They Have Been Your Roommates For Quite A While. Enraged With How The Termites Have Eaten Up Your Antique Furniture? Can't Wait To Have Them Exterminated Completely From The Face Of The Earth? Fret Not. We Will Tell You How To Get Rid Of Them From Your House At Least. If Not From The Face The Earth.

Get My Free Ebook


Post a comment