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
Literaturverzeichnis
Abbildungsverzeichnis
Abb. 1: Das Sphärenmodell R3
Abb. 2: Die Rosenbrock-Funktion im R3
Abb. 3: Die Treppenfunktion R3.
Abb. 4: Funktion mit normalverteilter Störung im R3
Abb. 5: Shekels Fuchsbauten im R3
Abb. 6: Die Rastrigin-Funktion im R3
Abb. 7: Schwefels Rochen im R3
Abb. 8: Boshafte Schwefel-Funktion im R3
Abb. 9: Die Griewangk-Funktion im R3.
1. Evolutionäre Algorithmen
1.1. Vorbemerkung
Seit Beginn der 1990´er Jahre haben Evolutionäre Algorithmen (EA) 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[1] 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.
1.2. Evolutionäre Standardalgorithmen
Mit der zunehmenden Leistungsfähigkeit von Rechnern hat in den letzten Dekaden eine Entwicklung begonnen, die zu den drei heutigen Hauptströmungen Evolutionärer Algorithmen führte.
Ingo Rechenberg und Hans-Paul Schwefel arbeiteten etwa an der Optimierung des Windwiderstandes eines Stromlinienkörpers. „Als das Problem mathematisch nicht gelöst werden konnte, kam man auf den Gedanken, durch die Nachahmung evolutionärer Prinzipien in vereinfachter Form, den Körper sukzessiv zu optimieren. Aus diesen Überlegungen der praktischen Optimierung entstand die Evolutionsstrategie (ES) . “[2]
Sie verwendet kontinuierliche Parameter und Mechanismen zur Selbstadaption ihrer Steuerungsparameter und ist vor allem auf Optimierungsprobleme mit kontinuierlichen Parametern zugeschnitten.
„John H. Holland schließlich ging es bei seinen Untersuchungen um eine Theorie adaptiver Systeme, welche über die Biologie hinausging und auch Phänomene ganz anderer Bereiche, wie z.B. der Ökonomie, einschloß. Seine zur Modellierung adaptiver Prozesse vorgeschlagenen (...) Genetische Algorithmen (GA) beruhten auf einer Abstraktion und Generalisierung des Populationskonzepts, der genetischen Codierung und Genetischer Operatoren.“[3] GA verwenden in ihrer ursprünglichen Form eine binäre Codierung, so dass sie sich vor allem für die kombinatorische Optimierung eignen.
Besondere Bedeutung unter den vielen Verfahrensvarianten hat auch die Genetische Programmierung (GP) erlangt, deren Grundgedanke darin besteht, „(...) Lösungen in Form von Computerprogrammen zu repräsentieren, die dann mit den Mechanismen der Evolution verändert werden.“[4]
Die Suche nach einer Möglichkeit, künstlich intelligente Automaten zu entwerfen, die
„(...) einerseits innovative Problemlösungen generieren, andererseits aber auch Schlussfolgerungen auf das Funktionieren des menschlichen Intellekts zulassen“[5], bestimmte die Evolutionäre Programmierung (EP), mit den Hauptoperatoren Mutation und Selektion. EP spielt aufgrund einiger einschränkender Annahmen heute aber eine eher geringere Rolle als die anderen Richtungen.[6]
1.2.1. Terminologie
Die Terminologie der EA orientiert sich stark an der Terminologie der Evolutionstheorie und der Genetik. Eine einzelne Lösung eines Ausgangsproblems wird als Individuum bezeichnet. Jedes Individuum hat eine bestimmte Güte, welche äquivalent in der Natur zu finden ist, wo sie die Überlebensfähigkeit eines Individuums beschreibt. Diese Güte bezeichnet man als Fitness. Aufgabe der EA ist es, das Individuum mit der höchstmöglichen Fitness zu finden, da es die optimale Lösung für das Ausgangsproblem darstellt. Mehrere Individuen werden zu einer Population zusammengefasst, die über den gesamten Lösungsraum „verstreut“ sein kann. Wird eine Population im Laufe des Algorithmus durch eine neue ersetzt, so spricht man – wie in der Natur – von Generationen. Ein Individuum besitzt eine Reihe von Eigenschaften bzw. Parametern, die letztendlich die Fitness bestimmen. Die Einheiten, die diese Parameter repräsentieren, werden Gene genannt. Ein Gen kann verschiedene Werte annehmen, welche man als Allele bezeichnet. Als Chromosomen bezeichnet man im Allgemeinen die Gesamtheit aller Gene eines Individuums.
1.2.2. Evolutionsstrategien
In den sechziger Jahren des zwanzigsten Jahrhunderts wurde von deutschen Wissenschaftlern versucht, die Evolutionstheorie auch für Suchalgorithmen auszunutzen.
I. Rechenberg und H.-P. Schwefel erarbeiteten dabei eine Variante Evolutionärer Algorithmen, die sie Evolutionsstrategien nannten.
Ausgangspunkt bei den ES ist eine Population mit m Individuen, wobei die Gene ausschließlich reelle Werte annehmen. Aus dieser Startpopulation werden λ Kinder durch Rekombination und anschließender Mutation (unter Beachtung der Mutationsschrittweiten) erzeugt, aus welchen im Anschluß m neue Eltern selektiert werden, die dann die Startpopulation ersetzen. Dieser Prozess wird solange fortgeführt, bis ein Abbruchkriterium erfüllt ist. Man wird feststellen, dass bei ES die Mutation der wichtigste genetische Operator ist, da jedes neue Individuum mit dessen Hilfe erzeugt wird.
Mit ES wurden in ihren Einsatzgebieten sehr gute Ergebnisse erzielt, doch sie sind leider nicht so universell einsetzbar wie Genetische Algorithmen. Auch neigen sie eher als GA dazu vorzeitig in lokalen Optima „steckenzubleiben“, weshalb heutzutage häufiger mit Genetischen Algorithmen als mit Evolutionsstrategien gearbeitet wird.[7]
1.2.3. Genetische Algorithmen
Um die Entwicklung einer Population von Lösungen eines Ausgangsproblems überhaupt simulieren zu können, müssen die Lösungen zunächst in geeigneter Form dargestellt werden. Man spricht hier von der Form der Kodierung, die zu wählen ist. Letztlich muss es möglich sein, mit der gewählten Repräsentation jede denkbare Lösung des Problems darstellen zu können. Ursprünglich wurde bei Genetischen Algorithmen ausschließlich die binäre Kodierung verwendet, d.h. Gruppen von Bits repräsentieren dabei jeweils ein bestimmtes Merkmal der Lösung. Heute werden jedoch zunehmend auch andere Kodierungsformen, wie reelle Zahlen oder Permutationsfolgen verwendet, da diese oftmals besser auf das Optimierungsproblem zugeschnitten und leichter verständlich sind.
Nach der Wahl einer geeigneten Kodierung muss noch definiert werden, was als Fitness der Individuen betrachtet wird. Üblicherweise ist dies eine Funktion, die von allen kodierten Parametern abhängig ist. Das Ziel des GA ist es nun, für diese Funktion ein möglichst globales Maximum der Fitness-Funktion zu bestimmen und somit das Individuum zu finden, das die beste Lösung für das Ausgangsproblem darstellt.
1.2.4. Genetische Programmierung
Die Genetische Programmierung (GP), eine Variante der Genetischen Algorithmen mit einer besonderen Form der Lösungsrepräsentation, ist ein evolutionärer Ansatz, um automatisch ein Computerprogramm zu generieren, welches eine vorgegebene Aufgabenstellung erfolgreich bearbeitet. Als Lösung erhält man dabei ein allgemeines Programm, das auf eine betrachtete Klasse von Problemstellungen anwendbar ist. „Anders ausgedrückt untersuchte man, ob Computerprogramme, die eine gegebene Aufgabenstellung lösen können, sich nicht auch rein automatisch generieren lassen. Diese frühen Versuche hatten nur bescheidenen Erfolg, nicht zuletzt, weil noch keine hinreichend leistungsfähigen Computer verfügbar waren.“[8]
Mögliche Anwendungen der GP sind das Lernen von Bool´schen Ausdrücken, das Lösen von Gleichungssystemen oder die Bestimmung von Zufallszahlen. Die Startpopulation besteht dabei aus einer Menge von Computerprogrammen, die zufällig aus vorab festgelegten Mengen problemangepasster elementarer Funktionen sowie passender Variablen und Konstanten generiert werden. Die Fitness eines Individuums sagt aus, wie gut das jeweilige Programm die gestellte Aufgabe löst. J.R. Koza erzielte unter Verwendung der Programmiersprache LISP sehr gute Erfolge mit Genetischer Programmierung.[9]
[...]
[1] Charles Darwin (1809-1882), heute oft als Vater der Evolutionstheorie bezeichnet
[2] [NISS97], S.9
[3] Ebenda, S. 9
[4] Ebenda, S. 11
[5] Ebenda, S. 9
[6] vgl. [GERKLAKRU], S. 2
[7] vgl. [NISS94], S.140ff.
[8] [NISS97], S.111
[9] vgl. [NISS94], S.89ff.
-
-
-
-
Laden Sie Ihre eigenen Arbeiten hoch! Geld verdienen und iPhone X gewinnen. -
-
Laden Sie Ihre eigenen Arbeiten hoch! Geld verdienen und iPhone X gewinnen. -
-
Laden Sie Ihre eigenen Arbeiten hoch! Geld verdienen und iPhone X gewinnen. -
-
Laden Sie Ihre eigenen Arbeiten hoch! Geld verdienen und iPhone X gewinnen. -
-
Laden Sie Ihre eigenen Arbeiten hoch! Geld verdienen und iPhone X gewinnen. -
-
Laden Sie Ihre eigenen Arbeiten hoch! Geld verdienen und iPhone X gewinnen. -
-
Laden Sie Ihre eigenen Arbeiten hoch! Geld verdienen und iPhone X gewinnen. -
-
Laden Sie Ihre eigenen Arbeiten hoch! Geld verdienen und iPhone X gewinnen.