Evolutionäre Algorithmen (German Edition)

Für die Lösung von Optimierungsproblemen mit evolutionären Algorithmen stattet dieses Buch seine Leser sowohl mit den gängigen Standardalgorithmen als auch mit den Arbeitsprinzipien, Vorgehensweisen und speziellen Techniken aus, mit denen evolutionäre Algorithmen für spezielle Probleme angepasst werden. Dabei zeichnen das Buch vor allem die hohe Anzahl an Beispielen, die anschauliche Darstellung der Grundlagen sowie vier ausführliche Fallstudien aus. Für die Anwendung evolutionärer Algorithmen in Industrie, Wirtschaft und Forschung sind die vorgestellten Ansätze zur Berücksichtigung von Randbedingungen, mehrerer sich widersprechender Zielfunktionen und verrauschte oder zeitabhängige Aspekte von großer Bedeutung. Evolutionäre Algorithmen sind ein vergleichsweise junges Optimierungsverfahren, welches das Wechselspiel zwischen Variation und Selektion der natürlichen Evolution imitiert. Vorwort zur dritten Auflage 5 Inhaltsverzeichnis 6 1. Natürliche Evolution 10 1.1. Entwicklung der evolutionären Mechanismen 11 1.2. Evolutionsfaktoren 17 1.2.1. Herleitung der Evolutionsfaktoren 18 1.2.2. Mutation 18 1.2.3. Rekombination 19 1.2.4. Selektion 19 1.2.5. Genfluss 21 1.2.6. Gendrift 21 1.3. Anpassung als Resultat der Evolution 21 1.3.1. Nischenbildung 21 1.3.2. Evolution ökologischer Beziehungen 22 1.3.3. Baldwin-Effekt 22 1.4. Biologische Konzepte in evolutionären Algorithmen 23 Übungsaufgaben 25 Historische Anmerkungen 26 2. Von der Evolution zur Optimierung 28 2.1. Optimierungsprobleme 29 2.2. Der simulierte evolutionäre Zyklus 33 2.3. Ein beispielhafter evolutionärer Algorithmus 35 2.4. Formale Einführung evolutionärer Algorithmen 43 2.5. Vergleich mit anderen Optimierungsverfahren 49 Übungsaufgaben 51 Historische Anmerkungen 52 3. Prinzipien evolutionärer Algorithmen 56 3.1. Wechselspiel zwischen Variation und Selektion 57 3.1.1. Ein einfaches binäres Beispiel 57 3.1.2. Die Gütelandschaft 58 3.1.3. Modellierung als Markovprozess 60 3.1.4. Das Problem lokaler Optima 62 3.1.5. Der Einfluss der Kodierung 63 3.1.6. Rollen der Mutation 68 3.2. Populationskonzept 71 3.2.1. Die Vielfalt in einer Population 72 3.2.2. Ein vergleichendes Experiment 74 3.2.3. Folgerungen für die Selektion 76 3.2.4. Varianten der Umweltselektion 77 3.2.5. Selektionsstärke 80 3.2.6. Probabilistische Elternselektion 81 3.2.7. Überblick und Parametrierung 86 3.2.8. Experimenteller Vergleich der Selektionsoperatoren 87 3.3. Verknüpfen mehrerer Individuen durch die Rekombination 90 3.3.1. Arten der Rekombination 90 3.3.2. Schema-Theorem 94 3.3.3. Formae als Verallgemeinerung der Schemata 104 3.3.4. Schema-Theorie und der Suchfortschritt 108 3.4. Selbstanpassende Algorithmen 117 3.4.1. Einfluss des Stands der Suche 117 3.4.2. Anpassungsstrategien für evolutionäre Operatoren 121 3.5. Zusammenfassung der Arbeitsprinzipien 124 3.6. Der ultimative evolutionäre Algorithmus 126 Übungsaufgaben 130 Historische Anmerkungen 133 4. Evolutionäre Standardalgorithmen 136 4.1. Genetischer Algorithmus 137 4.2. Evolutionsstrategien 143 4.3. Evolutionäres Programmieren 149 4.4. Genetisches Programmieren 156 4.5. Einfache Lokale Suchalgorithmen 165 4.6. Weitere Verfahren 169 4.6.1. Klassifizierende Systeme 169 4.6.2. Tabu-Suche 173 4.6.3. Memetische Algorithmen 175 4.6.4. Populationsbasiertes inkrementelles Lernen 176 4.6.5. Differentialevolution 179 4.6.6. Scatter Search 181 4.6.7. Kulturelle Algorithmen 183 4.6.8. Ameisenkolonien 186 4.6.9. Partikelschwärme 189 4.7. Kurzzusammenfassung 190 Übungsaufgaben 193 Historische Anmerkungen 194 5. Techniken für spezifische Problemanforderungen 197 5.1. Optimieren mit Randbedingungen 197 5.1.1. Übersicht über die Methoden 199 5.1.2. Dekoder-Ansatz 199 5.1.3. Restriktive Methoden 202 5.1.4. Tolerante Methoden 203 5.1.5. Straffunktionen 205 5.2. Mehrzieloptimierung 208 5.2.1. Optimalitätskriterium bei mehreren Zielgrößen 208 5.2.2. Überblick der Techniken zur Mehrzieloptimierung 213 5.2.3. Modifikation der Bewertungsfunktion 214 5.2.4. Berechnung der Pareto-Front 216 5.3. Zeitabhängige Optimierungsprobleme 224 5.4. Approximative Bewertung 229 5.4.1. Verrauschte Bewertung 230 5.4.2. Stabile Lösungen 233 5.4.3. Zeitaufwändige Bewertung 234 5.4.4. Bewertung durch Testfälle 237 5.4.5. Bewertung von Spielstrategien 239 Übungsaufgaben 240 Historische Anmerkungen 241 6. Anwendung evolutionärer Algorithmen 245 6.1. Vergleich evolutionärer Algorithmen 246 6.2. Entwurf evolutionärer Algorithmen 249 6.2.1. Der wiederverwendungsbasierte Ansatz 250 6.2.2. Der Forma-basierte Ansatz 251 6.2.3. Der analysebasierte Ansatz 252 6.3. Nutzung von Problemwissen 259 6.4. Fallstudie: Beladung von Containern 262 6.4.1. Aufgabenstellung 262 6.4.2. Entwurf des evolutionären Algorithmus 265 6.4.3. Ergebnisse 268 6.5. Fallstudie: Platzierung von Mobilfunkantennen 270 6.5.1. Aufgabenstellung 270 6.5.2. Entwurf des evolutionären Algorithmus 273 6.5.3. Ergebnisse 277 6.6. Fallstudie: Motorenkalibrierung 280 6.6.1. Aufgabenstellung 280 6.6.2. Entwurf des evolutionären Algorithmus 283 6.6.3. Ergebnisse 284 6.7. Fallstudie: Konstruktion von LEGO®-Bauwerken 288 6.7.1. Aufgabenstellung 288 6.7.2. Entwurf des evolutionären Algorithmus 290 6.7.3. Ergebnisse 291 Übungsaufgaben 297 Historische Anmerkungen 298 Anhang 300 A. Benchmark-Funktionen 301 B. Notation der Algorithmen 305 Literaturverzeichnis 307 Bildnachweis 327 Liste der Algorithmen 328 Symbolverzeichnis 330 Stichwortverzeichnis 332 Für die Lösung von Optimierungsproblemen mit evolutionären Algorithmen stattet dieses Buch seine Leser sowohl mit den gängigen Standardalgorithmen als auch mit den Arbeitsprinzipien, Vorgehensweisen und speziellen Techniken aus, mit denen evolutionäre Algorithmen für spezielle Probleme angepasst werden. Dabei zeichnen das Buch vor allem die hohe Anzahl an Beispielen, die anschauliche Darstellung der Grundlagen sowie vier ausführliche Fallstudien aus. Für die Anwendung evolutionärer Algorithmen in Industrie, Wirtschaft und Forschung sind die vorgestellten Ansätze zur Berücksichtigung von Randbedingungen, mehrerer sich widersprechender Zielfunktionen und verrauschte oder zeitabhängige Aspekte von großer Bedeutung. Evolutionäre Algorithmen sind ein vergleichsweise junges Optimierungsverfahren, welches das Wechselspiel zwischen Variation und Selektion der natürlichen Evolution imitiert. Der Inhalt Natürliche Evolution Von der Evolution zur Optimierung Prinzipien evolutionärer Algorithmen Evolutionäre Standardalgorithmen Techniken für spezifische Problemanforderungen Anwendung evolutionärer Algorithmen Die Zielgruppen Studierende der Informatik an Universitäten und Technischen Hochschulen Software-Entwickler in ihrer Anwendungsdomäne Der Autor Prof. Dr. Karsten Weicker lehrt und forscht an der HTWK Leipzig Front Matter....Pages I-X Natürliche Evolution....Pages 1-18 Von der Evolution zur Optimierung....Pages 19-46 Prinzipien evolutionärer Algorithmen....Pages 47-126 Evolutionäre Standardalgorithmen....Pages 127-187 Techniken für spezifische Problemanforderungen....Pages 189-236 Anwendung evolutionärer Algorithmen....Pages 237-291 Back Matter....Pages 293-331 Fur die Loesung von Optimierungsproblemen mit evolutionaren Algorithmen stattet dieses Buch seine Leser sowohl mit den gangigen Standardalgorithmen als auch mit den Arbeitsprinzipien, Vorgehensweisen und speziellen Techniken aus, mit denen evolutionare Algorithmen fur spezielle Probleme angepasst werden.