Clever Algorithms Welcome to CleverAlgorithms.com! Get notified of future announcements! Email:

 Clever Algorithms: Nature-Inspired Programming Recipes By Jason Brownlee PhD. First Edition, Lulu Enterprises, January 2011. ISBN: 978-1-4467-8506-5.

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

Input: $\mu$, $\lambda$, ProblemSize
Output: $S_{best}$
Population $\leftarrow$ InitializePopulation($\mu$, ProblemSize)
EvaluatePopulation(Population)
$S_{best}$ $\leftarrow$ GetBest(Population, 1)
While ($\neg$StopCondition())
Children $\leftarrow \emptyset$
For ($i=0$ To $\lambda$)
$Parent_{i}$ $\leftarrow$ GetParent(Population, $i$)
$S_{i}$ $\leftarrow \emptyset$
$Si_{problem}$ $\leftarrow$ Mutate($Pi_{problem}$, $Pi_{strategy}$)
$Si_{strategy}$ $\leftarrow$ Mutate($Pi_{strategy}$)
Children $\leftarrow$ $S_{i}$
End
EvaluatePopulation(Children)
$S_{best}$ $\leftarrow$ GetBest(Children + $S_{best}$, 1)
Population $\leftarrow$ SelectBest(Population, Children, $\mu$)
End
Return ($S_{best}$)
Pseudocode for $(\mu,\lambda)$ Evolution Strategies.

## 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

### More in the Series

Check-out other books in the series.

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