Search the FAQ Archives

3 - A - B - C - D - E - F - G - H - I - J - K - L - M
N - O - P - Q - R - S - T - U - V - W - X - Y - Z
faqs.org - Internet FAQ Archives

FAQ: comp.ai.genetic part 2/6 (A Guide to Frequently Asked Questions)
Section - Q1.3: What's an Evolution Strategy (ES)?

( Part1 - Part2 - Part3 - Part4 - Part5 - Part6 - Single Page )
[ Usenet FAQs | Web FAQs | Documents | RFC Index | Forum ]


Top Document: FAQ: comp.ai.genetic part 2/6 (A Guide to Frequently Asked Questions)
Previous Document: Q1.2: What's Evolutionary Programming (EP)?
Next Document: Q1.4: What's a Classifier System (CFS)?
See reader questions & answers on this topic! - Help others by sharing your knowledge
     In  1963 two students at the Technical University of Berlin (TUB) met
     and were soon to collaborate  on  experiments  which  used  the  wind
     tunnel  of  the Institute of Flow Engineering.  During the search for
     the optimal shapes of bodies in a flow, which was then  a  matter  of
     laborious  intuitive  experimentation,  the  idea  was  conceived  of
     proceeding strategically.  However, attempts with the coordinate  and
     simple  gradient  strategies  (cf Q5) were unsuccessful.  Then one of
     the  students,  Ingo  Rechenberg,  now  Professor  of   Bionics   and
     Evolutionary  Engineering, hit upon the idea of trying random changes
     in the parameters  defining  the  shape,  following  the  example  of
     natural  MUTATIONs.   The  EVOLUTION  STRATEGY  was  born.   A  third
     student, Peter Bienert, joined them and started the  construction  of
     an  automatic  experimenter, which would work according to the simple
     rules of mutation  and  SELECTION.   The  second  student,  Hans-Paul
     Schwefel,  set  about  testing the efficiency of the new methods with
     the help of a Zuse Z23 computer; for there were plenty of  objections
     to these "random strategies."

     In spite of an occasional lack of financial support, the Evolutionary
     Engineering Group which had been formed held  firmly  together.  Ingo
     Rechenberg  received  his  doctorate  in  1970  (Rechenberg  73).  It
     contains the theory of the two  membered  EVOLUTION  strategy  and  a
     first proposal for a multimembered strategy which in the nomenclature
     introduced here is of the (m+1) type.   In the  same  year  financial
     support  from  the  Deutsche  Forschungsgemeinschaft  (DFG, Germany's
     National Science Foundation) enabled the work, that was concluded, at
     least  temporarily,  in 1974 with the thesis "Evolutionsstrategie und
     numerische Optimierung" (Schwefel 77).

     Thus,  EVOLUTION  STRATEGIEs  were  invented   to   solve   technical
     OPTIMIZATION  problems  (TOPs)  like  e.g.  constructing  an  optimal
     flashing nozzle, and until recently  ES  were  only  known  to  civil
     engineering  folks, as an alternative to standard solutions.  Usually
     no closed form analytical objective function is  available  for  TOPs
     and   hence,  no  applicable  optimization  method  exists,  but  the
     engineer's intuition.

     The first attempts to imitate principles of organic  evolution  on  a
     computer  still resembled the iterative optimization methods known up
     to that time (cf Q5):  In a two-membered  or  (1+1)  ES,  one  PARENT
     generates   one   OFFSPRING   per  GENERATION  by  applying  NORMALLY
     DISTRIBUTED mutations, i.e. smaller steps occur more likely than  big
     ones,  until  a child performs better than its ancestor and takes its
     place. Because of this  simple  structure,  theoretical  results  for
     STEPSIZE control and CONVERGENCE VELOCITY could be derived. The ratio
     between successful and all mutations should  come  to  1/5:  the  so-
     called  1/5  SUCCESS RULE was discovered. This first algorithm, using
     mutation only, has then been  enhanced  to  a  (m+1)  strategy  which
     incorporated  RECOMBINATION  due  to  several,  i.e.  m parents being
     available. The mutation scheme and  the  exogenous  stepsize  control
     were taken across unchanged from  (1+1) ESs.

     Schwefel  later  generalized these strategies to the multimembered ES
     now denoted by (m+l) and (m,l) which  imitates  the  following  basic
     principles  of  organic  evolution:  a  POPULATION,  leading  to  the
     possibility  of  recombination  with  random  mating,  mutation   and
     selection.  These  strategies  are  termed  PLUS  STRATEGY  and COMMA
     STRATEGY, respectively: in the plus case, the parental generation  is
     taken into account during selection, while in the comma case only the
     offspring undergoes selection, and the parents die off. m (usually  a
     lowercase mu, denotes the population size, and l, usually a lowercase
     lambda denotes the number of offspring generated per generation).  Or
     to  put  it  in  an  utterly  insignificant  and  hopelessly outdated
     language:

	  (define (Evolution-strategy population)
	    (if (terminate? population)
	      population
	      (evolution-strategy
		(select
		  (cond (plus-strategy?
			  (union (mutate
				   (recombine population))
				 population))
			(comma-strategy?
			  (mutate
			    (recombine population))))))))

     However, dealing with ES is sometimes seen as "strong  tobacco,"  for
     it takes a decent amount of probability theory and applied STATISTICS
     to understand the inner workings of an ES, while it navigates through
     the  hyperspace  of  the  usually  n-dimensional  problem  space,  by
     throwing hyperelipses into the deep...

     Luckily, this medium doesn't allow for  much  mathematical  ballyhoo;
     the  author  therefore  has  to come up with a simple but brilliantly
     intriguing explanation to save the reader from falling asleep  during
     the rest of this section, so here we go:

     Imagine a black box. A large black box. As large as, say for example,
     a Coca-Cola vending machine. Now, [..] (to be continued)

     A single INDIVIDUAL of the ES' population consists of  the  following
     GENOTYPE representing a point in the SEARCH SPACE:

     OBJECT VARIABLES
	  Real-valued  x_i  have to be tuned by recombination and mutation
	  such that an objective  function  reaches  its  global  optimum.
	  Referring   to   the  metaphor  mentioned  previously,  the  x_i
	  represent the regulators of the alien Coka-Cola vending machine.

     STRATEGY VARIABLEs
	  Real-valued  s_i  (usually denoted by a lowercase sigma) or mean
	  stepsizes determine the mutability of the  x_i.  They  represent
	  the STANDARD DEVIATION of a  (0, s_i) GAUSSIAN DISTRIBUTION (GD)
	  being added to each x_i as  an  undirected  mutation.   With  an
	  "expectancy  value"  of  0  the  parents  will produce offspring
	  similar to themselves on  average.  In order to make a  doubling
	  and  a  halving  of  a stepsize equally probable, the s_i mutate
	  log-normally, distributed,  i.e.  exp(GD),  from  generation  to
	  generation.    These  stepsizes  hide  the  internal  model  the
	  population has made of its ENVIRONMENT, i.e.  a  SELF-ADAPTATION
	  of the stepsizes has replaced the exogenous control of the (1+1)
	  ES.

	  This concept works because selection  sooner  or  later  prefers
	  those  individuals  having  built  a good model of the objective
	  function, thus producing better offspring. Hence, learning takes
	  place  on  two levels: (1) at the genotypic, i.e. the object and
	  strategy variable level and (2) at the  phenotypic  level,  i.e.
	  the FITNESS level.

	  Depending  on  an  individual's  x_i,  the  resulting  objective
	  function value f(x), where x denotes  the  vector  of  objective
	  variables,  serves  as  the PHENOTYPE (fitness) in the selection
	  step. In a plus strategy, the m best of  all  (m+l)  individuals
	  survive to become the parents of the next generation.  Using the
	  comma variant, selection takes place only among the l offspring.
	  The   second   scheme  is  more  realistic  and  therefore  more
	  successful, because no individual  may  survive  forever,  which
	  could  at  least  theoretically  occur  using  the plus variant.
	  Untypical for conventional optimization algorithms and lavish at
	  first    sight,   a   comma   strategy   allowing   intermediate
	  deterioration performs better! Only  by  forgetting  highly  fit
	  individuals  can  a  permanent  adaptation of the stepsizes take
	  place and avoid long stagnation phases due to misadapted  s_i's.
	  This  means  that these individuals have built an internal model
	  that is no longer appropriate for  further  progress,  and  thus
	  should better be discarded.

	  By   choosing  a  certain  ratio  m/l,  one  can  determine  the
	  convergence property of the evolution strategy: If one  wants  a
	  fast,  but  local  convergence,  one  should choose a small HARD
	  SELECTION, ratio, e.g.  (5,100),  but  looking  for  the  global
	  optimum, one should favour  a softer selection (15,100).

	  Self-adaptation  within  ESs  depends  on  the  following agents
	  (Schwefel 87):

     Randomness: One cannot model mutation
	  as a purely random process. This would  mean  that  a  child  is
	  completely independent of its parents.

     Population size: The population has to be sufficiently large. Not
	  only
	  the current best should be allowed to reproduce, but  a  set  of
	  good  individuals.   Biologists  have coined the term "requisite
	  variety" to mean the genetic  variety  necessary  to  prevent  a
	  SPECIES   from   becoming  poorer  and  poorer  genetically  and
	  eventually dying out.

     COOPERATION:
	  In order to exploit the effects of a population  (m  >  1),  the
	  individuals should recombine their knowledge with that of others
	  (cooperate)  because  one  cannot  expect   the   knowledge   to
	  accumulate in the best individual only.
     Deterioration: In order to allow better internal models (stepsizes)
	  to  provide  better  progress  in  the future, one should accept
	  deterioration from one generation to the next. A  limited  life-
	  span  in nature is not a sign of failure, but an important means
	  of preventing a species from freezing genetically.

	  ESs prove to be successful  when  compared  to  other  iterative
	  methods  on a large number of test problems (Schwefel 77).  They
	  are adaptable to nearly all sorts of problems  in  optimization,
	  because  they  need  very  little information about the problem,
	  especially no derivatives of the objective function. For a  list
	  of  some  300  applications  of EAs, see the SyS-2/92 report (cf
	  Q14).  ESs are capable of solving high dimensional,  multimodal,
	  nonlinear   problems   subject   to   linear   and/or  nonlinear
	  constraints.  The objective  function  can  also,  e.g.  be  the
	  result of a SIMULATION, it does not have to be given in a closed
	  form.  This also holds for the constraints which  may  represent
	  the  outcome  of, e.g. a finite elements method (FEM).  ESs have
	  been adapted to VECTOR OPTIMIZATION problems (Kursawe  92),  and
	  they can also serve as a heuristic for NP-complete combinatorial
	  problems like the TRAVELLING SALESMAN PROBLEM or problems with a
	  noisy or changing response surface.

	  References

	  Kursawe,   F.   (1992)   "   Evolution   strategies  for  vector
	  optimization", Taipei, National Chiao Tung University,  187-193.

	  Kursawe,  F.  (1994)  "  Evolution  strategies: Simple models of
	  natural processes?", Revue Internationale de Systemique,  France
	  (to appear).

	  Rechenberg,    I.   (1973)   "Evolutionsstrategie:   Optimierung
	  technischer Systeme nach Prinzipien der biologischen Evolution",
	  Stuttgart: Fromman-Holzboog.

	  Schwefel,    H.-P.    (1977)    "Numerische    Optimierung   von
	  Computermodellen  mittels   der   Evolutionsstrategie",   Basel:
	  Birkhaeuser.

	  Schwefel,  H.-P.  (1987)  "Collective Phaenomena in Evolutionary
	  Systems", 31st Annu.  Meet.  Inter'l  Soc.  for  General  System
	  Research, Budapest, 1025-1033.

User Contributions:

1
Report this comment as inappropriate
Sep 18, 2019 @ 6:06 am
Get $1000 – $6000 A Day: https://hec.su/lVGm?&nqwer=D1dLXHNih6KQY
2
Report this comment as inappropriate
Sep 18, 2019 @ 8:08 am
How to make $3000 a day: https://hec.su/l0tn?&gcaos=ez6p0l9qS
3
Report this comment as inappropriate
Sep 18, 2019 @ 10:10 am
Bitcoin rate is growing. Become a millionaire. Get a passive income of $ 3,500 per day.: https://hec.su/nI6E?&qnoht=iQVr9
4
Report this comment as inappropriate
Sep 19, 2019 @ 8:08 am
BuyEssayClub | Buy Essay Papers Online: https://vk.cc/9OTGak?id=buyessayonline1129nv
5
Report this comment as inappropriate
Sep 19, 2019 @ 11:11 am
Buy Essay Online At Writing Service from Canada: https://vk.cc/9OTGak?id=buyessayonline1131p2
6
Report this comment as inappropriate
Sep 20, 2019 @ 2:14 pm
Buy Essay Online At Writing Service from Canada: https://vk.cc/9OTGak?id=buyessayonline111lir
7
Report this comment as inappropriate
Sep 20, 2019 @ 6:18 pm
BuyEssayClub | Buy Essay Papers Online: https://vk.cc/9OTGak?id=buyessayonline112os9
8
Report this comment as inappropriate
Sep 26, 2019 @ 12:12 pm
Find yourself a girl for the night in your city: https://bogazicitente.com/bestsexygirls357413?u=im
The best girls for sex in your town: https://is.gd/sexygirlsinyourcity28232?u=ch
These Are The Best Sex Apps For No Strings Attached Sex: https://jtbtigers.com/bestsexygirls595902?u=kj
Meet sexy girls in your city: https://ecuadortenisclub.com/bestsexygirls741435?u=31
Best Casual Online Dating Sites: https://vae.me/WNIe?u=46j
Best Dating Apps 2019: https://ecuadortenisclub.com/bestsexygirls741435?u=2x
10 Best Sex Dating Sites (100% Free): https://fla.kr/bestsexygirls107078?u=4d
Adult Dating Site, Meet and Fuck - 445 girls want to meet for sex in your city: https://bestsexygirlsinyourcity.blogspot.tw?j=64
Single girls want sex in your city (447 beautiful girls want sex in your city right now): https://1borsa.com/adultdatingsex21747?s=7328
How to find a woman for casual sex (554 women want to meet for sex in your city): https://bestadultdatingsite999.blogspot.it?z=34
Sex Dating Sites - Online Adult Dating - 541 beautiful girls want sex in your city right now: https://bestadultdatingsite999.blogspot.de?h=01
#1 Adult Sex Dating App - 143 beautiful women want sex in your city right now: https://the-best-adult-dating-sites.blogspot.com.au?d=63
Meet for Sex - Find Sex Tonight, Free Fuck Sites - 719 girls want to meet for sex in your city: https://adultdating-sites777.blogspot.co.uk?f=55
Meet a sexy girl right now (558 girls want to meet for sex in your city): https://links.wtf/NH73?i=8949
Adult Dating Site, Meet and Fuck - 164 girls want to meet for sex in your city: https://the-best-adult-dating-sites.blogspot.com.br?h=41
Women are looking for sex in your city (468 girls want to meet for sex in your city): https://the-best-adult-dating-sites.blogspot.com.ar?c=99
Wie man 0,78 BTC pro Woche macht: https://make5btcperweek.blogspot.ie?u=02
Genau wie wГјrden Sie mit Sicherheit 6537 US-Dollar einsetzen, um mehr Geld zu verdienen?: https://10-btc-per-week.blogspot.ie?t=632
Paid Surveys: Make $9135 Or More Each week: https://7-btc-per-day.blogspot.co.uk?c=290
How to make $ 8866 per day: https://1-btc-per-day.blogspot.hu?s=307
How to Make $5799 FAST, Quick Cash, The Busy Budgeter: https://earn1btcperdayy.blogspot.gr?u=80
Just how would certainly you make use of $86563 to make more cash: https://make-5-btc-perweek.blogspot.ro?c=99
How to invest in Bitcoin and receive from $ 8994 per day: https://get-2-btc-perday.blogspot.fr?q=28
Just how would you use $78353 to make more loan: https://onlineuniversalwork.com/earnonebtc368010?i=1136
32
Report this comment as inappropriate
Oct 17, 2019 @ 6:18 pm
How to Make $9626 FAST, Quick Loan, The Busy Budgeter: https://hideuri.com/KGRoJ1?&eiobg=bLGRhqg8E78r
Exactly how would certainly you use $75381 to make more money: https://cutt.us/dUSpW1R?VoGv0ewk4lh
Paid Studies: Make $8858 Or More Weekly: https://cutt.us/NXb9BT?YYXTiyb2r0
Binary options + Cryptocurrency = $ 4493 per week: https://soo.gd/uGVjo?&rtfvw=eVHII
Paid Surveys: Earn $6131 Or More Per Week: https://cutt.us/TdlXNKi?immdbsvr2GtfC
Just how to Make $5197 FAST, Fast Loan, The Busy Budgeter: https://soo.gd/ejy9?fnJto
How to make $ 5733 per day: https://soo.gd/Uxpm?&bxqyi=G0iYUbCQMUrb
Invest $ 65218 in Bitcoin once and get $ 242513 passive income per month: https://soo.gd/YnggI?0xdy5mrg7FtOn
How to invest in Cryptocurrency $ 31292 - get a return of up to 8716%: https://cutt.us/QHnNLOx7V?JT03TPYKMDJFu
Your account has accumulated $914326,98: https://soo.gd/UpFF
Sex Websites for Meeting Singles, Adult Dating Sites - 742 beautiful girls want sex in your city right now: https://slimex365.com/yfm1
Sex Dating Sites - Online Adult Dating - 631 women want to meet for sex in your city: https://slimex365.com/yfdu
Free Adult Dating & Sex Hookups - 725 beautiful women want sex in your city right now: https://links.wtf/rdAD
How to invest in Bitcoin and receive from $ 4497 per day: https://jtbtigers.com/wqae
Just how to Make $8268 FAST, Fast Money, The Busy Budgeter: https://jtbtigers.com/wnrq
What's the simplest way to gain $83429 a month: https://links.wtf/Kalw
Paid Studies: Make $5364 Or More Weekly: https://ecuadortenisclub.com/wnmf
Invest $ 39849 in Bitcoin once and get $ 653544 passive income per month: https://jtbtigers.com/wq3n
How to invest in Bitcoin and receive from $ 9686 per day: https://bogazicitente.com/x5ha
How to get $ 9333 per day: https://jtbtigers.com/wq4f
52
Report this comment as inappropriate
Nov 2, 2019 @ 3:03 am
Binary options + Cryptocurrency = $ 9889 per week: https://fla.kr/rCsr
Paid Studies: Make $7774 Or More Per Week: https://fla.kr/rCjf
Forex + Cryptocurrency = $ 9163 per week: https://links.wtf/KSfv
Invest $ 9811 and get $ 26859 every month: https://fla.kr/rBm3
Just how to Make $6628 FAST, Rapid Loan, The Busy Budgeter: https://darknesstr.com/wxng
Invest $ 99458 in Bitcoin once and get $ 264919 passive income per month: https://bogazicitente.com/x5r5
Invest $ 69465 in Cryptocurrency once and get $ 743496 passive income per month: https://ecuadortenisclub.com/earnonebitcoinperday63756
Paid Surveys: Make $5589 Or Even more Weekly: https://links.wtf/oLOc
56
Report this comment as inappropriate
Apr 3, 2021 @ 2:14 pm
injectable drug for erectile dysfunction https://alprostadildrugs.com/ buy muse alprostadil urethral suppository
57
Report this comment as inappropriate
Apr 7, 2021 @ 3:15 pm
sildenafil pfizer https://eunicesildenafilcitrate.com/ sildenafil 25
58
Report this comment as inappropriate
Apr 9, 2021 @ 10:22 pm
https://ingogf.com/ - female viagra name in pakistan
59
Report this comment as inappropriate
Jul 27, 2021 @ 7:07 am
Thank you for the good writeup. It in reality was a amusement account it. Glance complex to more brought agreeable from you! However, how could we keep up a correspondence?
60
Report this comment as inappropriate
Aug 1, 2021 @ 10:22 pm
hydroxychloroquinine https://plaquenilx.com/# hydroxychloroquine tablet
61
Report this comment as inappropriate
Oct 7, 2021 @ 8:08 am
you are in point of fact a good webmaster. The web site loading speed is amazing. It sort of feels that you are doing any unique trick. Also, The contents are masterpiece. you have done a wonderful task on this subject! slitet hår efter blekning jado.teswomango.com/map25.php
62
Report this comment as inappropriate
Jan 14, 2022 @ 3:03 am
"May I just say what a comfort to uncover someone that really understands what they are talking about on the web. You actually know how to bring an issue to light and make it important. A lot more people need to check this out and understand this side of the story. It's surprising you are not more popular given that you certainly have the gift."
https://tinyurl.com/y7h69pcq
63
Report this comment as inappropriate
May 3, 2022 @ 2:02 am
"This is the perfect website for anybody who hopes to understand this topic. You realize a whole lot its almost hard to argue with you (not that I personally will need toÖHaHa). You definitely put a brand new spin on a subject that has been discussed for decades. Excellent stuff, just great!"
https://delhiescortss.com/%D7%97%D7%91%D7%99%D7%9C%D7%95%D7%AA-%D7%A1%D7%A4%D7%90-%D7%9E%D7%A4%D7%A0%D7%A7%D7%95%D7%AA-%D7%91%D7%93%D7%A8%D7%95%D7%9D-%D7%A1%D7%A4%D7%90-%D7%A4%D7%9C%D7%95%D7%A1/
64
Report this comment as inappropriate
May 5, 2022 @ 9:09 am
"Next time I read a blog, Hopefully it won't disappoint me just as much as this particular one. After all, I know it was my choice to read, nonetheless I really believed you'd have something interesting to talk about. All I hear is a bunch of moaning about something you can fix if you were not too busy searching for attention."
https://rokslides.com/%d7%a2%d7%99%d7%a1%d7%95%d7%99-%d7%98%d7%a0%d7%98%d7%a8%d7%99-%d7%a2%d7%91%d7%95%d7%93%d7%aa-%d7%a2%d7%95%d7%9e%d7%a7-%d7%a2%d7%9d-%d7%94%d7%92%d7%95%d7%a3/
65
Report this comment as inappropriate
Jun 17, 2022 @ 3:03 am
"The very next time I read a blog, I hope that it does not fail me as much as this one. After all, Yes, it was my choice to read, but I truly thought you'd have something interesting to say. All I hear is a bunch of whining about something that you could fix if you were not too busy searching for attention."
https://lover-israil-graf.gq/news/spathathcaro
66
Report this comment as inappropriate
Sep 27, 2022 @ 2:02 am
stx21 Sist Swalley silled pokoje pracownicze nieopodal suwalk noclegi augustow agroturystyka noclegi wojciech augustow noclegi augustow jezioro biale w augustowie

Comment about this article, ask questions, or add new information about this topic:




Top Document: FAQ: comp.ai.genetic part 2/6 (A Guide to Frequently Asked Questions)
Previous Document: Q1.2: What's Evolutionary Programming (EP)?
Next Document: Q1.4: What's a Classifier System (CFS)?

Part1 - Part2 - Part3 - Part4 - Part5 - Part6 - Single Page

[ Usenet FAQs | Web FAQs | Documents | RFC Index ]

Send corrections/additions to the FAQ Maintainer:
David.Beasley@cs.cf.ac.uk (David Beasley)





Last Update March 27 2014 @ 02:11 PM