🗊Презентация Evolution strategies. Chapter 4

Категория: Математика
Нажмите для полного просмотра!
Evolution strategies. Chapter 4, слайд №1Evolution strategies. Chapter 4, слайд №2Evolution strategies. Chapter 4, слайд №3Evolution strategies. Chapter 4, слайд №4Evolution strategies. Chapter 4, слайд №5Evolution strategies. Chapter 4, слайд №6Evolution strategies. Chapter 4, слайд №7Evolution strategies. Chapter 4, слайд №8Evolution strategies. Chapter 4, слайд №9Evolution strategies. Chapter 4, слайд №10Evolution strategies. Chapter 4, слайд №11Evolution strategies. Chapter 4, слайд №12Evolution strategies. Chapter 4, слайд №13Evolution strategies. Chapter 4, слайд №14Evolution strategies. Chapter 4, слайд №15Evolution strategies. Chapter 4, слайд №16Evolution strategies. Chapter 4, слайд №17Evolution strategies. Chapter 4, слайд №18Evolution strategies. Chapter 4, слайд №19Evolution strategies. Chapter 4, слайд №20Evolution strategies. Chapter 4, слайд №21Evolution strategies. Chapter 4, слайд №22Evolution strategies. Chapter 4, слайд №23Evolution strategies. Chapter 4, слайд №24Evolution strategies. Chapter 4, слайд №25Evolution strategies. Chapter 4, слайд №26Evolution strategies. Chapter 4, слайд №27Evolution strategies. Chapter 4, слайд №28Evolution strategies. Chapter 4, слайд №29Evolution strategies. Chapter 4, слайд №30Evolution strategies. Chapter 4, слайд №31Evolution strategies. Chapter 4, слайд №32
Скачать

Содержание ▲

Вы можете ознакомиться и скачать презентацию на тему Evolution strategies. Chapter 4. Доклад-сообщение содержит 32 слайдов. Презентации для любого класса можно скачать бесплатно. Если материал и наш сайт презентаций Mypresentation Вам понравились – поделитесь им с друзьями с помощью социальных кнопок и добавьте в закладки в своем браузере.

Слайды и текст этой презентации

Слайд 1


Evolution strategies Chapter 4
Описание слайда:
Evolution strategies Chapter 4

Слайд 2


ES quick overview Developed: Germany in the 1970’s Early names: I. Rechenberg, H.-P. Schwefel Typically applied to: numerical optimisation Attributed features: fast good optimizer for real-valued optimisation relatively much theory Special: self-adaptation of (mutation) parameters standard
Описание слайда:
ES quick overview Developed: Germany in the 1970’s Early names: I. Rechenberg, H.-P. Schwefel Typically applied to: numerical optimisation Attributed features: fast good optimizer for real-valued optimisation relatively much theory Special: self-adaptation of (mutation) parameters standard

Слайд 3


ES technical summary tableau
Описание слайда:
ES technical summary tableau

Слайд 4


Introductory example Task: minimimise f : Rn  R Algorithm: “two-membered ES” using Vectors from Rn directly as chromosomes Population size 1 Only mutation creating one child Greedy selection
Описание слайда:
Introductory example Task: minimimise f : Rn  R Algorithm: “two-membered ES” using Vectors from Rn directly as chromosomes Population size 1 Only mutation creating one child Greedy selection

Слайд 5


Introductory example: pseudocde 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
Описание слайда:
Introductory example: pseudocde 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

Слайд 6


Introductory example: mutation mechanism z values drawn from normal distribution N(,) mean  is set to 0 variation  is called mutation step size  is varied on the fly by the “1/5 success rule”: This rule resets  after every k iterations by  =  / c if ps > 1/5  =  • c if ps < 1/5  =  if ps = 1/5 where ps is the % of successful mutations, 0.8  c  1
Описание слайда:
Introductory example: mutation mechanism z values drawn from normal distribution N(,) mean  is set to 0 variation  is called mutation step size  is varied on the fly by the “1/5 success rule”: This rule resets  after every k iterations by  =  / c if ps > 1/5  =  • c if ps < 1/5  =  if ps = 1/5 where ps is the % of successful mutations, 0.8  c  1

Слайд 7


Illustration of normal distribution
Описание слайда:
Illustration of normal distribution

Слайд 8


Another historical example: the jet nozzle experiment
Описание слайда:
Another historical example: the jet nozzle experiment

Слайд 9


Another historical example: the jet nozzle experiment cont’d
Описание слайда:
Another historical example: the jet nozzle experiment cont’d

Слайд 10


The famous jet nozzle experiment (movie)
Описание слайда:
The famous jet nozzle experiment (movie)

Слайд 11


Genetic operators: mutations (2)
Описание слайда:
Genetic operators: mutations (2)

Слайд 12


Representation Chromosomes consist of three parts: Object variables: x1,…,xn Strategy parameters: Mutation step sizes: 1,…,n Rotation angles: 1,…, n Not every component is always present Full size:  x1,…,xn, 1,…,n ,1,…, k  where k = n(n-1)/2 (no. of i,j pairs)
Описание слайда:
Representation Chromosomes consist of three parts: Object variables: x1,…,xn Strategy parameters: Mutation step sizes: 1,…,n Rotation angles: 1,…, n Not every component is always present Full size:  x1,…,xn, 1,…,n ,1,…, k  where k = n(n-1)/2 (no. of i,j pairs)

Слайд 13


Mutation Main mechanism: changing value by adding random noise drawn from normal distribution x’i = xi + N(0,) Key idea:  is part of the chromosome  x1,…,xn,    is also mutated into ’ (see later how) Thus: mutation step size  is coevolving with the solution x
Описание слайда:
Mutation Main mechanism: changing value by adding random noise drawn from normal distribution x’i = xi + N(0,) Key idea:  is part of the chromosome  x1,…,xn,    is also mutated into ’ (see later how) Thus: mutation step size  is coevolving with the solution x

Слайд 14


Mutate  first Net mutation effect:  x,     x’, ’  Order is important: first   ’ (see later how) then x  x’ = x + N(0,’) Rationale: new  x’ ,’  is evaluated twice Primary: x’ is good if f(x’) is good Secondary: ’ is good if the x’ it created is good Reversing mutation order this would not work
Описание слайда:
Mutate  first Net mutation effect:  x,     x’, ’  Order is important: first   ’ (see later how) then x  x’ = x + N(0,’) Rationale: new  x’ ,’  is evaluated twice Primary: x’ is good if f(x’) is good Secondary: ’ is good if the x’ it created is good Reversing mutation order this would not work

Слайд 15


Mutation case 1: Uncorrelated mutation with one  Chromosomes:  x1,…,xn,   ’ =  • exp( • N(0,1)) x’i = xi + ’ • N(0,1) Typically the “learning rate”   1/ n½ And we have a boundary rule ’ < 0  ’ = 0
Описание слайда:
Mutation case 1: Uncorrelated mutation with one  Chromosomes:  x1,…,xn,   ’ =  • exp( • N(0,1)) x’i = xi + ’ • N(0,1) Typically the “learning rate”   1/ n½ And we have a boundary rule ’ < 0  ’ = 0

Слайд 16


Mutants with equal likelihood Circle: mutants having the same chance to be created
Описание слайда:
Mutants with equal likelihood Circle: mutants having the same chance to be created

Слайд 17


Mutation case 2: Uncorrelated mutation with n ’s Chromosomes:  x1,…,xn, 1,…, n  ’i = i • exp(’ • N(0,1) +  • Ni (0,1)) x’i = xi + ’i • Ni (0,1) Two learning rate parmeters: ’ overall learning rate  coordinate wise learning rate   1/(2 n)½ and   1/(2 n½) ½ And i’ < 0  i’ = 0
Описание слайда:
Mutation case 2: Uncorrelated mutation with n ’s Chromosomes:  x1,…,xn, 1,…, n  ’i = i • exp(’ • N(0,1) +  • Ni (0,1)) x’i = xi + ’i • Ni (0,1) Two learning rate parmeters: ’ overall learning rate  coordinate wise learning rate   1/(2 n)½ and   1/(2 n½) ½ And i’ < 0  i’ = 0

Слайд 18


Mutants with equal likelihood Ellipse: mutants having the same chance to be created
Описание слайда:
Mutants with equal likelihood Ellipse: mutants having the same chance to be created

Слайд 19


Mutation case 3: Correlated mutations Chromosomes:  x1,…,xn, 1,…, n ,1,…, k  where k = n • (n-1)/2 and the covariance matrix C is defined as: cii = i2 cij = 0 if i and j are not correlated cij = ½ • ( i2 - j2 ) • tan(2 ij) if i and j are correlated Note the numbering / indices of the ‘s
Описание слайда:
Mutation case 3: Correlated mutations Chromosomes:  x1,…,xn, 1,…, n ,1,…, k  where k = n • (n-1)/2 and the covariance matrix C is defined as: cii = i2 cij = 0 if i and j are not correlated cij = ½ • ( i2 - j2 ) • tan(2 ij) if i and j are correlated Note the numbering / indices of the ‘s

Слайд 20


Correlated mutations cont’d The mutation mechanism is then: ’i = i • exp(’ • N(0,1) +  • Ni (0,1)) ’j = j +  • N (0,1) x ’ = x + N(0,C’) x stands for the vector  x1,…,xn  C’ is the covariance matrix C after mutation of the  values   1/(2 n)½ and   1/(2 n½) ½ and   5° i’ < 0  i’ = 0 and | ’j | >   ’j = ’j - 2  sign(’j)
Описание слайда:
Correlated mutations cont’d The mutation mechanism is then: ’i = i • exp(’ • N(0,1) +  • Ni (0,1)) ’j = j +  • N (0,1) x ’ = x + N(0,C’) x stands for the vector  x1,…,xn  C’ is the covariance matrix C after mutation of the  values   1/(2 n)½ and   1/(2 n½) ½ and   5° i’ < 0  i’ = 0 and | ’j | >   ’j = ’j - 2  sign(’j)

Слайд 21


Mutants with equal likelihood Ellipse: mutants having the same chance to be created
Описание слайда:
Mutants with equal likelihood Ellipse: mutants having the same chance to be created

Слайд 22


Recombination Creates one child Acts per variable / position by either Averaging parental values, or Selecting one of the parental values From two or more parents by either: Using two selected parents to make a child Selecting two parents for each position anew
Описание слайда:
Recombination Creates one child Acts per variable / position by either Averaging parental values, or Selecting one of the parental values From two or more parents by either: Using two selected parents to make a child Selecting two parents for each position anew

Слайд 23


Names of recombinations
Описание слайда:
Names of recombinations

Слайд 24


Parent selection Parents are selected by uniform random distribution whenever an operator needs one/some Thus: ES parent selection is unbiased - every individual has the same probability to be selected Note that in ES “parent” means a population member (in GA’s: a population member selected to undergo variation)
Описание слайда:
Parent selection Parents are selected by uniform random distribution whenever an operator needs one/some Thus: ES parent selection is unbiased - every individual has the same probability to be selected Note that in ES “parent” means a population member (in GA’s: a population member selected to undergo variation)

Слайд 25


Survivor selection Applied after creating  children from the  parents by mutation and recombination Deterministically chops off the “bad stuff” Basis of selection is either: The set of children only: (,)-selection The set of parents and children: (+)-selection
Описание слайда:
Survivor selection Applied after creating  children from the  parents by mutation and recombination Deterministically chops off the “bad stuff” Basis of selection is either: The set of children only: (,)-selection The set of parents and children: (+)-selection

Слайд 26


Survivor selection cont’d (+)-selection is an elitist strategy (,)-selection can “forget” Often (,)-selection is preferred for: Better in leaving local optima Better in following moving optima Using the + strategy bad  values can survive in x, too long if their host x is very fit Selective pressure in ES is very high (  7 •  is the common setting)
Описание слайда:
Survivor selection cont’d (+)-selection is an elitist strategy (,)-selection can “forget” Often (,)-selection is preferred for: Better in leaving local optima Better in following moving optima Using the + strategy bad  values can survive in x, too long if their host x is very fit Selective pressure in ES is very high (  7 •  is the common setting)

Слайд 27


Self-adaptation illustrated Given a dynamically changing fitness landscape (optimum location shifted every 200 generations) Self-adaptive ES is able to follow the optimum and adjust the mutation step size after every shift !
Описание слайда:
Self-adaptation illustrated Given a dynamically changing fitness landscape (optimum location shifted every 200 generations) Self-adaptive ES is able to follow the optimum and adjust the mutation step size after every shift !

Слайд 28


Self-adaptation illustrated cont’d
Описание слайда:
Self-adaptation illustrated cont’d

Слайд 29


Prerequisites for self-adaptation  > 1 to carry different strategies  >  to generate offspring surplus Not “too” strong selection, e.g.,   7 •  (,)-selection to get rid of misadapted ‘s Mixing strategy parameters by (intermediary) recombination on them
Описание слайда:
Prerequisites for self-adaptation  > 1 to carry different strategies  >  to generate offspring surplus Not “too” strong selection, e.g.,   7 •  (,)-selection to get rid of misadapted ‘s Mixing strategy parameters by (intermediary) recombination on them

Слайд 30


Example application: the cherry brandy experiment Task to create a colour mix yielding a target colour (that of a well known cherry brandy) Ingredients: water + red, yellow, blue dye Representation:  w, r, y ,b  no self-adaptation! Values scaled to give a predefined total volume (30 ml) Mutation: lo / med / hi  values used with equal chance Selection: (1,8) strategy
Описание слайда:
Example application: the cherry brandy experiment Task to create a colour mix yielding a target colour (that of a well known cherry brandy) Ingredients: water + red, yellow, blue dye Representation:  w, r, y ,b  no self-adaptation! Values scaled to give a predefined total volume (30 ml) Mutation: lo / med / hi  values used with equal chance Selection: (1,8) strategy

Слайд 31


Example application: cherry brandy experiment cont’d Fitness: students effectively making the mix and comparing it with target colour Termination criterion: student satisfied with mixed colour Solution is found mostly within 20 generations Accuracy is very good
Описание слайда:
Example application: cherry brandy experiment cont’d Fitness: students effectively making the mix and comparing it with target colour Termination criterion: student satisfied with mixed colour Solution is found mostly within 20 generations Accuracy is very good

Слайд 32


Example application: the Ackley function (Bäck et al ’93) The Ackley function (here used with n =30): Evolution strategy: Representation: -30 < xi < 30 (coincidence of 30’s!) 30 step sizes (30,200) selection Termination : after 200000 fitness evaluations Results: average best solution is 7.48 • 10 –8 (very good)
Описание слайда:
Example application: the Ackley function (Bäck et al ’93) The Ackley function (here used with n =30): Evolution strategy: Representation: -30 < xi < 30 (coincidence of 30’s!) 30 step sizes (30,200) selection Termination : after 200000 fitness evaluations Results: average best solution is 7.48 • 10 –8 (very good)

Скачать

Похожие презентации
Mypresentation.ru
Загрузить презентацию