Saturday, 2017-07-22, 9:54 AM
Welcome Guest | RSS

Login form

Statistics
Total online: 1
Guests: 1
Users: 0

Is Online User
Site Search
Main » 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

Representation
Real-valued vectors
Recombination
Discrete or intermediary
Mutation
Gaussian perturbation
Parent selection
Uniform random
Survivor selection
(m,l) or (m+l)
Specialty
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ñ
    • REPEAT UNTIL (TERMIN.COND satisfied) DO
    • 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
Local
discrete
Global
discrete

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: 543 | Added by: Ansari | Rating: 0.0/0
Total comments: 0
Name *:
Email *:
Code *:
Tag Board
Your Ads
Site friends

Copyright MyCorp © 2017
Free website builderuCoz