VDI 6224 Blatt 1-2012 Biomimetic optimization - Application of evolutionary algorithms.pdf

1、VEREIN DEUTSCHERINGENIEUREBionische OptimierungEvolutionre Algorithmen in der AnwendungBiomimetic optimizationApplication of evolutionary algorithmsVDI 6224Blatt 1 / Part 1Ausg. deutsch/englischIssue German/EnglishVDI-Handbuch BionikVDI-RICHTLINIENZubeziehen durch /Available at BeuthVerlag GmbH,1077

2、2 Berlin AlleRechtevorbehalten /All rights reserved Verein Deutscher Ingenieuree.V.,Dsseldorf 2012Vervielfltigung auchfr innerbetrieblicheZwecke nichtgestattet / Reproduction evenfor internal use not permittedICS 07.080 Juni 2012 June 2012FrhereAusgabe: 06.11 Entwurf Former edition: 06/11DraftVDI-Ge

3、sellschaft Technologies of Life Sciences (TLS)Fachbereich BionikInhalt SeiteVorbemerkung . . . . . . . . . . . . . . . . . . . 2Einleitung . . . . . . . . . . . . . . . . . . . . . . 21 Anwendungsbereich . . . . . . . . . . . . . . 42 Begriffe . . . . . . . . . . . . . . . . . . . . . 43 Formelzeich

4、en . . . . . . . . . . . . . . . . . 44 Prinzipielle Vorgehensweise in der evolutionren Optimierung. . . . . . . . . . . 54.1 Aufgabenstellung . . . . . . . . . . . . . . 54.2 Mathematische Modellierung . . . . . . . . 54.3 Verwendeter Evolutionrer Algorithmus . . 64.4 Beispiel einer einfachen ( /,

5、)-CMSA-Evolutionsstrategie . . . 94.5 Optimierungsverlauf und Ergebnisse . . . . 125 Beispiele zur Durchfhrung des Verfahrens . 155.1 Kontinuierliche Optimierung . . . . . . . . 155.2 Optimierung mit diskreten Parametern . . . 185.3 Kombinatorische Optimierung . . . . . . . 235.4 Subjektive Optimier

6、ung . . . . . . . . . . . 266 Weitere Problemklassen . . . . . . . . . . . . 296.1 Optimierung unter mehrfacher Zielsetzung. 296.2 Optimierung unter Nebenbedingungen . . . 326.3 Optimierung unter Unsicherheiten . . . . . 337 Abschlieende Bemerkungen . . . . . . . . . 347.1 Historische Algorithmen .

7、. . . . . . . . . 347.2 Abgrenzung zu anderen Optimierungsstrategien . . . . . . . . . . . 347.3 Andere bionische Verfahren. . . . . . . . . 35Anhang . . . . . . . . . . . . . . . . . . . . . . . 37Schrifttum. . . . . . . . . . . . . . . . . . . . . . 38Contents PagePreliminary note . . . . . . . .

8、. . . . . . . . . . 2Introduction . . . . . . . . . . . . . . . . . . . . 21 Scope . . . . . . . . . . . . . . . . . . . . . . 42 Terms and definitions . . . . . . . . . . . . . 43 Symbols. . . . . . . . . . . . . . . . . . . . . 44 Basic approach to evolutionary optimization . . . . . . . . . . . 5

9、4.1 Problem definition . . . . . . . . . . . . . 54.2 Mathematical model . . . . . . . . . . . . 54.3 Evolutionary algorithms used . . . . . . . 64.4 Example of a simple ( /, )- CMSA evolution strategy. . . . 94.5 Optimization process and results . . . . . . 125 Examples of application of the method

10、. . . . 155.1 Continuous optimization . . . . . . . . . . 155.2 Optimization with discrete parameters . . . 185.3 Combinatorial optimization . . . . . . . . 235.4 Subjective optimization. . . . . . . . . . . 266 Additional classes of problems . . . . . . . . 296.1 Optimization of multiple objectives

11、 . . . . 296.2 Optimization with constraints . . . . . . . 326.3 Optimization with uncertainties . . . . . . 337 Closing remarks . . . . . . . . . . . . . . . . 347.1 Historical algorithms . . . . . . . . . . . . 347.2 Differences from other optimization strategies . . . . . . . . . . . 347.3 Other

12、biomimetic methods . . . . . . . . . 35Annex . . . . . . . . . . . . . . . . . . . . . . . 37Bibliography . . . . . . . . . . . . . . . . . . . . 38Die deutsche Version dieser Richtlinie ist verbindlich. The German version of this guideline shall be taken as authorita-tive. No guarantee can be given

13、 with respect to the English trans-lation.Zubeziehen durch /Available at BeuthVerlag GmbH,10772 Berlin AlleRechtevorbehalten /All rights reserved Verein Deutscher Ingenieuree.V.,Dsseldorf 2012B55EB1B3E14C22109E918E8EA43EDB30F09DCCB7EF86D9NormCD - Stand 2012-08Alle Rechte vorbehalten Verein Deutscher

14、 Ingenieure e.V., Dsseldorf 2012 2 VDI 6224 Blatt 1 / Part 1VorbemerkungDer Inhalt dieser Richtlinie ist entstanden unter Be-achtung der Vorgaben und Empfehlungen der Richt-linie VDI 1000.Alle Rechte, insbesondere die des Nachdrucks, der Fotokopie, der elektronischen Verwendung und der bersetzung, j

15、eweils auszugsweise oder vollstndig, sind vorbehalten.Die Nutzung dieser VDI-Richtlinie ist unter Wahrung des Urheberrechts und unter Beachtung der Lizenz-bedingungen (www.vdi-richtlinien.de), die in den VDI-Merkblttern geregelt sind, mglich.Allen, die ehrenamtlich an der Erarbeitung dieser VDI-Rich

16、tlinie mitgewirkt haben, sei gedankt.Eine Liste der aktuell verfgbaren Bltter dieser Richtlinienreihe ist im Internet abrufbar unter www.vdi.de/6224.EinleitungEvolutionre Algorithmen sind bionische Optimie-rungsverfahren, deren erste Varianten in den 1960er- Jahren entstanden sind. Mit diesen Algori

17、thmen kn-nen schwierige Optimierungsprobleme gelst wer-den, fr die keine Standardverfahren anwendbar sind, weil z. B. keine Gradienteninformationen, nur ver-rauschte Bewertungen oder noch nicht einmal eine mathematisch formulierbare Zielfunktion vorliegen. Die Grundidee Evolutionrer Algorithmen (EA)

18、 lei-tet sich von den Prinzipien der darwinschen Evolu-tion ab: Individuen stehen im Wettstreit um Ressour-cen (Nahrung, Lebensraum, Fortpflanzungspartner). Besonders gut angepasste oder starke Individuen ha-ben besseren Zugang zu den Ressourcen und damit eine erhhte Chance zur Fortpflanzung. Das Ma

19、 ih-rer Fhigkeit, sich fortzupflanzen, wird als Fitness“ bezeichnet; diese hngt von den Eigenschaften des Individuums, dem sogenannten Phnotyp ab. Die phnotypischen Eigenschaften ihrerseits werden (ne-ben der Umwelt) hauptschlich durch den Bauplan“ des Individuums der Menge der Gene (das Genom, der

20、Genotyp) bestimmt. Individuen mit guter Fit-ness bertragen per Definition mit grerem Erfolg ihre Bauplne auf die Nachkommen der nchsten Ge-neration. Dieses Prinzip, auch als survival of the fit-test“ bezeichnet, stellt die eine Seite des darwinschen Evolutionsprinzips dar die Selektion.Hherentwicklu

21、ng ist jedoch nur mglich, wenn ver-schiedene Bauplne also Genome in der Popula-tion vorhanden sind, wenn also genetische Varia-tion“ in der Individuenpopulation vorhanden ist. Se-lektion kann dann die bezglich der Fitness besten Preliminary noteThe content of this guideline has been developed in str

22、ict accordance with the requirements and recom-mendations of the guideline VDI 1000.All rights are reserved, including those of reprinting, reproduction (photocopying, micro copying), storage in data processing systems and translation, either of the full text or of extracts.The use of this guideline

23、 without infringement of copy-right is permitted subject to the licensing conditions specified in the VDI Notices (www.vdi-richtlinien.de). We wish to express our gratitude to all honorary con-tributors to this guideline.A catalogue of all available parts of this series of guidelines can be accessed

24、 on the internet at www.vdi.de/6224.IntroductionEvolutionary algorithms are biomimetic optimization methods. The first versions of these methods were de-veloped in 1960s. With evolutionary algorithms, it is possible to solve difficult optimization problems for which no standard optimization method c

25、an be ap-plied because there is no gradient information availa-ble, only noisy evaluations are available, or there is not even a mathematical formulation of the target function available, for example.The basic concept of evolutionary algorithms (EAs) is derived from the principles of Darwinian evolu

26、tion: Individuals compete with each other for resources (food, territory, reproduction partners). Especially well-adapted or strong individuals have better access to the resources and therefore a higher chance of re-producing. The measure of an individuals ability to reproduce is referred to as its

27、“fitness”. Its fitness de-pends on the characteristics of the individual, the so-called phenotype. The phenotypic characteristics, on the other hand, are determined primarily by the “con-struction plan” of the individual, meaning its set of genes (the genome or the genotype), as well as by the envir

28、onment. By definition, individuals with “good” fitness are able to transfer their construction plans to the offspring of the next generation with greater suc-cess. This principle, which is also referred to as “sur-vival of the fittest”, is one of the principles of Darwin-ian evolution namely the pri

29、nciple of selection.Higher development is only possible, though, when different construction plans i. e. genomes are present in the population, which therefore means there is “genetic variation” in the population of indi-viduals. Selection can then prefer the best construc-B55EB1B3E14C22109E918E8EA4

30、3EDB30F09DCCB7EF86D9NormCD - Stand 2012-08All rights reserved Verein Deutscher Ingenieure e.V., Dsseldorf 2012 VDI 6224 Blatt 1 / Part 1 3 Bauplne prferieren. Genetische Variation entsteht durch zwei Prozesse, durch Rekombination der Gene verschiedener Individuen und durch Mutation. Rekombination mi

31、scht die genetische Information zweier oder mehrerer Individuen, die aufgrund ihrer Fitness selektiert wurden; dadurch entstehen neue Genome und damit, phnotypisch gesehen, neue In-dividuen.Mutationen ndern das Genom eines Individuums zu-fllig. Whrend die Selektion am Phnotyp angreift, erfolgt die V

32、ariation durch genetische Operatoren“ (Mutation und Rekombination) am Genotyp.Der Prozess Variation und Selektion ndert das gene-tische Material von der Elternpopulation zur Nach-kommenpopulation, dies entspricht einer Generation. Die wiederholte Anwendung (Iteration) definiert eine Evolutionsschlei

33、fe, in der das System schrittweise bezglich der Fitnesswerte verbessert wird.Evolutionre Algorithmen (EA) verwenden die Prin-zipien der Variation (Mutation und Rekombination) und Selektion, iterativ ausgefhrt in einer Evolutions-schleife, zum Evolvieren neuer Lsungen mit dem Ziel der Systemverbesser

34、ung und Optimierung. Hier-bei liefert die Variation das genetische Material (Diversitt) und die Selektion gibt der Evolution die (gewnschte) Richtung.Die algorithmische Umsetzung des darwinschen Evo-lutionsparadigmas kann auf verschiedene Art und Weise erfolgen und unterscheidet sich unter anderem a

35、uch in dem Grad, wie die biologische Maschinerie nachgebildet wird. Historisch gesehen haben sich so verschiedene Unterklassen von EA herausgebildet: Genetische Algorithmen (GA) 41, Evolutionsstrate-gien (ES) 39; 40 und Evolutionary Programming (EP) 42. Neben diesen historisch in ihren Grundver-sion

36、en schon seit den 1960er-Jahren bekannten Ver-fahren, sind noch weitere bionische Optimierungsver-fahren (siehe Abschnitt 7.3) zu erwhnen, die jedoch nicht Inhalt dieser Beschreibung sind.Am Beispiel der Optimierung einer Prismenlinse wird in Abschnitt 4 die prinzipielle Vorgehensweise in der evolut

37、ionren Optimierung beschrieben. In Abschnitt 5 werden Beispiele zur Durchfhrung des Verfahrens fr die Problemklassen kontinuierliche Optimierung, Optimierung mit diskreten Parametern, kombinatorische Optimierung und subjektive Opti-mierung gezeigt. Abschnitt 6 behandelt die Themen mehrfache Zielsetz

38、ung, Nebenbedingungen und un-sichere Bewertung.tion plans in terms of their fitness. Genetic variation arises through two different processes, through re-combination of the genes of different individuals and through mutation.Recombination mixes the genetic information of two or more individuals sele

39、cted based on their fitness. This produces new genomes, and therefore new indi-viduals in terms of their phenotypes. Mutations randomly change the genome of an indi-vidual. While selection is based on the phenotype, variation is achieved on the genotype using “genetic operators” (mutation and recomb

40、ination).The process of variation and selection changes the genetic material of the parent population in the off-spring population, which corresponds to one genera-tion. Repeated application (iteration) defines an evo-lutionary loop in which the system is improved step-by-step in terms of its fitnes

41、s values.Evolutionary algorithms (EAs) use the principles of variation (mutation and recombination) and selec-tion, executed iteratively in an evolutionary loop, to evolve new solutions with the objective of improving and optimizing the system. In this process, variation supplies the genetic materia

42、l (diversity) and selection pushes evolution in the (desired) direction. The Darwinian evolution paradigm can be imple-mented algorithmically in various ways. These im-plementations differ in the degree to which they model the biological machinery, among other differ-ences. When viewed historically,

43、 this has resulted in the creation of various subclasses of EAs: genetic al-gorithms (GA) 41, evolution strategies (ES)39; 40, and evolutionary programming (EP) 42. In addition to these methods, basic versions of which have been known historically since the 1960s, there are other biomimetic optimiza

44、tion methods (see Section 7.3) available, but these are not described in the following.Section 4 describes the basic evolutionary optimiza-tion procedure based on an example of the optimiza-tion of a prism lens. Section 5 presents examples of the execution of this method for continuous optimiza-tion

45、 problems, optimization problems with discrete parameters, combinatorial optimization problems, and subjective optimization problems. Section 6 han-dles the subject of multiple objectives, constraints, and uncertain evaluations. B55EB1B3E14C22109E918E8EA43EDB30F09DCCB7EF86D9NormCD - Stand 2012-08All

46、e Rechte vorbehalten Verein Deutscher Ingenieure e.V., Dsseldorf 2012 4 VDI 6224 Blatt 1 / Part 11 AnwendungsbereichDie Richtlinie wendet sich vorrangig an Ingenieure, die Optimierungsprobleme zu lsen haben, fr die keine Standardlsungen oder Algorithmen bekannt sind, fr die Standardlsungen oder Algo

47、rithmen nicht den gewnschten Erfolg bringen, deren Lsung mit herkmmlichen Verfahren ab-sehbar zu aufwendig erscheinen.Um in diesen Fllen Evolutionre Algorithmen er-folgreich anwenden zu knnen, sollten gewisse De-signprinzipien beachtet werden, die in dieser Richt-linie detaillierter ausgefhrt werden

48、.2 BegriffeFr die Anwendung dieser Richtlinie gelten die Be-griffe der Richtlinien VDI/VDE 3550 Blatt 3 und VDI 6220.3 FormelzeichenIn dieser Richtlinie werden die nachfolgend aufge-fhrten Formelzeichen verwendet:Formel- zeichen BedeutungD Definitionsbereich des Optimierungs-problemsn Dimension des

49、OptimierungsproblemsN Zufallsvektor, ZufallszahlMenge der natrlichen ZahlenMenge der reellen Zahlenx* Stelle des Extremums des Optimie-rungsproblemsX Definitionsbereich des Optimierungs-problemsMenge der ganzen Zahlen Isolationszeitparameter Zahl der Nachkommen Zahl der selektierten Eltern Zahl der an der Rekombination beteilig-ten Individuen Lernparameter+ Es wird eine Plus-Selektion durchge-fhrt., Es wird eine Komma-Selekt