Friday, 2020-02-28
BioInfo Pakistan
Site menu
Section categories
Related Subjects [38]
This category includes brief overview of all related subjects.
Defining BioInformatics [7]
In this section we tried to briefly explain what bioinformatics is ?
Unviersities [30]
This contains information about universities that are offering bioinformatics degree programs.
Resources [24]
Contains information about bioinformatics resources including databases, tools and techniques.
Algorithms [31]
This category includes some of the basic algorithms that are usually used by bioinformaticians.
Our poll
Pakistani Students Should Join Bio-Informatics
Total of answers: 35
Chat Box

Total online: 1
Guests: 1
Users: 0
Home » 2011 » August » 22 » Evolution Strategies
11:29 AM
Evolution Strategies

Evolution Strategies

1. Description:
   In computer science, evolution strategy (ES) is an optimization technique based on ideas of adaptation and evolution. It belongs to the general class of evolutionary computation or artificial evolution methodologies.
   The evolution strategy optimization technique was created in the early 1960s and developed further in the 1970s and later by Ingo Rechenberg, Hans-Paul Schwefel and his co-workers.

2. Key Points:
  1. Typically applied to:
    • numerical optimisation
  2. Attributed features:
    • fast
    • good optimizer for real-valued optimisation
    • relatively much theory
  3. Special:
    • self-adaptation of (mutation) parameters standard

Real-valued vectors
Discrete or intermediary
Gaussian perturbation
Parent selection
Uniform random
Survivor selection
(m,l) or (m+l)
Self-adaptation of mutation step sizes

3. Introductory Example:
  1. Task: minimimise f : Rnà R 
  2. Algorithm: "two-membered ES” using  
    • Vectors from Rn directly as chromosomes 
    • Population size 1 
    • Only mutation creating one child 
    • Greedy selection  
  3. Pseudocode:
    • Set t = 0
    • Create initial point xt = á x1t,…,xntñ
    • Draw zi from a normal distr. for all i = 1,…,n
    • yit = xit + zi
    • IF f(xt) < f(yt) THEN xt+1 = xt
      • ELSE xt+1 = yt
      • FI
      • Set t = t+1
    • OD
  4. Mutation Mechanism:
    • z values drawn from normal distribution N(x,s)
      • mean x is set to 0
      • variation s is called mutation step size 
    • s is varied on the fly by the "1/5 success rule”: 
    • This rule resets s after every k iterations by 
      • s = s / c if ps > 1/5 
      • s = s  c if ps < 1/5 
      • s = s if ps = 1/5  
    • where ps is the % of successful mutations, 0.8 £ c £ 1 
  5. Illustration Of Normal Distribution:
4. Representation:
  1. Chromosomes consist of three parts: 
    • Object variables: x1,…,x
    • Strategy parameters:
      • Mutation step sizes: s1,…,sn
      • Rotation angles: a1,…, an
  2. Not every component is always present
  3. Full size: á x1,…,xn, s1,…,sn ,a1,…, ak ñ 
  4. where k = n(n-1)/2 (no. of i,j pairs)
5. Mutation:
  1. Main Mechanism: changing value by adding random noise drawn from normal distribution
  2. x’i = xi + N(0,s)
  3. Key Idea
    1. is part of the chromosome áx1,…,xn,sñ 
    2. is also mutated into s
  4. Thus: mutation step size s is co-evolving with the solution x
6. Recombination:
  1. Creates one child
  2. Acts per variable / position by either
    • Averaging parental values, or
    • Selecting one of the parental values
  3. From two or more parents by either:
    • Using two selected parents to make a child
    • Selecting two parents for each position a new
  4. Names Of Recombinations:


Two fixed parents
Two parents selected for each i
zi=(xi + yi)/2
Local intermediary
Global intermediary
zi is xi or yi chosen randomly

7. Parent Selection:
  1. Parents are selected by uniform random distribution whenever an operator needs one/some 
  2. Thus: ES parent selection is unbiased - every individual has the same probability to be selected
  3. Note that in ES "parent” means a population member (in GA’s: a population member selected to undergo variation)
8. Survivor Selection:
  1. Applied after creating p children from the m parents by mutation and recombination
  2. Deterministically chops off the "bad stuff”
  3. Basis of selection is either:
    • The set of children only: (m,p)-selection
    • The set of parents and children: (m+p)-selection
  4. (m+p)-selection is an elitist strategy
  5. (m,p)-selection can "forget”
  6. Often (m,p)-selection is preferred for:
  7. Better in leaving local optima
  8. Better in following moving optima
  9. Using the + strategy bad m values can survive in áx, too long if their host x is very fit
  10. Selective pressure in ES is very high (» 7 • m is the common setting) 
9. Self-Adaptation Illustrated:
  1. Given a dynamically changing fitness landscape (optimum location shifted every 200 generations)
  2. Self-adaptive ES is able to 
    • follow the optimum and 
    • adjust the mutation step size after every shift !
  3. Prerequisites For Self-Adaptation:
    • m 1 to carry different strategies
    • p > m to generate offspring surplus 
    • Not "too” strong selection, e.g., » 7•m
    • (m,p)-selection to get rid of misadapted s‘s
    • Mixing strategy parameters by (intermediary) recombination on them

Category: Algorithms | Views: 900 | Added by: Ansari | Rating: 0.0/0
Total comments: 0
Name *:
Email *:
Code *:
Log In

«  August 2011  »
Entries archive
Site friends
Copyright MyCorp © 2020
Free website builderuCoz