VDI VDE 3550 Blatt 3-2003 Computational intelligence - Evolutionary algorithms - Terms and definitions.pdf

1、VEREIN DEUTSCHERINGENIEUREVERBAND DERELEKTROTECHNIKELEKTRONIKINFORMATIONSTECH-NIKComputational IntelligenceEvolutionre AlgorithmenBegriffe und DefinitionenEvolutionary algorithmsTerms and definitionsVDI/VDE 3550Blatt 3/ Part 3Ausg. deutsch/englischIssue German/EnglishVDI/VDE-Gesellschaft Mess- und A

2、utomatisierungstechnik (GMA)Fachausschuss Neuronale Netze und Evolutionre AlgorithmenVDI/VDE-Handbuch RegelungstechnikVDI/VDE-RICHTLINIENZubeziehen durch/Available fromBeuth Verlag GmbH, 10772 BerlinAlleRechtevorbehalten / AllrightsreservedVereinDeutscherIngenieure, Dsseldorf 2003Vervielfltigungauch

3、frinnerbetrieblicheZweckenichtgestattet/ReproductionevenforinternalusenotpermittedDie deutsche Version dieser Richtlinie ist verbindlich.ICS 17.020Februar 2003February 2003The German version of this guideline shall be taken as authorita-tive. No guarantee can be given with respect to the English tra

4、ns-lation.Inhalt SeiteVorbemerkung . . . . . . . . . . . . . . . . . . . . 21 Zweck und Geltungsbereich . . . . . . . . . . 22 Begriffe und Definitionen. . . . . . . . . . . . 33 Englische Begriffe mit Verweisen auf dasGlossar . . . . . . . . . . . . . . . . . . . . . . 16Schrifttum . . . . . . . .

5、. . . . . . . . . . . . 18Contents PagePreliminary note . . . . . . . . . . . . . . . . . . . 21 Objective and scope . . . . . . . . . . . . . . . 22 Terms and definitions . . . . . . . . . . . . . . 33 English terms with reprimands to the glossary . . . . . . . . . . . . . . . . . . . . . . 16Bibli

6、ography . . . . . . . . . . . . . . . . . . . . . 18FrhereAusgabe:11.01,Entwurf,deutschFormeredition:11/01,draft,in GermanonlyB55EB1B3E14C22109E918E8EA43EDB30F09DCCB7EF86D9NormCD - Stand 2012-08All rights reserved Verein Deutscher Ingenieure, Dsseldorf 20032 VDI/VDE 3550 Blatt 3 / Part 3Vorbemerkung

7、Evolutionre Algorithmen (EA) haben als universellanwendbare Verbesserungs- und Optimierungsstrate-gien seit Beginn der 1990er Jahre eine weite Verbrei-tung in allen Bereichen von Wirtschaft und For-schung gefunden. Der groe Erfolg liegt dabei unteranderem in der Tatsache begrndet, dass ihre Anwen-du

8、ng auf einem scheinbar einfachen und leicht nach-vollziehbaren Prinzip, dem Darwinschen Evoluti-onsparadigma“ oder etwas zugespitzt ausgedrckt dem survival of the fittest“ basiert: Durch die An-wendung von Variation und Selektion auf eine Popu-lation von Lsungsalternativen werden nach demMuster der

9、Natur schrittweise bessere Lsungen ge-funden und auf diese Weise Optima bestimmt oderzumindest approximiert.Bedingt durch die einfachen Grundprinzipien hatsich in den vergangenen Jahren eine Unzahl von Va-rianten der EA gebildet (Anzahl der jhrlichenVerffentlichungen zurzeit grer als 1000). War dieF

10、rhphase der EA-Geschichte noch durch disjunkteEA-Klassen gekennzeichnet, die Genetischen Algo-rithmen (GA), die Evolutionsstrategie (ES) und dieEvolutionre Programmierung (EP), so findet manzunehmend eine Vermischung all dieser Anstze.Aus diesem Grund wurde der Oberbegriff Evolutio-nre Algorithmen“

11、eingefhrt. Neben der allgemei-nen Verwendung dieses Begriffes sollte dieser immerdann zur Anwendung kommen, wenn die spezielle-ren, in dieser Richtlinie genauer definierten EA-Vari-anten nicht zutreffen.Da es auf Grund der international groen Zahl vonVerffentlichungen und der Vielzahl von EA-Varian-

12、ten zu einem Wildwuchs von Begriffen gekommenist, besteht ein groer Bedarf an Systematisierungund Standardisierung. Aus diesem Grund hat sich derFachausschuss Neuronale Netze und EvolutionreAlgorithmen“ der VDI/VDE-Gesellschaft Mess- undAutomatisierungstechnik (GMA) entschlossen, diewichtigsten Begr

13、iffe aus dem EA-Bereich in einerRichtlinie zusammenzufassen und zu definieren.1 Zweck und GeltungsbereichDer Zweck dieser Richtlinie ist es, eine einheitlicheBegriffs- und Definitionsbasis fr den Bereich derEvolutionren Algorithmen zu liefern. Ein groerTeil der hier zu definierenden Begriffe hat sei

14、nen Ur-sprung in der Biologie und wird dort in hnlicher, je-doch nicht notwendigerweise quivalenter, teilweiseauch abweichender Form/Bedeutung verwendet. DieRichtlinie ist fr die Anwendung im Ingenieurbe-reich gedacht, jedoch nicht darauf beschrnkt.Preliminary noteBeing universally applicable strate

15、gies for improve-ment and optimisation, Evolutionary Algorithms(EA) have become widespread in all fields of econ-omy and research since the early 1990. Among otherthings, their great success is due to the fact that theirapplication is based on a seemingly simple and easilycomprehensible principle, n

16、amely ”Darwins evolu-tion paradigm“ or, put in somewhat stronger terms,the principle of the ”survival of the fittest“: Like inNature, solutions are improved step by step, and op-tima are identified, or at least approximated, by ap-plying variation and selection to a population of alter-native soluti

17、ons.In recent years, countless EA variants have come intoexistence as a result of the simple basic principles(number of publications per year presently exceeding1000). Whereas the early phase of EA history wasstill marked by disjunct EA classes, Genetic Algo-rithms (GA), Evolution Strategy (ES), and

18、 Evolution-ary Programming (EP), the present trend is towardsmerging all these approaches. The generic term ”Ev-olutionary Algorithms“ has therefore been intro-duced. Apart from its generic meaning, this termshould be used wherever the more specific EA vari-ants defined in greater detail in this gui

19、deline are notapplicable.In view of the terminological jungle that has grown asa consequence of the multitude of international pub-lications and EA variants, there is a great need forsystematization and standardization. For this reason,the technical committee ”Neural Networks and Evo-lutionary Algor

20、ithms“ of the VDI/VDE Society forMeasurement and Automatic Control (VDI/VDE-GMA) has decided to compile and define the mostimportant EA terms in a guideline.1 Objective and scopeThis guideline is intended to provide a harmonizedbasis of terms and definitions for the field of Evolu-tionary Algorithms

21、. Many terms to be defined hereoriginate in biology where a similar, but not necessar-ily equivalent, and sometimes even different, form/meaning is used. This guideline is meant for, but notlimited to, engineering applications.B55EB1B3E14C22109E918E8EA43EDB30F09DCCB7EF86D9NormCD - Stand 2012-08Alle

22、Rechte vorbehalten Verein Deutscher Ingenieure, Dsseldorf 2003 VDI/VDE 3550 Blatt 3 / Part 3 32 Begriffe und DefinitionenTerms and definitionsABCDEAbbruchkriterium Bedingungen, unter denen derEvolutionsprozess im EA termi-niert (Beispiele: Anzahl derFunktionsberechnungen, max.Rechenzeit, Konvergenz

23、im Ziel-funktions- oder Suchraum)Abschneideselek-tion Kommaselektion, Plus-selektionAdaptation Prozess der Anpassung an gege-bene (uere) BedingungenAllele mgliche Ausprgungen des Zu-standes eines Gens (bei bin-rer Reprsentation: 0|1)automatisch definierte Funktion (ADF)Modularisierungskonzept, umdie

24、 Effizienz von GP zu erhhen.Hierzu werden Unterbume ge-bildet, welche in den Hauptbu-men als Funktionen verwendetwerden knnen. Die ADF wer-den in gleicher Weise variiert wiedie Hauptbume.Baldwin-Effekt Vom Baldwin-Effekt sprichtman, wenn bei hybriden Stra-tegien durch lokale Suchverfah-ren der Zielf

25、unktionswert einesIndividuums verndert wird unddies zu einer nderung des Fit-nesswertes, das heit der zu er-wartenden Reproduktionsrate,fhrt. Im Gegensatz zur La-marckschen Evolution bleibtaber der Genotyp unverndert.Baustein-Hypothese (kurz BBH fr engl. building block hypothesis“)Erklrungsversuch f

26、r das Funk-tionieren des (binren) GA aufder Basis des Schematheo-rems. Die BBH basiert auf derAnnahme, dass gnstige Eigen-schaften in den elterlichen Geno-men in (relativ) kleinen Codebl-cken an verschiedenen Stellenaggregiert sind und durch Crossover im Nachkommenzusammengefhrt werden. Dieverbesser

27、te Lsung wird also ausTeillsungen“, den Bausteinen,zusammengebaut“.Bitmutation zufllige Negation einer Bitposi-tion (Gen) im Individuengenom(bei binrer Reprsentation)Block KnotenChromosom Satz der Gene eines IndividuumsCodeaufblhung Phnomen des unkontrolliertenWachstums der Genome von GP-IndividuenC

28、odierung ReprsentationCrossover (CO, XO)(seltener Kreuzung“) spezielleForm der Rekombination inGA bei der zwei Eltern durchGenaustausch (in der Regel)zwei Nachkommen produzieren,Varianten: n-Punkt-CO, unifor-mes CO, problemspezifische COCrossover-Rate Wahrscheinlichkeit fr dieDurchfhrung eines CODif

29、fusionsmodell lokales Populationsmodelldiskrete Rekombinationauch dominante Rekombination,Erzeugung eines Rekombinantendurch koordinatenweise Zufalls-auswahl aus einer Menge von ElternDiversitt Grad bzw. Ma(e) der Verschie-denartigkeit der Individuen aufder Ebene ihrer Genomedominante Rekombination

30、diskrete RekombinationEin-Fnftel-Regel (1/5-Regel)Regel zur Steuerung der Mu-tationsstrke in der (1+1)-ES: InAbhngigkeit von der (gemesse-nen) Erfolgswahrscheinlich-keit Pswird die Mutationsstrkenach einer gewissen Anzahl vonGenerationen vergrert, wennPs 1/5, und verkleinert, wennPs1) als Variati-on

31、soperatoren.Evolvierbare Hardware (EH)spezielle Vorrichtungen, Schalt-kreise oder Maschinen, die eineRealisierung des DarwinschenEvolutionsparadigmas auf mate-rieller Ebene erlauben exogener StrategieparameterStrategieparameter, der whrendder Evolution konstant gehaltenwird, z.B. (in der Regel) Popu

32、lationsgre, Lernpa-rameterFitness Bewertung des Individuums be-zglich seiner Reproduktions-tauglichkeit. Selektion im EAerfolgt auf der Basis der FitnessDie Fitness wird hierfr im All-gemeinen basierend auf dem(n)Zielfunktionswert(en) im Ver-gleich zu allen anderen Indivi-duen im Selektionspool be-s

33、timmt. Die Fitnessfunktionkann zustzlich von verschiede-nen Nebenbedingungen abhn-gen und stochastischen Einfls-sen unterliegen (Fitnessrau-schen). Der Begriff der Fitness-funktion wird hufig synonymzur Zielfunktion verwendet.B55EB1B3E14C22109E918E8EA43EDB30F09DCCB7EF86D9NormCD - Stand 2012-08Alle R

34、echte vorbehalten Verein Deutscher Ingenieure, Dsseldorf 2003 VDI/VDE 3550 Blatt 3 / Part 3 5GFitnesslandschaft auch Gtegebirge, Metapher zurVerdeutlichung der Abhngig-keit der Fitness bzw. Zielfunk-tion von der Lage des Individu-ums im Suchraumfitness-proportionale SelektionSelektionsverfahren, bei

35、 dem dieSelektionswahrscheinlichkeit frein Individuum proportional zudessen Fitness ist. Die Fitnessmuss daher nichtnegativ sein( Skalierungsfunktion). AlsEvolutionsziel ist nur die Maxi-mierung mglich.Fortschritts-geschwindigkeittheoretisches Performancema,Erwartungswert der nderungdes Abstandes zu

36、 einem vordefi-nierten Ziel (in der Regel Opti-mum) in einer GenerationFunktionenmenge Menge problemangemessenerelementarer Funktionen, die alsinnere Knoten zusammen mit derTerminalmenge einem GP zumBilden eines baumfrmigen Indi-viduums zur Verfgung stehen.Beispiele fr Funktionenmengensind arithmeti

37、sche Operationenund mathematische Funktionen+, , , /, sin, cos fr die sym-bolische Regression oder Ele-mente einer Programmierspracheif-then-else, for, do-until, .fr das Bilden von Program-men.Geburtenber-schussberschuss der Geburten gegen-ber der Gre der Elternpopula-tion, notwendige Voraussetzungf

38、r das Funktionieren gewisserSelektionsoperatoren( Kommaselektion)Gen Untereinheit des Chromosoms(Genoms), die in der Regel einen( Objekt-)Parameter bzw. Block (im GP) darstellt oderdafr codiertGeneration (natrliche) Zeiteinheit im EA,eine Iteration des EA, vollstndi-ger Zyklus, der die Bildung undEv

39、aluierung (Fitnessbestim-mung) eines oder mehrerer neuerIndividuen umfasstGenerationslcke Konzept zur Beschreibung ber-lappender Generationen ( sta-tionrer EA), wobei Genera-tionslcke als das Verhltnis derAnzahl der Nachkommen zurGre der Elternpopulation defi-niert istGenetische Programmierung (GP)V

40、ariante der EA, die mit Geno-men variabler Lnge arbeitet undzum Evolvieren symbolischerInformationen dient. Hauptan-wendungsfelder sind das Evol-vieren von Computercode, sym-bolische Regression, automati-scher Schaltungsentwurf. Einehufige Form der Reprsenta-tion ist die baumfrmige Anord-nung der Ge

41、ne als Programm.Genetischer Algorithmus (GA)(auch kanonischer GA, oder ein-facher GA) Variante der EA, diein der Regel in Analogie zum bi-ologischen DNA-Alphabet aufZeichenketten, insbesondere Bit-ketten konstanter Lnge, operiert(siehe aber reellwertiger GA).Die Zeichenkette stellt den Genotyp des I

42、ndividuumsdar. Der Phnotyp des Indivi-duums wird durch eine Abbil-dung auf die Objektparameter(Genotyp-Phnotyp-Abbildung)realisiert. Die Fitness des In-dividuums ist in der Regel eineFunktion der zu optimierenden Zielfunktion, die von den Ob-jektparametern abhngt. Der GAist meist charakterisiert dur

43、ch fitness-proportionale bzw. Turnierselektion, Haupt-Vari-ationsoperator ist Crossover;Mutation ( Bitmutation) istHintergrundoperator oder fehltvollstndig.genetische Drift Zufallsprozess, der auch ohne Selektionsdruck zum Diversi-ttsverlust und zur Gen-Kon-vergenz in endlichen Populatio-nen fhrt. D

44、ie Zeit bis zur Gen-Fixierung ist proportional zur ef-fektiven (das heit reproduzie-renden) Populationsgre.genetische Operatoren VariationsoperatorenB55EB1B3E14C22109E918E8EA43EDB30F09DCCB7EF86D9NormCD - Stand 2012-08All rights reserved Verein Deutscher Ingenieure, Dsseldorf 20036 VDI/VDE 3550 Blatt

45、 3 / Part 3HIGen-Konvergenz Diversittsverlust whrend derEvolution. Von der Gen-Konver-genz kann nicht mit Notwendig-keit auf Konvergenz gegen lo-kale oder globale Optima ge-schlossen werden (Problem der vorzeitigen Konvergenz, engl.premature convergence)Genom Satz der Gene eines Individu-umsGenotyp

46、bei EA mit Genotyp-PhnotypAbbildung, die Reprsenta-tion, auf der die Rekombinati-ons- und Mutationsoperatorenarbeiten ( Phnotyp)genotypische Vari an z DiversittGenpool Gesamtheit der Gene in einer PopulationGenreparatur Ansatz zur Erklrung des mgli-chen Performancegewinns durch Rekombination. Danach

47、 be-steht die Aufgabe der Rekombi-nation in der Extraktion von Ge-meinsamkeiten in der geneti-schen Information der selektier-ten Individuen, da diese mit ge-wisser Wahrscheinlichkeit frden Fitnessgewinn verantwort-lich sind. Ein idealer Rekombi-nationsoperator sollte zudem dieAnteile im Genom, die

48、fr Fit-nessverlust verantwortlich sind,reduzieren. Die Standard-ES-Re-kombinationsoperatoren in reell-wertigen Suchrumen realisierendies durch statistisches Heraus-mitteln von Verlustkomponenten(Genreparatur).geschachtelter EA Meta-EAglobales Populationsmodellauch panmiktische Popula-tion, Populatio

49、nsmodell bei demkeine Unterteilung der Popula-tion stattfindet, zum Selekti-onspool gehren alle Individuender Population. Die Populationwird als unstrukturierte Menge“betrachtet. Individuen aus belie-bigen Bereichen der Populationknnen gemeinsam Nachkom-men bilden. Das globalePopulationsmodell entsprichtdem klassische