Like both ES and GAs, EP is a useful method of optimization when other techniques such as gradient descent or direct, analytical discovery are not possible. Combinatoric and real-valued FUNCTION OPTIMIZATION in which the optimization surface or FITNESS landscape is "rugged", possessing many locally optimal solutions, are well suited for evolutionary programming.
In 1992, the First Annual Conference on evolutionary programming was held in La Jolla, CA. Further conferences have been held annually. The conferences attract a diverse group of academic, commercial and military researchers engaged in both developing the theory of the EP technique and in applying EP to a wide range of optimization problems, both in engineering and biology.
Rather than list and analyze the sources in detail, several fundamental sources are listed below which should serve as good pointers to the entire body of work in the field.
The basic EP method involves 3 steps (Repeat until a threshold for iteration is exceeded or an adequate solution is obtained):
(1) Choose an initial POPULATION of trial solutions at random. The number of solutions in a population is highly relevant to the speed of optimization, but no definite answers are available as to how many solutions are appropriate (other than >1) and how many solutions are just wasteful.
(2) Each solution is replicated into a new population. Each of these offspring solutions are mutated according to a distribution of MUTATION types, ranging from minor to extreme with a continuum of mutation types between. The severity of MUTATION is judged on the basis of the functional change imposed on the parents.
(3) Each offspring solution is assessed by computing it's fitness. Typically, a stochastic tournament is held to determine N solutions to be retained for the population of solutions, although this is occasionally performed deterministically. There is no requirement that the population size be held constant, however, nor that only a single offspring be generated from each parent.
It should be pointed out that EP typically does not use any CROSSOVER as a GENETIC OPERATOR.
First, there is no constraint on the representation. The typical GA approach involves encoding the problem solutions as a string of representative tokens, the GENOME. In EP, the representation follows from the problem. A neural network can be represented in the same manner as it is implemented, for example, because the mutation operation does not demand a linear encoding. (In this case, for a fixed topology, real- valued weights could be coded directly as their real values and mutation operates by perturbing a weight vector with a zero mean multivariate Gaussian perturbation. For variable topologies, the architecture is also perturbed, often using Poisson distributed additions and deletions.)
Second, the mutation operation simply changes aspects of the solution according to a statistical distribution which weights minor variations in the behavior of the offspring as highly probable and substantial variations as increasingly unlikely. Further, the severity of mutations is often reduced as the global optimum is approached. There is a certain tautology here: if the global optimum is not already known, how can the spread of the mutation operation be damped as the solutions approach it? Several techniques have been proposed and implemented which address this difficulty, the most widely studied being the "Meta- Evolutionary" technique in which the variance of the mutation distribution is subject to mutation by a fixed variance mutation operator and evolves along with the solution.
The main differences between ES and EP are:
1. Selection: EP typically uses stochastic selection via a tournament. Each trial solution in the population faces competition against a preselected number of opponents and receives a "win" if it is at least as good as its opponent in each encounter. Selection then eliminates those solutions with the least wins. In contrast, ES typically uses deterministic selection in which the worst solutions are purged from the population based directly on their function evaluation.
2. RECOMBINATION: EP is an abstraction of EVOLUTION at the level of reproductive populations (i.e., SPECIES) and thus no recombination mechanisms are typically used because recombination does not occur between species (by definition: see Mayr's biological species concept). In contrast, ES is an abstraction of evolution at the level of INDIVIDUAL behavior. When self-adaptive information is incorporated this is purely genetic information (as opposed to phenotypic) and thus some forms of recombination are reasonable and many forms of recombination have been implemented within ES. Again, the effectiveness of such operators depends on the problem at hand.
Artificial Intelligence Through Simulated Evolution [Fogel66] (primary)
Fogel DB (1995) "Evolutionary Computation: Toward a New Philosophy of
Machine Intelligence," IEEE Press, Piscataway, NJ.
Algorithm EP is// start with an initial time t := 0;
// initialize a usually random population of individuals initpopulation P (t);
// evaluate fitness of all initial individuals of population evaluate P (t);
// test for termination criterion (time, fitness, etc.) while not done do
// perturb the whole population stochastically P'(t) := mutate P (t);
// evaluate it's new fitness evaluate P' (t);
// stochastically select the survivors from actual fitness P(t+1) := survive P(t),P'(t);
// increase the time counter t := t + 1;
od end EP.