Evolutionary algorithms and optimization [Elektronische Ressource] / von Axel Reimann

Dipl. Phys. Axel Reimann

Sujets

• Mathematics

Informations

• Publié par: humboldt-universitat_zu_berlin
• Publié le: 01 janvier 2002
• Nombre de lectures: 17
• Langue: Deutsch
• Poids de l'ouvrage: 4 Mo

Extrait

Evolutionary Algorithms and Optimization
D I S S E R T A T I O N
zur Erlangung des akademischen Grades
doctor rerum naturalium
(dr. rer. nat.)
im Fach Physik
eingereicht an der
Mathematisch Naturwissenschaftlichen Fakultat¨ I
Humboldt Universitat¨ zu Berlin
von
Herr Dipl. Phys. Axel Reimann
geboren am 28.05.1973 in Hennigsdorf
Prasident¨ der Humboldt Universitat¨ zu Berlin:
¨Prof. Dr. Jurgen Mlynek
Dekan der Mathematisch Naturwissenschaftlichen Fakultat¨ I:
Prof. Dr. Michael Linscheid
Gutachter:
1. Prof. Dr. Werner Ebeling
2. Prof. Dr. Heinz Muhlenbein¨
3. PD Dr. Dr. Frank Schweitzer
eingereicht am: 20. August 2001
Tag der mundlichen¨ Prufung:¨ 5. Dezember 2002Zusammenfassung
Diese Arbeit beschaftigt¨ sich mit dem Thema Evolutionar¨ e Algorithmen und deren Verwen
dung fur¨ Optimierungsaufgaben. Im ersten Teil der Arbeit werden die theoretischen Grund
lagen ausfuhrlich¨ dargelegt, die zum Verstandnis¨ der Problemstellung und der vorgeschlage
nen Losungsm¨ oglichk¨ eiten notwendig sind. Dazu gehoren¨ die Einfuhrung¨ des Konzeptes von
Fitneßlandschaften, deren Eigenschaften sowie die kurze Darstellung bekannter stochastischer
Optimierungsverfahren wie z.B. Simulated Annealing. Im Anschluß daran wird auf neue Ver-
fahren – insbesondere gemischte Strategien – eingegangen und diese vergleichend gegenuber¨
den herkommlichen¨ Verfahren abgegrenzt.
Die neu entwickelten Verfahren werden an Modellproblemen getestet, welche im zweiten Teil
der Arbeit vorgestellt werden. Verwendet wurden sowohl einfache theoretische Modelle wie
Frustrierte Periodische Sequenzen als auch praktisch relevante Probleme wie das der RNA Se
kundarstrukturen.¨ Die verschiedenen Modellprobleme werden bezuglich¨ ihrer Eigenschaften
und Schwierigkeitsgrade untersucht und miteinander verglichen, um die Effizienz der verwende
ten Optimierungsverfahren abschatzen¨ zu konnen.¨
Der dritte Teil der Arbeit prasentiert¨ wichtige Ergebnisse der im Rahmen dieser Arbeit durch
gefuhrten¨ umfangreichen numerischen Simulationen. Es wird demonstriert, wie sensitiv die
Optimierungsergebnisse von den verwendeten Parametern der Algorithmen (wie z.B. Ensem
blegroße,¨ Temperatur oder Mutationsrate) abhangen¨ und das ein relativ scharf umrissenes evo
¨lutionares Fenster der Parameter existiert, innerhalb dessen die Optimierungsresultate deutlich
besser sind. Eine im Rahmen dieser Arbeit entwickelte adaptive Parametersteuerung wird an
den im zweiten Teil vorgestellten Modellproblemen getestet und gezeigt, daß es moglich¨ ist, den
Optimierungsprozeß automatisch innerhalb des evolutionaren¨ Fensters zu halten.
Der letzte Teil gibt Einblick in die im Rahmen dieser Arbeit verwendete Computer Software und
das vom Autor entwickelte Programmpaket. Es wird hervorgehoben, daß die in C++ objekto
rientiert und modular geschriebene Software leicht an andere Optimierungsaufgaben angepaßt
werden kann und dank graphischer Benutzeroberflache¨ auch einfach zu bedienen ist.EVOLUTIONARY ALGORITHMS
AND OPTIMIZATION
Axel ReimannAuthor: Axel Reimann, 2001
Cover : Ribonucleic Acid, Structure of loop E from E. Coli 5s Rrna
ORGANISM SCIENTIFIC: Escheria coli
C. C. Correll, B. Freeborn, P. B. Moore and T. A. Steitz
30th Sep. 1997, PDB Code: 354D
visualized using Cn3D
This document was typeset using pdfT XE
Copyright (C) 1999 Han The Thanh, Petr Sojka, and Jiri Zlatuska
pdfT X is covered by the terms of both theE
pdfT X copyright and the GNU General Public LicenseEDedicated to my parents and friends.Contents
1 Introduction 9
2 Learning from Nature 11
2.1 The Theoretical Framework . . . . . . . . . . . . . . . . . . . . 11
2.1.1 The Concept of Fitness Landscapes . . . . . . . . . . . 12
2.1.2 Properties of Fitness . . . . . . . . . . . . . 14
The Density of States . . . . . . . . . . . . . . . . . . . 15
The Autocorrelation Function . . . . . . . . . . . . . . 17
2.1.3 Stochastic Modeling of Basic Evolutionary Strategies . . 20
The Darwin Strategy . . . . . . . . . . . . . . . . . . . 21
The Boltzmann Strategy . . . . . . . . . . . . . . . . . 23
The Mixed Boltzmann Darwin Strategy . . . . . . . . . 25
2.1.4 Other Stochastic Optimization Strategies . . . . . . . . 27
Simulated Annealing . . . . . . . . . . . . . . . . . . . 27
Genetic Algorithms . . . . . . . . . . . . . . . . . . . . 28
3 Model Problems 31
3.1 Correlated Random Landscapes . . . . . . . . . . . . . . . . . 31
3.2 Frustrated Periodic Sequences . . . . . . . . . . . . . . . . . . 34
3.3 The LABS Problem . . . . . . . . . . . . . . . . . . . . . . . . 35
3.4 The RNA and NK Model Compared . . . . . . . . . . . . . . . 36
13.4.1 The NK Model . . . . . . . . . . . . . . . . . . . . . . 36
3.4.2 RNA Secondary Structures . . . . . . . . . . . . . . . . 38
4 Optimizing the Search Process 43
4.1 Exact Stochastic Simulations . . . . . . . . . . . . . . . . . . . 43
4.1.1 The Direct Method . . . . . . . . . . . . . . . . . . . . 44
4.1.2 The First Reaction Method . . . . . . . . . . . . . . . . 45
4.1.3 The Next Method . . . . . . . . . . . . . . . . 45
4.2 The Evolutionary Window . . . . . . . . . . . . . . . . . . . . 46
4.2.1 Comparing Fitness Landscapes . . . . . . . . . . . . . . 46
4.2.2 Exploring Parameter Windows . . . . . . . . . . . . . . 50
1. Constant Temperature . . . . . . . . . . . . . . . . . 52
2. Variable T . . . . . . . . . . . . . . . . . 54
4.3 Mastering Intrinsic Search Parameters . . . . . . . . . . . . . . 58
4.3.1 Ensemble Size Adaptation . . . . . . . . . . . . . . . . 58
4.3.2 Temperature . . . . . . . . . . . . . . . . . 59
4.3.3 Mutation Rate Adaptation . . . . . . . . . . . . . . . . 61
First Approach: The Ensemble Variability . . . . . . . . 64
Second The Relative Ensemble Dispersion . 66
Third Approach: The Ensemble Entropy . . . . . . . . . 68
4.4 An Adaptive Evolutionary Algorithm . . . . . . . . . . . . . . 73
5 Software 77
5.1 Newly Developed Software . . . . . . . . . . . . . . . . . . . . 77
5.1.1 Optimization Programs . . . . . . . . . . . . . . . . . . 77
The User Interface . . . . . . . . . . . . . . . . . . . . 78
The Workflow . . . . . . . . . . . . . . . . . . . . . . 78
5.1.2 The SimRNA Mutation Operator . . . . . . . . . . . . . 80