Seit Beginn der 1990´er Jahre haben Evolutionäre Algorithmen als universell anwendbare Verbesserungs- und Optimierungsstrategien eine weite Verbreitung in allen Bereichen von Wirtschaft und Forschung gefunden. Ihr großer Erfolg liegt u.a. in der Tatsache begründet, dass ihre Anwendung auf einem scheinbar einfachen und leicht nachvollziehbarem Prinzip, dem Darwinschen Evolutionsparadigma, oder etwas zugespitzt ausgedrückt, dem „survival of the fittest“ basiert: Durch die Anwendung von Variation und Selektion auf eine Population von Lösungsalternativen werden nach dem Muster der Natur schrittweise bessere Lösungen gefunden und auf diese Weise Optima bestimmt – oder zumindest approximiert.
Inhaltsverzeichnis
1. Evolutionäre Algorithmen
1.1. Vorbemerkung
1.2. Evolutionäre Standardalgorithmen
1.2.1. Terminologie
1.2.2. Evolutionsstrategien
1.2.3. Genetische Algorithmen
1.2.4. Genetische Programmierung
2. Testumgebung Evolutionärer Algorithmen
2.1. Testfunktionen
2.1.1. Das Sphären-Modell
2.1.2. Die Rosenbrock-Funktion
2.1.3. Die Treppenfunktion
2.1.4. Funktion mit normalverteilter Störung
2.1.5. Shekels Fuchsbauten
2.1.6. Die Rastrigin-Funktion
2.1.7. Schwefels Rochen
2.1.8. Boshafte Schwefel-Funktion
2.1.9. Die Griewangk-Funktion
2.2. Kombinatorische Optimierungsprobleme als Testumgebung für EA
3. Problematik praktischer Leistungsvergleiche
4. Stärken und Schwächen von EA
5. Rückschlüsse für praktische Anwendungen
6. Fazit
Zielsetzung & Themen
Das Hauptziel dieser Arbeit ist die Untersuchung und Definition einer geeigneten Testumgebung, um die Leistungsfähigkeit von Evolutionären Algorithmen (EA) in verschiedenen Problemkontexten beurteilen zu können. Es wird der Frage nachgegangen, wie ein fairer Leistungsvergleich zwischen EA und anderen Optimierungsverfahren gestaltet werden kann.
- Grundlagen und Hauptströmungen Evolutionärer Algorithmen
- Methodik zur Erstellung einer fairen Testumgebung mittels standardisierter Testfunktionen
- Herausforderungen bei empirischen Leistungsvergleichen von Heuristiken
- Analyse der spezifischen Stärken und Schwächen von EA
- Kriterien für den praktischen Einsatz von EA in verschiedenen Anwendungsbereichen
Auszug aus dem Buch
2.1. Testfunktionen
Um einen bestmöglichen Vergleich von Optimierungsverfahren durchführen zu können, ist es notwendig eine faire Testumgebung zu kreieren, d.h. man müsste eigentlich immer noch die jeweiligen Parametereinstellungen berücksichtigen bzw. nur optimale Einstellungen zulassen. Dies ist jedoch in der Regel kaum möglich, da es eine Vielzahl von Variationsmöglichkeiten der Parameter gibt und man die optimalen Einstellungen häufig gar nicht kennt. Aus diesem Grund hat sich in der Evolutionsforschung und in der Literatur ein recht pragmatischer Ansatz durchgesetzt. Es werden einfach einige Funktionen definiert, die zum Testen der Algorithmen herangezogen werden. Diese Testfunktionen werden generell so gewählt, dass die zu vergleichenden Verfahren im Mittel gleichermaßen bevorzugt und benachteiligt werden. „Dabei spielt insbesondere das Verhalten der Algorithmen bei Testfunktionen eine Rolle, die viele lokale Optima und/oder Plateau-Flächen aufweisen, um festzustellen, wie leicht die Algorithmen in solche „Fallen tappen“, und um festzustellen, ob sie aus diesen Fallen durch Mutation oder Rekombination wieder herauskommen.“
Im Folgenden werden Funktionen vorgestellt, die sehr heterogen sind. Sie enthalten stetige und unstetige, quadratische und nicht-quadratische, uni- und multimodale, niedrig- und hochdimensionale sowie stochastische und deterministische Funktionen. Zudem wurden sie so gewählt, dass sie viele „boshafte“ Eigenschaften haben. Sie variieren stark hinsichtlich der Anzahl und der Verteilung der lokalen Minima sowie hinsichtlich der Verteilung der Werte der lokalen Minima und der Größe ihres Einzugsbereiches.
Zusammenfassung der Kapitel
1. Evolutionäre Algorithmen: Einführung in die Grundlagen des Darwinschen Evolutionsparadigmas und Darstellung der drei Hauptströmungen (Evolutionsstrategien, Genetische Algorithmen, Genetische Programmierung) sowie deren Terminologie.
2. Testumgebung Evolutionärer Algorithmen: Erläuterung der Notwendigkeit von Testfunktionen und deren Klassifizierung, um Algorithmen vergleichbar zu machen und die Robustheit gegenüber lokalen Optima zu prüfen.
3. Problematik praktischer Leistungsvergleiche: Analyse der methodischen Schwierigkeiten beim Vergleich von Heuristiken, insbesondere bezüglich der Auswahl von Testinstanzen und Konkurrenzverfahren.
4. Stärken und Schwächen von EA: Gegenüberstellung der Vorteile, wie die breite Anwendbarkeit und Populationsrobustheit, mit den Nachteilen, wie der fehlenden Optimalitätsgarantie und dem Rechenaufwand.
5. Rückschlüsse für praktische Anwendungen: Ableitung von Entscheidungskriterien für den praktischen Einsatz, basierend auf den identifizierten Stärken und Schwächen in Bezug auf spezifische Problemmerkmale.
6. Fazit: Zusammenfassende Bewertung der Leistungsfähigkeit von EA und die Feststellung, dass keine einzelne heuristische Methode allen anderen in jedem Bereich überlegen ist.
Schlüsselwörter
Evolutionäre Algorithmen, Optimierung, Testfunktionen, Evolutionsstrategien, Genetische Algorithmen, Fitness, Mutation, Selektion, Leistungsvergleich, Heuristiken, Kombinatorische Optimierung, Lokale Optima, Populationsansatz, Zielfunktion, Simulationsläufe.
Häufig gestellte Fragen
Worum geht es in dieser Arbeit grundsätzlich?
Die Arbeit beschäftigt sich mit der Beurteilung der Leistungsfähigkeit von Evolutionären Algorithmen und der dazu notwendigen Schaffung einer geeigneten, fairen Testumgebung.
Was sind die zentralen Themenfelder der Publikation?
Zentrale Themen sind die theoretischen Grundlagen evolutionärer Verfahren, die Auswahl mathematischer Testfunktionen für Benchmarks sowie die kritische Auseinandersetzung mit empirischen Leistungsvergleichen.
Was ist das primäre Ziel oder die Forschungsfrage?
Ziel ist es, Methoden aufzuzeigen, wie die Eignung von Evolutionären Algorithmen für spezielle Optimierungsprobleme objektiv bewertet werden kann.
Welche wissenschaftliche Methode wird primär verwendet?
Die Arbeit stützt sich auf eine Literaturanalyse bestehender Verfahren der Evolutionsforschung und die Systematisierung bekannter Testfunktionen für Optimierungsaufgaben.
Was wird im Hauptteil der Arbeit behandelt?
Der Hauptteil gliedert sich in die Vorstellung der Algorithmus-Grundlagen, eine detaillierte Auflistung verschiedener mathematischer Testfunktionen sowie die Diskussion der Problematik beim Vergleich verschiedener Optimierungsmethoden.
Welche Schlüsselwörter charakterisieren die Arbeit?
Die Arbeit wird durch Begriffe wie Evolutionäre Algorithmen, Testfunktionen, Optimierung, Fitness, Selektion und Leistungsvergleich definiert.
Warum sind die vorgestellten Testfunktionen so heterogen?
Sie sind heterogen, um einen möglichst großen Bereich an Eigenschaften (wie Stetigkeit, Konvexität oder Multimodalität) abzudecken und sicherzustellen, dass keine Methode durch einseitig gewählte Testbedingungen unzulässig bevorzugt wird.
Was bedeutet der Begriff "boshafte" Eigenschaft bei Testfunktionen?
Dies bezieht sich auf Funktionen, die gezielt mit vielen lokalen Minima oder flachen Plateaus konstruiert wurden, um Algorithmen in Suchfallen zu locken und ihre Fähigkeit zu testen, diese wieder zu verlassen.
Eignen sich Evolutionäre Algorithmen immer für jedes Optimierungsproblem?
Nein, der Autor weist darauf hin, dass bei bereits existierenden effizienten Spezialverfahren oder Problemen, die eine garantierte globale Optimalität erfordern, andere Ansätze sinnvoller sein können.
- Citation du texte
- Ronny Ibe (Auteur), 2005, Testumgebung zur Beurteilung der Leistungsfähigkeit evolutionärer Algorithmen, Munich, GRIN Verlag, https://www.grin.com/document/66665
