Evolution Strategies

Evolution Strategies, Evolution Strategy, Evolutionary Strategies, ES.

Taxonomy

Evolution Strategies is a global optimization algorithm and is an instance of an Evolutionary Algorithm from the field of Evolutionary Computation. Evolution Strategies is a sibling technique to other Evolutionary Algorithms such as Genetic Algorithms, Genetic Programming, Learning Classifier Systems, and Evolutionary Programming. A popular descendant of the Evolution Strategies algorithm is the Covariance Matrix Adaptation Evolution Strategies (CMA-ES).

Inspiration

Evolution Strategies is inspired by the theory of evolution by means of natural selection. Specifically, the technique is inspired by macro-level or the species-level process of evolution (phenotype, hereditary, variation) and is not concerned with the genetic mechanisms of evolution (genome, chromosomes, genes, alleles).

Strategy

The objective of the Evolution Strategies algorithm is to maximize the suitability of collection of candidate solutions in the context of an objective function from a domain. The objective was classically achieved through the adoption of dynamic variation, a surrogate for descent with modification, where the amount of variation was adapted dynamically with performance-based heuristics. Contemporary approaches co-adapt parameters that control the amount and bias of variation with the candidate solutions.

Procedure

Instances of Evolution Strategies algorithms may be concisely described with a custom terminology in the form $(\mu,\lambda)-ES$, where $\mu$ is number of candidate solutions in the parent generation, and $\lambda$ is the number of candidate solutions generated from the parent generation. In this configuration, the best $\mu$ are kept if $\lambda > \mu$, where $\lambda$ must be great or equal to $\mu$. In addition to the so-called comma-selection Evolution Strategies algorithm, a plus-selection variation may be defined $(\mu + \lambda)-ES$, where the best members of the union of the $\mu$ and $\lambda$ generations compete based on objective fitness for a position in the next generation. The simplest configuration is the $(1+1)-ES$, which is a type of greedy hill climbing algorithm. Algorithm (below) provides a pseudocode listing of the $(\mu,\lambda)-ES$ algorithm for minimizing a cost function. The algorithm shows the adaptation of candidate solutions that co-adapt their own strategy parameters that influence the amount of mutation applied to a candidate solutions descendants.

Heuristics

• Evolution Strategies uses problem specific representations, such as real values for continuous function optimization.
• The algorithm is commonly configured such that $1 \leq \mu \leq \lambda$.
• The ratio of $\mu$ to $\lambda$ influences the amount of selection pressure (greediness) exerted by the algorithm.
• A contemporary update to the algorithms notation includes a $\rho$ as $(\mu/\rho,\lambda)-ES$ that specifies the number of parents that will contribute to each new candidate solution using a recombination operator.
• A classical rule used to govern the amount of mutation (standard deviation used in mutation for continuous function optimization) was the $\frac{1}{5}$-rule, where the ratio of successful mutations should be $\frac{1}{5}$ of all mutations. If it is greater the variance is increased, otherwise if the ratio is is less, the variance is decreased.
• The comma-selection variation of the algorithm can be good for dynamic problem instances given its capability for continued exploration of the search space, whereas the plus-selection variation can be good for refinement and convergence.

Code Listing

Listing (below) provides an example of the Evolution Strategies algorithm implemented in the Ruby Programming Language. The demonstration problem is an instance of a continuous function optimization that seeks $\min f(x)$ where $f=\sum_{i=1}^n x_{i}^2$, $-5.0\leq x_i \leq 5.0$ and $n=2$. The optimal solution for this basin function is $(v_0,\ldots,v_{n-1})=0.0$. The algorithm is a implementation of Evolution Strategies based on simple version described by Bäck and Schwefel [Back1993b], which was also used as the basis of a detailed empirical study [Yao1997]. The algorithm is an $(30+20)-ES$ that adapts both the problem and strategy (standard deviations) variables. More contemporary implementations may modify the strategy variables differently, and include an additional set of adapted strategy parameters to influence the direction of mutation (see [Rudolph2000] for a concise description).

def objective_function(vector)
  return vector.inject(0.0) {|sum, x| sum +  (x ** 2.0)}
end

def random_vector(minmax)
  return Array.new(minmax.size) do |i|
    minmax[i][0] + ((minmax[i][1] - minmax[i][0]) * rand())
  end
end

def random_gaussian(mean=0.0, stdev=1.0)
  u1 = u2 = w = 0
  begin
    u1 = 2 * rand() - 1
    u2 = 2 * rand() - 1
    w = u1 * u1 + u2 * u2
  end while w >= 1
  w = Math.sqrt((-2.0 * Math.log(w)) / w)
  return mean + (u2 * w) * stdev
end

def mutate_problem(vector, stdevs, search_space)
  child = Array(vector.size)
  vector.each_with_index do |v, i|
    child[i] = v + stdevs[i] * random_gaussian()
    child[i] = search_space[i][0] if child[i] < search_space[i][0]
    child[i] = search_space[i][1] if child[i] > search_space[i][1]
  end
  return child
end

def mutate_strategy(stdevs)
  tau = Math.sqrt(2.0*stdevs.size.to_f)**-1.0
  tau_p = Math.sqrt(2.0*Math.sqrt(stdevs.size.to_f))**-1.0
  child = Array.new(stdevs.size) do |i|
    stdevs[i] * Math.exp(tau_p*random_gaussian() + tau*random_gaussian())
  end
  return child
end

def mutate(par, minmax)
  child = {}
  child[:vector] = mutate_problem(par[:vector], par[:strategy], minmax)
  child[:strategy] = mutate_strategy(par[:strategy])
  return child
end

def init_population(minmax, pop_size)
  strategy = Array.new(minmax.size) do |i|
    [0,  (minmax[i][1]-minmax[i][0]) * 0.05]
  end
  pop = Array.new(pop_size) { Hash.new }
  pop.each_index do |i|
    pop[i][:vector] = random_vector(minmax)
    pop[i][:strategy] = random_vector(strategy)
  end
  pop.each{|c| c[:fitness] = objective_function(c[:vector])}
  return pop
end

def search(max_gens, search_space, pop_size, num_children)
  population = init_population(search_space, pop_size)
  best = population.sort{|x,y| x[:fitness] <=> y[:fitness]}.first
  max_gens.times do |gen|
    children = Array.new(num_children) do |i|
      mutate(population[i], search_space)
    end
    children.each{|c| c[:fitness] = objective_function(c[:vector])}
    union = children+population
    union.sort!{|x,y| x[:fitness] <=> y[:fitness]}
    best = union.first if union.first[:fitness] < best[:fitness]
    population = union.first(pop_size)
    puts " > gen #{gen}, fitness=#{best[:fitness]}"
  end
  return best
end

if __FILE__ == $0
  # problem configuration
  problem_size = 2
  search_space = Array.new(problem_size) {|i| [-5, +5]}
  # algorithm configuration
  max_gens = 100
  pop_size = 30
  num_children = 20
  # execute the algorithm
  best = search(max_gens, search_space, pop_size, num_children)
  puts "done! Solution: f=#{best[:fitness]}, s=#{best[:vector].inspect}"
end

References

Primary Sources

Evolution Strategies was developed by three students (Bienert, Rechenberg, Schwefel) at the Technical University in Berlin in 1964 in an effort to robotically optimize an aerodynamics design problem. The seminal work in Evolution Strategies was Rechenberg's PhD thesis [Rechenberg1971] that was later published as a book [Rechenberg1973], both in German. Many technical reports and papers were published by Schwefel and Rechenberg, although the seminal paper published in English was by Klockgether and Schwefel on the two–phase nozzle design problem [Klockgether1970].

Learn More

Schwefel published his PhD dissertation [Schwefel1975] not long after Rechenberg, which was also published as a book [Schwefel1977], both in German. Schwefel's book was later translated into English and represents a classical reference for the technique [Schwefel1981]. Bäck et al. provide a classical introduction to the technique, covering the history, development of the algorithm, and the steps that lead it to where it was in 1991 [Back1991]. Beyer and Schwefel provide a contemporary introduction to the field that includes a detailed history of the approach, the developments and improvements since its inception, and an overview of the theoretical findings that have been made [Beyer2002].

Bibliography

Please Note: This content was automatically generated from the book content and may contain minor differences.