"Evolutionäre Algorithmen - Verfahren, Operatoren, Hinweise aus der Praxis"

Hartmut Pohlheim
Berlin, Heidelberg, New York: Springer-Verlag
322 Seiten, 105 Abbildungen und Tabellen
mit Matlab-Toolbox auf CD-ROM (GEATbx 1.95, Vollversion)

ISBN 3-540-66413-0 (erschienen: Oktober 1999)
Preis: DM 98,- DM
www.pohlheim.com/eavoh/

Inhaltsverzeichnis

Abkürzungsverzeichnis XIII

1 Einleitung 1

2 Struktur und Aufbau Evolutionärer Algorithmen 7

3 Grundlegende Verfahren und Operatoren 13
- 3.1 Fitneßzuweisung 16
  - 3.1.1 Proportionale Fitneßzuweisung 17
  - 3.1.2 Reihenfolgebasierte Fitneßzuweisung (Ranking) 18
  - 3.1.3 Mehrkriterielle Fitneßzuweisung 20
- 3.2 Selektion 24
  - 3.2.1 Rouletteselektion 25
  - 3.2.2 Stochastic universal sampling 25
  - 3.2.3 Turnierselektion 26
  - 3.2.4 Truncation-Selektion 27
  - 3.2.5 Analyse der Selektionsverfahren 28
  - 3.2.6 Vergleich der Selektionsverfahren 31
- 3.3 Rekombination 34
  - 3.3.1 Diskrete Rekombination 35
  - 3.3.2 Rekombination reeller und ganzzahliger Variablen 35
  - 3.3.3 Rekombination binärer Variablen (crossover) 39
  - 3.3.4 Rekombination bei kombinatorischen Problemen 42
- 3.4 Mutation 46
  - 3.4.1 Mutation reeller und ganzzahliger Variablen 47
  - 3.4.2 Mutation reeller Variablen mit Adaption der Schrittweiten 51
  - 3.4.3 Mutation binärer Variablen 53
  - 3.4.4 Mutation bei kombinatorischen Problemen 54
- 3.5 Wiedereinfügen (Reinsertion) 57
- 3.6 Initialisierung der Individuen 60
  - 3.6.1 Zufällige Initialisierung 61
  - 3.6.2 Erweiterte Initialisierung (nicht-zufällig) 62
- 3.7 Abbruchkriterien 63
  - 3.7.1 Direkte Abbruchkriterien 64
  - 3.7.2 Abgeleitete Abbruchkriterien 65
  - 3.7.3 Einsatz der Abbruchkriterien 70
- 3.8 Zusammenfassung 71

4 Populationen, verschiedene Strategien und Konkurrenz 73
- 4.1 Klassifikation von Populationsmodellen 74
- 4.2 Globales Modell 75
- 4.3 Lokales Modell 77
  - 4.3.1 Topologie von Nachbarschaften 78
  - 4.3.2 Allgemeine Beschreibung von Nachbarschaften 79
  - 4.3.3 Selektion in Nachbarschaft 83
  - 4.3.4 Wiedereinfügen in Nachbarschaft 83
  - 4.3.5 Analyse des lokalen Modells 84
- 4.4 Regionales Modell 87
  - 4.4.1 Anzahl und Größe der Unterpopulationen 89
  - 4.4.2 Migrationstopologien 90
  - 4.4.3 Migrationsintervall und Migrationsrate 92
  - 4.4.4 Auswahl der Migranten 94
  - 4.4.5 Ablauf der Migration 94
  - 4.4.6 Analyse des regionalen Modells 95
- 4.5 Anwendung verschiedener Strategien 96
  - 4.5.1 Berechnung der Ordnung der Unterpopulationen 97
  - 4.5.2 Beispiel der Anwendung verschiedener Strategien 99
  - 4.5.3 Analyse der Anwendung verschiedener Strategien 101
- 4.6 Konkurrierende Unterpopulationen 102
  - 4.6.1 Erfolg der Unterpopulationen 103
  - 4.6.2 Aufteilung der Ressourcen 103
  - 4.6.3 Umsetzung der Verteilung der Ressourcen 105
  - 4.6.4 Beispiel des Einsatzes konkurrierender Unterpopulationen 108
  - 4.6.5 Analyse der konkurrierenden Unterpopulationen 111
- 4.7 Zusammenfassung 113

5 Visualisierung und Optimierung 115
- 5.1 Systematisierung der Visualisierung von EA 116
  - 5.1.1 Kriterien der Systematisierung 116
  - 5.1.2 Daten zur Visualisierung 117
  - 5.1.3 Schema der Systematisierung 118
- 5.2 Globale Eigenschaften einer Population 119
  - 5.2.1 Zielfunktionswert des besten Individuums der Population (Konvergenzdiagramm) 119
  - 5.2.2 Variablen des jeweils besten Individuums einer Population 121
  - 5.2.3 Zielfunktionswerte (Güte) aller Individuen über mehrere Generationen 123
  - 5.2.4 Position und Größe der Unterpopulationen 127
- 5.3 Lokale Eigenschaften einer Population 128
  - 5.3.1 Variablen aller Individuen einer Generation 128
  - 5.3.2 Zielfunktionswerte aller Individuen einer Generation 131
  - 5.3.3 Distanzverteilung und Distanzkarten der Individuen einer Generation 134
- 5.4 Hochdimensionale Visualisierung 138
  - 5.4.1 Verfahren 138
  - 5.4.2 Anwendung der mehrdimensionalen Visualisierung 140
  - 5.4.3 Analyse der mehrdimensionalen Visualisierung 143
- 5.5 Eigenschaften der Zielfunktion 144
  - 5.5.1 Direkte Darstellung der Zielfunktion 145
  - 5.5.2 Fitneß-Distanz-Verteilung 148
  - 5.5.3 Visualisierung problemspezifischer Daten und Ergebnisse 150
- 5.6 Protokollierung von Daten und Ergebnissen 152
- 5.7 Zusammenfassung und Ausblick 153

6 Genetic and Evolutionary Algorithm Toolbox for Matlab 157
- 6.1 Aufbau und Struktur der GEATbx 158
- 6.2 Anwenderschnittstelle – Scriptfunktionen 161
- 6.3 Vordefinierte Algorithmen – Toolboxfunktionen 161
- 6.4 Zentralfunktion 162
  - 6.4.1 Initialisierung 163
  - 6.4.2 Fitneßzuweisung und Selektion 163
  - 6.4.3 Rekombination 164
  - 6.4.4 Mutation 165
  - 6.4.5 Wiedereinfügen 165
  - 6.4.6 Migration und Konkurrenz zwischen Unterpopulationen 166
  - 6.4.7 Terminierung 166
  - 6.4.8 Visualisierung 166
  - 6.4.9 Protokollierung 167
- 6.5 Zielfunktionen und Beispiele 168
- 6.6 Einbeziehung problemspezifischen Wissens 169
- 6.7 Dokumentation 169
- 6.8 Zusammenfassung und Ausblick 170

7 Kombination von Operatoren zu Evolutionären Algorithmen 171
- 7.1 Allgemein einstellbare Verfahren und Operatoren 172
  - 7.1.1 Fitneßzuweisung und Selektion 172
  - 7.1.2 Anwendung verschiedener Strategien und Konkurrenz zwischen Unterpopulationen 173
  - 7.1.3 Regionales Populationsmodell (Migration zwischen Unterpopulationen) 174
  - 7.1.4 Zusammenfassung allgemein einstellbare Verfahren 174
- 7.2 Global orientierte Parameteroptimierung 175
- 7.3 Lokal orientierte Parameteroptimierung 176
- 7.4 Parameteroptimierung binärer Variablen 178
- 7.5 Kombinatorische Optimierung 179
- 7.6 Parameteroptimierung von Variablen verschiedener Repräsentation 181
- 7.7 Zusammenfassung 184

8 Anwendung Evolutionärer Algorithmen auf Praxisprobleme 185
- 8.1 Vorgehen bei der Lösung von Optimierungsaufgaben 186
  - 8.1.1 Einordnung des Problems und Festlegung der Zielfunktion 187
  - 8.1.2 Untersuchungen des Systemverhaltens 188
  - 8.1.3 Festlegung des Optimierungsverfahrens 191
  - 8.1.4 Durchführung und Auswertung von Optimierungen 192
- 8.2 Optimierung mehrdimensionaler Funktionen 194
  - 8.2.1 Verwendete Optimierungsverfahren 195
  - 8.2.2 RASTRIGIN’s Funktion 196
  - 8.2.3 ROSENBROCK’s Funktion 198
  - 8.2.4 Moved axis parallel hyper-ellipsoid Funktion 201
  - 8.2.5 Zusammenfassung mehrdimensionale Funktionen 204
- 8.3 Parameteridentifikation eines Dieselmotormodells 204
  - 8.3.1 Beschreibung des Systems 205
  - 8.3.2 Untersuchungen des Systemverhaltens 207
  - 8.3.3 Zielfunktion für die Optimierung 211
  - 8.3.4 Verwendetes Optimierungsverfahren 213
  - 8.3.5 Problemspezifische Visualisierung 214
  - 8.3.6 Ergebnisse der Optimierungen 215
  - 8.3.7 Auswertung der Ergebnisse 222
  - 8.3.8 Zusammenfassung Parameteridentifikation Dieselmotor 224
- 8.4 Optimierung der Parameter eines Reglers (Fahrzeuglenkung) 226
  - 8.4.1 Modell der Querlenkung 226
  - 8.4.2 Anforderungen an den Regler 227
  - 8.4.3 Simulation des Gesamtsystems 228
  - 8.4.4 Aufstellung der Zielfunktion 229
  - 8.4.5 Durchführung der Optimierung 232
  - 8.4.6 Ergebnisse der Optimierung 234
  - 8.4.7 Zusammenfassung Fahrzeuglenkung 238
- 8.5 Steuerung eines komplexen Systems (Gewächshausklima) 239
  - 8.5.1 Einleitung 239
  - 8.5.2 Kurzbeschreibung des Gewächshausklimamodells 240
  - 8.5.3 Repräsentation der Individuen und Zielfunktion 242
  - 8.5.4 Einbeziehung problemspezifischen Wissens 243
  - 8.5.5 Optimale Steuerung für durchschnittliche Tage 244
  - 8.5.6 Optimale Steuerung bei veränderten Preisen 246
  - 8.5.7 Optimale Steuerung unter Verwendung realer Wetterdaten 247
  - 8.5.8 Zusammenfassung Gewächshausklima 252
- 8.6 Zusammenfassung 253

9 Schlußbetrachtungen 257
- 9.1 Zusammenfassung 257
- 9.2 Ausblick 261

Anhang 267
- A.1 Historische Entwicklung Evolutionärer Algorithmen 267
  - A.1.1 Erste Arbeiten zu Evolutionären Algorithmen 267
  - A.1.2 Evolutionäre Programmierung 271
  - A.1.3 Evolutionsstrategien 272
  - A.1.4 Genetische Algorithmen 273
  - A.1.5 Evolutionäre Algorithmen heute 275
- A.2 Gewächshaus- und Pflanzenmodell 276
  - A.2.1 Zustandsgleichungen des Gewächshauses 276
  - A.2.2 Zustandsgleichungen des Pflanzenmodells (Paprika) 278
  - A.2.3 Biomasse und Gewinn 279
  - A.2.4 Beschränkungen 280

Literaturverzeichnis 281

Glossar 297

Sachverzeichnis 307

Vorwort

Einleitung

Übersicht

Bestellung

Neuigkeiten

Inhalt

Literatur

Glossar

pohlheim.com